# Finding the stationary distribution of a markov chain

I am asked to compute the stationary distribution of the markov chain with state space $E=\mathbb{N}_0$, $q_n >0$ for all $n \in \mathbb{N}_0$ and transition matrix below:

\begin{bmatrix} q_0 & q_1&q_2&q_3 &q_4&q_5&\dots \\ 1 & 0 & \\ & 1 & 0 & & \\ & & 1 & 0 & \\ & & & 1 & 0 & \\ & & & & 1 & 0 \\ & & & & & \ddots &\ddots \\ \end{bmatrix}

I used $\pi P = \pi$ and I also tried the way from my other thread Calculating stationary distribution of markov chain. Letting $g(x) = \sum_{k=0}^n x^k \pi_k$ What I got was:

$\pi_0 = \pi_1 +q_0\pi_0 \\ \pi_1 = \pi_2 +q_1\pi_0 \\ \pi_2 = \pi_3 +q_2\pi_0 \\ \pi_k =\pi_{k+1}+q_k\pi_0 \\ x^k\pi_k =x^k\pi_{k+1}+x^kq_k\pi_0 \\ \sum_{k=0}^{n}x^k\pi_k = \sum_{k=0}^{n}x^{k-1}\pi_{k}+\sum_{k=0}^{n}x^kq_k\pi_0 \\ g(x) =x^{-1}g(x)+\sum_{k=0}^{n}x^kq_k\pi_0$

and also

$\pi_0=\frac{1}{1-q_0}\pi_1 \\ \pi_1 =\pi_0(1-q_0) \\ \pi_2 =\pi_0(1-q_0-q_1) \\ \pi_3 =\pi_0(1-q_0-q_1-q_2) \\\pi_n = \pi_0(1-\sum_{k=0}^{n-1}q_k) \\$

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?

Edit: $\pi_n = \pi_0(1-\sum_{k=0}^{n-1}q_k) \\ \sum_{n=0}^{\infty}\pi_n =1 \\ \sum_{n=0}^{\infty}\pi_0(1-\sum_{k=0}^{n-1}q_k) =1 \\ \pi_0 = \frac{1}{\sum_{n=0}^{\infty}(1-\sum_{k=0}^{n-1}q_k)} = \frac{1}{(1-q_0)+(1-q_o-q_1)+(1-q_0-q_1-q_2)+\dots}$

Looking at @BrianMScott 's comment, how do I get the bottom line to simplify to $\sum_{k\ge 0}(k+1)q_k$? /To simplify the last line above?

-
You're almost there, you just have to find $\pi_0$. And there's one fact you haven't used yet: you want $\pi$ to be a probability distribution, so you need $\sum_{k=0}^\infty \pi_k = 1$... – Nate Eldredge May 4 '12 at 3:57
Since $\sum_{k=0}^\infty q_k = 1$, we have $\sum_{n=0}^\infty (1-\sum_{k=0}^{n-1} q_k) = \sum_{n=0}^\infty \sum_{k=n}^\infty q_k$. Now try interchanging the order of summation. – Nate Eldredge May 4 '12 at 14:07
Note that your written-out denominator starts at $n=1$; it should start at $n=0$ with a term $1$; this is where the $+1$ in Brian's $k+1$ comes from. – joriki May 4 '12 at 14:28
@Richard: Where does the $-1$ come from? As I wrote above, the $n=0$ term is $1$; the sum over $q_k$ from $k=0$ to $-1$ is $0$. By the way, pinging doesn't work if you leave a space between the @ and the user name; I read this comment by chance. – joriki May 4 '12 at 14:44
@Richard: No, that's how I'd do it. – joriki May 4 '12 at 15:33

I think you've made some errors in transferring stuff from the other question. The other question has a finite state space up to $n$, whereas your state space is infinite and $n$ in the problem statement is just a generic index, not a limit. Accordingly, the upper limits in the line with the three summation signs should be $\infty$, not $n$. Also you'd need to explain why you can lower $k$ by $1$ in the middle term; I don't think you can. This also looks like an incorrect transfer from the other question, as does your switch to $k$ as a generic index and $n$ as the upper limit of the state space in the last line.
The equations in the second block (after "and also") look OK (including the last one, where you correctly used $n$ as a generic index). As Nate wrote in a comment, you can determine $\pi_0$ by requiring that the $\pi_n$ sum up to $1$ (again summing up to $\infty$). Note that the sum of the factors on the right-hand side need not converge; although the factors go to $0$ because the sum over the $q_k$ is $1$, they could go to $0$ e.g. as $1/n$, yielding the harmonic series; in that case there would be no stationary distribution.
Specifically, if I've made no computational error, one needs $\sum_{k\ge 0}(k+1)q_k$ to converge. – Brian M. Scott May 4 '12 at 8:20
Thanks, @BrianM.Scott and joriki, I took out some paper and did some further calculations and posted what I got in my original post above, but how did you get the terms to simplify to $\sum_{k\ge 0}(k+1)q_k$? – Richard May 4 '12 at 13:44