Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


$$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_] := 

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

Can anyone give some hints? Thank you~

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
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

Your Answer


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.