Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.