Finding the stationary distribution for this Discrete Time Markov Chain (DTMC)

Question

I have the following discrete-time Markov chain defined on the state space $S:=\{0,1,2,\ldots\}$: $$p(i,j) = \begin{cases} 1, \quad &\text{if $i=0$ and $j=1$}\\ \frac{1}{2}, \quad &\text{if $j=i-1$ and $i=1,2,\ldots$}\\ \frac{i-1}{2(i+1)}, \quad &\text{if $j=i$ and $i=1,2,\ldots$}\\ \frac{1}{i+1}, \quad &\text{if $j=i+1$ and $i=1,2,\ldots$}\\ 0, \quad &\text{otherwise} \end{cases}$$

In other words, $$P = \begin{bmatrix} 0&1\\ 1/2 & 0 &1/2\\ & 1/2& 1/(2*3)&1/3\\ &&1/2&2/(2*4)&1/4\\ &&&1/2&3/(2*5)&1/5\\ &&&\ddots&\ddots&\ddots \end{bmatrix}$$

I'm asked to find the stationary distribution for this Markov chain. I know that solving $\pi=\pi P$ along with $\sum_{i=0}^\infty \pi_i=1$ for $\pi$ will get me the stationary distribution, but every time I try to compute this, I get stuck. Specifically, I have

• $\pi_0 = 1/2*\pi_1$
• $\pi_n = \pi_{n-1}\left(\frac{1}{n}\right) + \pi_n\left(\frac{n-1}{2(n+1)}\right)+ \pi_{n+1}\left(\frac{1}{2}\right)\quad$ for $n \ge 1$

I just don't know where to go from here. Any help would be outstanding. Is there any alternative way to compute stationary distributions other than solving the system $\{\pi = \pi P, \quad \sum_{i=0}^\infty \pi_i = 1\}$?

Answer 1

This looks like a modified Birth-Death Chain which should say "reversible" to you. Reversible chains only require solving the detailed balance equations, which in general is a lot easier than solving the global balance equations.

so you need to solve
$\pi_i P_{i,j} = \pi_j P_{j,i}$

for the top left corner (i.e. for states 0 and 1) you have
$\pi_0 1 = \pi_1 \frac{1}{2}$

now consider natural number $n \geq 2$, the detailed balance equations give
$\pi_{n-1}\frac{1}{n} =\pi_n\frac{1}{2}$
or
$\pi_{n-1}\frac{2}{n} =\pi_n$

at this point you can try applying this for small values of $n$ and form a guess:
$\pi_{1}\frac{1}{2}\cdot\frac{2^{n}}{n!} = \pi_{1}\frac{2^{n-1}}{n!} =\pi_n$
(note this technically actually nolds for the case of n=1 and n=0 as well)

for n = 2 this reads
$\pi_{1}\frac{2}{2!}= \pi_1 =\pi_2$ which is equivalent to previously stated $\pi_{n-1}\frac{2}{n} =\pi_n$ when n = 2. This is our base case.

now for $n\geq 3$
$\pi_{1}\frac{2^{n-1}}{n!} = \big(\pi_{1}\frac{2^{n-2}}{(n-1)!}\big)\frac{2}{n} =\big(\pi_{n-1}\big)\frac{2}{n} =\pi_n$

where the middle inequality follows by induction hypothesis.

The final thing is, for a positive recurrent chain with one communicating class, the $\pi_i$'s must all sum to one, so

$1 = \sum_{n=0}^\infty \pi_n = \sum_{n=0}^\infty \pi_1\frac{1}{2}\frac{2^{n}}{n!}= \pi_1\frac{1}{2}\big(\sum_{n=0}^\infty \frac{2^{n}}{n!}\big)= \pi_1 \frac{1}{2} e^2 $

so $\pi_1 = \frac{2}{e^2}$
and $\pi_n =\frac{2}{e^2}\frac{2^{n-1}}{n!}=\frac{2^{n}}{n!e^2}$

Answer 2

This is a birth-death process and so has an invariant measure given by $\nu(1)=1$ and $$\nu(n) = \prod_{j=0}^{n-1}\frac{p_j}{q_{j+1}},$$ where $p_j=\mathbb P(X_{n+1}=j+1\mid X_n=j)$ and $q_j = \mathbb P(X_{n+1}=j-1\mid X_n=j)$. (I leave it to the reader to check that this is an invariant measure.) So the process has a stationary distribution if and only if $\nu$ is summable, that is, $$ \sum_{n=0}^\infty\prod_{j=0}^{n-1}\frac{p_j}{q_{j+1}}<\infty. $$ If this sum is finite with value $C$, define $\pi = \frac1C\nu$. Then $\pi$ is a stationary distribution for the Markov chain.