3
$\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}

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?

1 Answers 1

7

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} $

  • 0
    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!2012-05-04