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