<s>[INST] Calculating stationary distribution of markov chain 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?
 [/INST] 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}
$$
</s>