Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

In a Markov chain, a state $j$ is transient if $f_{jj}<1$ ($f_{jj}$ is probability of ever visiting state $j$ starting from state $j$ ). Suppose, I have an irreducible transient DTMC (means all states are transient). Now, I want to prove that for any $i,j$ in $S$ ($S$ is DTMC state space), $f_{ij}$ (i.e probability of ever reaching state $j$ starting from state $i$) is less than 1. It is clear that $f_{ii}<1$ and $f_{jj}<1$. But, how to prove that $f_{ij}<1$ for any $i,j$.

Thanks Prasenjit

share|improve this question
    
You need to clarify what you mean, exactly, by "DTMC." For instance, let the states be $0, 1, \ldots, n, \ldots$. Define a Markov chain with transition probabilities $p_{i,i+1} = 1$. Because $f_{ii}=0$ for all $i$ it is transient. Because every state is eventually reached from $0$ it is irreducible. Nevertheless, your intended conclusion is obviously not true in this example. –  whuber Dec 30 '10 at 16:03
    
Perhaps the questioner forgot to add the condition that the state space is finite. –  onestop Dec 30 '10 at 17:25
    
@onestop I initially suspected that, but then it occurred to me that in the finite case there must exist either an absorbing or a recurrent state; neither of those can be transient. Thus a finite transient Markov chain does not exist. –  whuber Dec 30 '10 at 18:07
    
@whuber - thanks for clarifying that. I started suspecting as much as I pondered after submitting my previous comment so tried to add a question mark to its end but was outside the arbitrary 5-minute edit window. –  onestop Dec 30 '10 at 22:49
add comment

1 Answer

Your claim is false: there exist transient Markov chains such that $f_{ij}=1$ for some (but not all) states $i$ and $j$.

For example, assume that the state space is the union of the discrete halfline $\mathbb{Z}_+$ and of a discrete circle $\mathbb{Z}/N\mathbb{Z}$ with $N\ge3$, the halfline and the circle meeting at $0$. Write $c(k)$ for the $k$th state on the circle, counted clockwise and starting from $0$, thus $c(0)=c(N)=0$ but $c(k)$ for $1\le k\le N-1$ is not on the halfline $\mathbb{Z}_+$.

The transitions are as follows. If one is at $i$ in $\mathbb{Z}_+$ with $i\ne0$, one moves to $i+1$ or to $i-1$ with probability $p$ or $1-p$, respectively. If one is at $0$, one moves to $1$ or to $c(1)$, both with positive probability. If one is at $c(k)$ with $1\le k\le N-1$, one moves to $c(k+1)$ with probability $1$.

In words, while on the halfline, one performs a biased random walk and while on the circle, one moves on the circle clockwise and deterministically until one is back at $0$.

For every $p>1/2$, this Markov chain is transient. Nevertheles, for every $k$ and $\ell$ such that $1\le k<\ell\le N-1$, starting from $c(k)$, one hits $c(\ell)$ with full probability hence $f_{c(k)c(\ell)}=1$.

share|improve this answer
    
What is true, however, is that if there exists a state $i$ such that $f_{ii}=1$, or if there exist two different states $i$ and $j$ such that $f_{ij}=f_{ji}=1$, then the Markov chain is recurrent. –  Did Dec 31 '10 at 17:08
    
understood, but it is true that for a transient DTMC Lt k->infinity pij(k) =0 for all i,j . How to prove that? We know that E(Mj|X0=i)=sigma k=1 to infinity pij(k). Here Mj= number of visits to state j. We can show that E(Mj|X0=i)=fij/1-fij . We need to show that for transient DTMC E(Mj|X0=i)=finite then it is obvious that pij(k) when k->infinity is zero. But we can't say that fij<1 for all i,j. Then how to prove that this expectation will be finite. Hope I am making my point clear. –  aaaaaa Jan 2 '11 at 17:54
    
The point here is that, if the Markov chain is transient, then $f_{jj}<1$ for every state $j$. To visit $j$ at least $n+1$ times starting from $i$, one first has to reach $j$, which happens with probability $f_{ij}$, and then to come back to $j$ at least $n$ times, which happens with probability $(f_{jj})^{n}$. Thus $E(M_j|X_0=i)$ is the sum over $n\ge0$ of $f_{ij}(f_{jj})^n$, which is finite if and only if $f_{jj}<1$, and then $E(M_j|X_0=i)=f_{ij}/(1-f_{jj})$. (Be careful: your comment is awfully written and you write "equals zero" instead of "converges to zero".) –  Did Jan 2 '11 at 19:22
    
yes, I understood my mistake of finding the expectation after posting this. Thanks for pointing it also. –  aaaaaa Jan 3 '11 at 4:26
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.