3
$\begingroup$

Consider a Markov chain $X$ with transition probability $P$ and finite state space $\Omega$. Which of the following statement is true?

  1. If $X$ is irreducible then $\exists t>0 \ni P^t(x,y)>0, \forall x,y\in\Omega$.

  2. If $X$ is irreducible and aperiodic then $\exists t>0 \ni P^t(x,y)>0, \forall x,y\in\Omega$.

I think it's (2.), and (1.) is false, but I can't find how to prove it.

  • 0
    Yes. (In fact, you can take a special case of that with just two states.) Another class of examples is a directed cycle (left edge in, right edge out) of length $n$ for any $n$, even or odd.2011-09-14

2 Answers 2

4

HINT You are correct that (1.) is false and (2.) is true. (1.) has a very simple counter-example, which I will leave you to figure out. Here I give a proof sketch for (2.).

[Added:] This is a roundabout proof compared to Byron's elegant one, but this is the proof that first came to my mind. :)

For each $x \in \Omega$, let $C(x)$ be the set of lengths of walks from $x$ to $x$ with positive probability. The aperiodicity condition says that the set $C(x)$ has gcd $1$. Therefore, there exist $a_1, a_2, \ldots, a_m \in C(x)$ such that $\gcd(a_1, a_2, \ldots, a_m)=1$.

The proof then proceeds in the following stages:

  1. (This is the crucial step of the proof.) For any collection of numbers $\{ a_1, a_2, \ldots, a_m \}$ with gcd equal to $d$, show that there exists a number $T \in \mathbb Z_{\geq 0}$, such that the following holds: if $t \geq T$ and $t$ is a multiple of $d$, then $t$ can be expressed a nonnegative integer combination of $a_1, \ldots, a_m$. This means that there exist $q_1, q_2, \ldots, q_m \in \mathbb Z_{\geq 0}$ such that $ t = q_1 a_1 + q_2 a_2 + \ldots + q_m a_m. $ HINT One way to prove this statement will be via mathematical induction and Bézout's identity. (See below for some more details on this problem.)

  2. For $x \in \Omega$, there exists a number $T_x \in \mathbb N$, such that for all $t \geq T_x$, there exists a walk from $x$ to $x$ (of positive probability) of length exactly $t$.

  3. For all $y \in \Omega$ and all $t \geq T_x+n$, there exists a walk from $x$ to $y$ (of positive probability) of length exactly $t$.
  4. Show how to conclude the claim in the question from the above statement.

More details on Step 1.

Step 1 is related to the so-called Frobenius coin problem. In the coin problem, we are given a number of denominations $a_1, a_2, \ldots, a_m$ (that do not have any nontrivial common factor), and are asked to compute the largest denomination $g$ such that $g$ cannot be expressed as an integer linear combination of these denominations. The proof that I have left as exercise essentially asks you to show that such a $g$ exists (i.e., it is finite). Moreover, in our notation, $T$ is at least $g+1$.

  • 0
    Yours is the "hands on" proof that students should master first. My alternative uses heavy machinery that also needs proof; I just posted it as another way to understand the result.2011-09-14
3

For an irreducible, aperiodic Markov chain on a finite state space, we have $P^t(x,y)\to\pi(y)>0$ where $\pi$ is the unique invariant probability distribution of the chain. Since the values $\pi(y)$ are all strictly positive, the result follows.

  • 0
    @Byron I see. Thanks for the clarification.2011-09-14