Originally Posted by

**Wolfram** "It is possible to show that if (the transition probability) p_ij > 0, then P (n_ij = 0) goes to 0 exponentially as n --> infinity."

This is not always true. This is true iff the Markov chain is positive recurrent, I believe. (And if state i is accessible from the starting point). Maybe your Markov chain has finitely many states?

Here is a proof (that positive recurrence suffices). Let $\displaystyle \tau$ be the time of the first transition from i to j, so that $\displaystyle P(n_{ij}=0)=P(\tau>n)$. Note that $\displaystyle P_x(\tau>1)=1$ if $\displaystyle x\neq i$, and $\displaystyle P_i(\tau>1)=1-p_{ij}$. By Markov property we have, for all $\displaystyle n$, $\displaystyle P(\tau>n+1)=E[{\bf 1}_{(\tau>n)}P_{X_n}(\tau>1)]=P(\tau>n)-p_{ij}P(\tau>n, X_n=i)$, where the last equality results from the previous remark. Thus,

$\displaystyle P(\tau>n+1)=P(\tau>n) (1-p_{ij}P(X_n=i|\tau>n))$.

For $\displaystyle P(\tau>n)$ to decrease exponentially, it would be sufficient if the last probability is greater than a positive constant, for a positive proportion of indices $\displaystyle n$ (we can't expect the probability to be positive for all $\displaystyle n$).

After a short thought, it appears that the conditional distribution of $\displaystyle (X_0,\ldots,X_n)$ given $\displaystyle \{\tau>n\}$ is a Markov chain with similar transitions as the initial ones, *expect* that the transition from i to j is removed and the other transitions starting from i are normalized accordingly. Note that this doesn't work if (i,j) is the only possible transition starting from i, i.e. if $\displaystyle p_{ij}=1$; this special case could be dealt with by modifying the Markov chain at the very beginning so as to "erase the (useless) state i" (it's a bit messy to explain, I hope you get the picture, anyway it's not the crucial part).

So let us consider this new Markov chain (without the transition (i,j)). If the state space was finite, of course it still is finite (same state space), so that the Markov chain still is positive recurrent. In the general case, the Markov chain (restricted to the still accessible states) still is positive recurrent as well, I guess, but I can't think of an argument so I let you figure that out if you want. Therefore, if $\displaystyle d$ denotes the period of the new Markov chain (whose law is denoted by $\displaystyle \widetilde{P}$), then $\displaystyle \widetilde{P}(X_{kd+n_0}=i)\to_{k\to\infty}\pi(i)$ for some invariant probability measure $\displaystyle \pi$, with $\displaystyle \pi(i)>0$ because i is accessible from the initial state (and where $\displaystyle n_0\in\{0,\ldots,d-1\}$). So we have a constant $\displaystyle c>0$ and $\displaystyle k_0,n_0>0$ such that, for all $\displaystyle k>k_0$, $\displaystyle P(X_{kd+n_0}=i|\tau>kd)>c$.

This gives the conclusion: we have $\displaystyle P(\tau>n+1)\leq P(\tau>n)$ for all $\displaystyle n$, and $\displaystyle P(\tau>n+1)\leq (1-p_{ij}c)P(\tau>n)$ for indices $\displaystyle n$ that are multiple of $\displaystyle d$ ($\displaystyle +n_0$, and large enough). Hence a geometric(=exponential) rate of decrease (here we use $\displaystyle p_{ij}>0$). If this is not obvious to you, try to prove it.

This should answer your questions; you may ask for additional explanations if you need.