Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
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
@Sasha , could you possibly take a look at what I've done? I tried calculating the stationary distribution using 2 ways, one using your method. Maybe I've done something wrong.. – Richard May 4 '12 at 13:45
@Richard: I don't know whether you can ping someone like that who has never interacted with this post. In case you don't get a response from Sasha, you may have to comment under his post instead. – joriki May 4 '12 at 14:30
@joriki Okay, thanks for your pointer! I didnt realise that. Will wait a while and see how it goes. – Richard May 4 '12 at 14:40

Your Answer


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.