# First passage time distribution in a irreducible transient discrete-time Markov chain (DTMC)

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

-
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

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

-
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