# Limit of a Markov transition matrix

Here,

$$T_n=\begin{pmatrix} 1&&&&&&\\ \frac{n-1}{n}&0&\frac{1}{n}&&&&\\ &\frac{n-2}{n}&0&\frac{2}{n}&&&\\ &&\ddots&\ddots&\ddots&&\\ &&&\frac{2}{n}&0&\frac{n-2}{n}&\\ &&&&\frac{1}{n}&0&\frac{n-1}{n}\\ &&&&&&1 \end{pmatrix}_{(n+1)\times(n+1)}$$

Now what is $\lim_{k\to\infty}T_n^k$?

Note that this chain doesn't have a stationary distribution because of the absorption states which make other states transient (and thus the eigenvalue 1 has multiple corresponding eigenvectors). Experiment shows that the limit has the form of $$T_n^{\infty}=(\mathbf{v,0,\cdots,0,e-v}),$$ where $\mathbf{v}$ is an eigenvector of eigenvalue 1 and can be calculated via Mathematica clause

TransitionMatrix[n_] := Module[{band = Table[k/n, {k, 0, n - 1}]},
SparseArray[{Band[{1, 2}] -> band, Band[{1, 1}] -> {1},
Band[{n + 1, n + 1}] -> {1},
Band[{2, 1}] -> Reverse[band]}]]
NonstationaryDistribution[n_] :=
#/#[[1]]&[Eigenvectors[TransitionMatrix[n]][[2]]]


and $\mathbf{e}$ is a vector of all 1's with a proper length.

Can anyone give some hints? Thank you~

-

The $j$th entry $v_j$ of the column vector $v= (v_0,v_1,\dots,v_n)^T$ is the probability that the chain hits state $0$ starting at state $j$. This is a gambler's ruin problem with unequal jump probabilities. In your case, the ruin probabilities are
$$v_j= {1\over 2^{(n-1)}}\sum_{i=j}^{n-1}{n-1\choose i}.$$

These are obtained by solving: $v_0=1$, $v_n=0$, and $$v_j=v_{j-1}{n-j\over n}+v_{j+1}{j\over n}\quad \mbox{ for }\quad 0<j<n.$$

-
Ah, thank you @Byron Schmuland, I am reading the wiki page. – ziyuang Jun 3 '11 at 15:58
@ziyuang The wiki page doesn't cover the case where there are different coins at each state. I've updated my solution to explain where the formula for $v_j$ comes from. – Byron Schmuland Jun 3 '11 at 16:34