Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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~

share|improve this question
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.