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?
Best Answer
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} $$