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}

What I did was use $\pi P = \pi$. And I got:

$\pi_0=\frac{1}{n}\pi_1 \Rightarrow \pi_1 =n\pi_0 \\ \pi_1 =\pi_0 +\frac{2}{n}\pi_2 \Rightarrow \pi_2 =\frac{n(n-1)}{2}\pi_0 \Rightarrow \pi_2=\frac{n-1}{2}\pi_1 \\$

I tried fiddling with it here and there but I cant seem to get anywhere to finish this problem. i.e. I can't seem to find $\pi_k$ for all $k \in E=\{0,\dots,n\}$. How would I finish this problem?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

The $\pi = P \pi$ equation, component-wise, reads: $$ \begin{eqnarray} \sum_{m=0}^n \pi_m \left(\frac{m}{n} \delta_{m,k+1} + \frac{n-m}{n} \delta_{m,k-1}\right) &=& \pi_k \\ (n-k+1) \pi_{k-1} + \pi_{k+1} (k+1) &=& n \pi_k \end{eqnarray} $$ It is easiest to solve this using probability generating function $g(x) = \sum_{k=0}^n x^k \pi_k$. Multiplying the equation with $x^k$ $$ (n-k+1) x^{k} \pi_{k-1} + x^{k} \pi_{k+1} (k+1) = n x^k \pi_k $$ and summing over $k$: $$ \begin{eqnarray} \sum_{k=1}^n (n-k+1) x^{k} \pi_{k-1} + \sum_{k=0}^{n-1} \pi_{k+1} (k+1) x^{k} &=& n \sum_{k=0}^n x^k \pi_k \\ \sum_{k=1}^{n+1} (n-k+1) x^{k} \pi_{k-1} + \sum_{k=-1}^{n-1} \pi_{k+1} (k+1) x^{k} &=& n g(x) \\ \sum_{k=0}^{n} (n-k) x^{k+1} \pi_{k} + \sum_{k=0}^{n} k x^{k-1} \pi_{k} &=& n g(x) \\ n x g(x) - x^2 g^\prime(x) + g^\prime(x) &=& n g(x) \\ (1-x^2) g^\prime(x) &=& n (1-x) g(x) \\ (1+x) g^\prime(x) &=& n g(x) \\ g(x) &=& C (1+x)^n \end{eqnarray} $$ Normalization is determined from $g(1) = 1$ requirement, since $g(x)$ is the probability generating function. Hence $$ \pi_k = \frac{1}{2^n} \binom{n}{k} $$

share|improve this answer
    
Thanks @Sasha , I understood everything you did, except how did you get from $(1+x) g^\prime(x) = n g(x) $ to $g(x) = C (1+x)^n$? –  Richard May 3 '12 at 23:37
    
@Richard Rewrite the ODE as $\frac{g^\prime(x)}{g(x)} = n \frac{1}{1+x}$. Integrating with respect to $x$ we get $\log(g(x)) = n \log(1+x) + \log(C)$. Solving, $g(x) = C (1+x)^n$. –  Sasha May 4 '12 at 0:32
    
Thanks @Sasha, most appreciated. Yeah, I think even if you said this is the most "easiest" method, it does seem quite a bit of work to compute the stationary distribution! –  Richard May 4 '12 at 2:24
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.