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.

I am wondering if anyone could prove the following equivalent definition of recurrent/persistent state for Markov chains:

1) $P(X_n=i,n\ge1|X_0=i)=1$

2) Let $T_{ij}=min\{n: X_n=j|X_0=i\}$, a state $i$ is recurrent if for $\forall j$ such that $P(T_{ij}<\infty)>0$, one has $P(T_{ij}<\infty)=1$

share|improve this question
    
Is this homework? –  picakhu Jan 19 '11 at 6:01
    
Do you want the equivalence of 1 and 2 proven or do you want them proven from some other definition? –  Calle Jan 19 '11 at 6:52
    
This is not homtwork! If I ask homework, I will specifically say that, guys! –  Qiang Li Jan 19 '11 at 15:43
    
@Calle: either way is fine. Do you have some thoughts? Please... –  Qiang Li Jan 19 '11 at 15:44
    
1) Is obvious. I mean it stems from the definition. (the probability that we visit every state repeatedly(multiple times) is 1) 2) Is also obvoius for the same reason(s) I guess what I mean to say is that: what exactly do you mean by a proof? are you looking for Rigor? –  picakhu Jan 19 '11 at 20:20

3 Answers 3

See this page.

Edit: Since incorrect statements continue to pop up on this page, let me explain once again the situation.

First, two notations (standard in the field): for every state $i$, $P_i$ denotes the distribution of the Markov chain $(X_n)_{n\ge0}$ conditionally on the event $[X_0=i]$ and $T_i=\inf\{n\ge1;X_n=i\}$ denotes the first hitting time of $i$. Next, a tautology: the events $[\exists n\ge1,X_n=i]$ and $[T_i<+\infty]$ are equal.

Second, a statement of the question the OP is interested in. One considers two properties which may or may not be satisfied by a given Markov chain $(X_n)_{n\ge0}$ and a given state $i$:

(1) $P_i(\exists n\ge1,X_n=i)=1$.

(2) For every state $j$, either $P_i(T_j<+\infty)=0$ or $P_i(T_j<+\infty)=1$.

Property (1) is often taken as a definition of the fact that $i$ is a recurrent state of the Markov chain $(X_n)_{n\ge0}$. Property (2) is more unusual.

Now, an answer to the question.

Property (1) implies property (2). Proof: see Byron's post. Note that if (1) holds, both $P_i(T_j<+\infty)=0$ and $P_i(T_j<+\infty)=1$ can occur for different states $i$ and $j$ of the same Markov chain. Example: state space $\{0,1,2\}$, transitions $0\to1$, $0\to2$, $1\to1$, $1\to2$, $2\to1$ and $2\to2$ all with positive probabilities, the other transitions with probability zero. Then $P_i(T_0<+\infty)=0$ and $P_i(T_j<+\infty)=1$ for every $i$ and every $j\ne0$.

Property (2) does not imply property (1). Proof by an example: state space $\mathbb{Z}$, transitions $i\to i+1$ with probability $1$. Then $P_i(T_j<+\infty)=0$ if $j\le i$, $P_i(T_j<+\infty)=1$ if $j\ge i+1$, but $P_i(\exists n\ge1,X_n=i)=0$ for every $i$.

Finally (and once again), a congenial reference for this is the first chapter of the book Markov chains by James Norris, which is freely available here.

share|improve this answer

A recurrent state will satisfy property (2), but not the other way around. Take a two state Markov chain that jumps from $i$ to $j$ with probability one, then stays there forever. Then $i$ is transient, but $P(T_{ij}<\infty)=1$.

Edit: Here's a sketch of (1) implies (2) in terms of "taboo probabilities". We assume that $i$ is recurrent, and all of the probabilities below are conditioned on $X_0=i$.

Define $T_i=\inf(n\geq 1 : X_n=i)$ and $T_j=\inf(n\geq 1 : X_n=j)$. We want to show that $P(T_j<\infty)>0$ implies $P(T_j<\infty)=1$. It suffices to assume $i\not= j$, since $P(T_i<\infty)=1$.

Since $i$ is recurrent, we have $P(T_i < \infty)=1$ so that $P(T_j < T_i)+P(T_i < T_j)=1,$ since $T_i=T_j$ implies $T_i=\infty$.

Also, if $P(T_j < \infty)>0$ we must have $P(T_j < T_i)>0$, by considering the shortest possible path from $i$ to $j$ with non-zero probability.

Finally, letting $n$ represent the number of times we return to $i$ without hitting $j$, the strong Markov property gives

$$P(T_j < \infty)=\sum_{n=0}^\infty P(T_i < T_j)^n P(T_j < T_i) =\sum_{n=0}^\infty P(T_i < T_j)^n [1-P(T_i < T_j)]=1.$$

share|improve this answer
    
for your first disproof, I think here $T_{ij}$ can be 0. Thus, in your example, $P(T_{ii} \lt \infty)>0$ but $P(T_{ii} \lt \infty) \ne 1$. Therefore, $i$ is not recurrent. Can you think of other examples to disprove it, or you can actually prove 2) also implies 1). Thanks a lot for your answer. –  Qiang Li Jan 25 '11 at 3:22

I think the first property is wrong. That would be a strictly periodic state. Perhaps you missed something?

share|improve this answer
    
I take it to mean the union $\cup_{n=1}^\infty (X_n=i)$. –  Byron Schmuland Jan 24 '11 at 17:40
    
how did you understand 1)? Like $$P(X_n=i, \forall n| X_0=i)=1$$? –  Qiang Li Jan 25 '11 at 3:14
    
No, rather that for some $n$, $P(X_n = i | X_0 = i) =1$. It's the normal way to read the equation, I think. –  leonbloy Jan 25 '11 at 12:02
    
right, that is the correct meaning. The same as Byron wrote above. Then if you understood it correctly, why would you still think it is not the definition of recurrent state? –  Qiang Li Jan 25 '11 at 20:24
    
No, that's not the same. Suppose the propery is true for a particular $n$ (say, for $n=5$) , then it would be that true $P(X_5=i | X_0=i)=1$ Now, that would imply that we are certain that the state 'i' will be revisited in exactly 6 steps. Hence, it would be periodic. –  leonbloy Jan 25 '11 at 20:32

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.