3
$\begingroup$

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~

1 Answers 1

6

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

  • 0
    @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.2011-06-03