# Finding again the stationary distribution of a markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\{0\dots,n\}$ and transition matrix below:

\begin{bmatrix} 0 & 1 \\ \frac{1}{n} & 0 & \frac{n-1}{n} \\ & \frac{2}{n} & 0 & \frac{n-2}{n} & \\ & & \ddots & \ddots & \ddots \\ & & & \frac{n-1}{n} & 0 & \frac{1}{n} \\ & & & & 1 & 0 & \\ \end{bmatrix}

I used $\pi P =\pi$ and I got:

$\pi_0=\frac{1}{n}\pi_1 \\\pi_1 = \pi_0+\frac{2}{n}\pi_2 \\ \pi_2 =\frac{n-1}{n}\pi_1 +\frac{3}{n}\pi_3 \\ \pi_3 =\frac{n-2}{n}\pi_2 +\frac{4}{n}\pi_4\\ \pi_4 =\frac{n-3}{n}\pi_3 +\frac{5}{n}\pi_5\\$

Working from there I got:

$\pi_0 = \frac{1}{n}\pi_1 \\\pi_1 =n.\pi_0 \\ \pi_2=\frac{n^2-n}{2} \pi_0 \\ \pi_3 = \frac{n^3-3n^2+2n}{6} \pi_0 \\ \pi_4 = \frac{n^4-6n^3+11n^2-6n}{24} \pi_0 \\ \sum_{k=0}^\infty \pi_k = 1$

I tried fiddling with it and spotting a pattern for $\pi_k$ but I cant see to find $\pi_k$ for all $k\in E=\{0,\dots,n\}$. How would I finish this problem?

This is a follow-up from my previous question Calculating stationary distribution of markov chain , Sasha kindly showed me a way to find the stationary distribution, and I understood that method, but I don't think i've come across that method before in my lecture. I was wondering if it was possible to compute the stationary distribution using the method I did above, but I can't seem to get to the end..

-

Write your solutions for the $\pi_k$ a little differently:

\begin{align*} \pi_1&=n\pi_0\\ \pi_2&=\frac12n(\pi_1-\pi_0)=\frac12n(n-1)\pi_0\\ \pi_3&=\frac13n\left(\pi_2-\frac{n-1}n\pi_1\right)=\frac13n\left(\frac12n(n-1)-(n-1)\right)\pi_0\\ &=\frac13n(n-1)\left(\frac12n-1\right)=\frac16n(n-1)(n-2)\\ \pi_4&=\frac14n\left(\pi_3-\frac{n-2}n\pi_2\right)\\ &=\frac14n\left(\frac16n(n-1)(n-2)-\frac{n-2}n\cdot\frac12n(n-1)\right)\pi_0\\ &=\frac14n\left(\frac16n(n-1)(n-2)-\frac12n(n-1)(n-2)\right)\pi_0\\ &=\frac1{24}n(n-1)(n-2)(n-3)\pi_0\;. \end{align*}

At this point the pattern should be pretty obvious, and the natural way to prove it is by induction.

-
Thanks @BrianM.Scott I can see the pattern now, and I guess that $\pi_n = \frac{1}{n!}\dots$, is there some other way to get the form of $\pi_n$ besides using induction or no? When you meant using induction, how would I start? Because I can't seem to get the equation for $\pi_n$ before proceeding onto the base/inductive step. – Richard May 4 '12 at 19:07
@Richard: Right, $\pi_k=\frac1{k!}\cdot\frac{n!}{n-k}!\pi_0=\binom{n}k\pi_0$. There may well be other ways; this is probably the most elementary, though. – Brian M. Scott May 4 '12 at 19:10
Thanks @BrianM.Scott, so assuming I spotted the pattern with the factorials and deduced that $\pi_k = \binom{n}k\pi_0$, is that 'acceptable'/enough to do or do I have to also prove it by induction? – Richard May 4 '12 at 19:21
@Richard: That would depend on instructor; I'd probably expect you to prove it. – Brian M. Scott May 4 '12 at 19:23
@Richard: Proving the formula for $\pi_k$ would most likely be by induction, yes. Showing that $1=\pi_0\sum_{k\ge 0}(k+1)q_k$ is then just a matter of reversing the order of a double summation. – Brian M. Scott May 4 '12 at 21:06

Thus, $\pi_1=n\pi_0$ and $\pi_2=\frac12n(n-1)\pi_0$, as you wrote, but $\pi_3$ is not what you wrote since $\pi_3=\frac16(n^3-3n^2+2n)\pi_0$. Can you see a pattern?

Hint: Find the factorization of $n^3-3n^2+2n$.

Follow-up: Since you found $\pi_3=\frac16n(n-1)(n-2)\pi_0$, factorials begin to enter the picture. So let us turn $\pi_3$ into an expression with factorials. Clearly, $n(n-1)(n-2)=\frac{n!}{(n-3)!}$ and $6=3!$ hence $\pi_3=\frac{n!}{3!(n-3)!}\pi_0$. You might also recognize this as $\pi_3={n\choose 3}\pi_0$. I am pretty sure you can take up things from here.

-
Thanks @Didier , sorry must have made an error with the $-$ and $+$ signs. I can see the pattern where $\pi_3 = \frac{1}{6}n(n-1)(n-2)\pi_0.$ How would I write it in terms of $n$ though? I can see that $\pi_n = \frac{1}{n!}\dots$ but what is the way to find the pattern? – Richard May 4 '12 at 19:04
See Edit. Two remarks: do not go too fast, I see nowhere why $\pi_n=1/n!$ should hold. And beware that $\pi_4$ in your post is still wrong. – Did May 4 '12 at 19:14
Thanks @Didier . So if I have spotted the pattern and stated that $\pi_k = \binom{n}k\pi_0$, is that sufficient/enough? Or do I have to prove it by induction before I can really use $\pi_k = \binom{n}k\pi_0$? Finally, thanks for your help again, yes I hope im capable to take it up from here, carrying on with the normalisation etc. My main problem I had in this question was finding the pattern/form for $\pi_k$. – Richard May 4 '12 at 19:23