1
$\begingroup$

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

2 Answers 2

1

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.

  • 0
    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$.2012-05-04
1

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.

  • 0
    @Richard: I forgot to mention that you also demonstrate the correctness of $\pi$ by verifying that $\pi P=\pi$, though proving that may also require an induction.2012-05-05