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.

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

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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
1  
@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
1  
@Richard: That would depend on instructor; I'd probably expect you to prove it. –  Brian M. Scott May 4 '12 at 19:23
1  
@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.

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

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.