# Irreducible and aperiodic Markov chain : $P^t(x,y)>0$

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.

-
For a finite one. Thanks for pointing this out. – Nicolas Essis-Breton Sep 14 '11 at 17:57
Not really. I say false because of this: Since the chain is irreducible I can find a $t_{xy} \ni P^{t_xy}(x,y)>0, \forall x,y\in\Omega$. Let $t=\min{t_{xy},x,y\in\Omega}$, I think there is no guarantee that $P^{t+1}(x,y)>0,\forall x,y\in\Omega$. – Nicolas Essis-Breton Sep 14 '11 at 18:50
Think of the simplest periodic markov chains. – Srivatsan Sep 14 '11 at 18:55
I see. Take a simple random walk on an $n$-cycle, where $n$ is even. – Nicolas Essis-Breton Sep 14 '11 at 19:48
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. – Srivatsan Sep 14 '11 at 19:53

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$.

-
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. – Byron Schmuland Sep 14 '11 at 19:02
Thanks for clarifying this Srivatsan. – Nicolas Essis-Breton Sep 14 '11 at 19:12

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.

-
This is an elegant argument indeed. (I ran out of my votes, so I'll upvote this later tonight.) I am wondering whether the existence of the limiting distribution needs the "hands-on" argument to be used somewhere? I remember so from my courses, but I don't think my instructor covered the material in the same order as others. – Srivatsan Sep 14 '11 at 19:08
Thanks for this alternative Byron. I think it gives some insight. I marked the "hands on" proof as answer, because, I didn't know it, and I feel I can appreciate your answer more, once I know the "hands on" one. – Nicolas Essis-Breton Sep 14 '11 at 19:18
@Nicolas No problem, I hope my post is useful for you. – Byron Schmuland Sep 14 '11 at 19:59
@Srivatsan The eventually positivity of $P^t(x,y)$ is not an ingredient in the proof. The strict positivity of $\pi(y)$ comes from the equation $1=\pi(y) \mathbb{E}_y(T_y)$, where $\mathbb{E}_y(T_y)$ is the expected return time starting at $y$. Of course, you need to prove that the equation is true, and also that $\mathbb{E}_y(T_y)<\infty$. The convergence of $P^t(x,y)$ is another issue. – Byron Schmuland Sep 14 '11 at 20:04
@Byron I see. Thanks for the clarification. – Srivatsan Sep 14 '11 at 20:05