Question

5. Define a Markov Chain on S-1,2,3,..) with transition probabilities Pi i+1 (a) Is the MC irreducible? (b) Are the states positive recurrent? (c) Find the invariant distribution

Answer 1

(a)

The probability distribution matrix can be written as,

$P = \begin{bmatrix} 1/2 & 1/2 &0 & .. & 0 &.. \\ 2/3 &0 &1/3 &.. &0 &.. \\ .. & .. & .. & .. & .. &.. \\ i/i+1 &0 &0 &.. &1/i+1 &.. \\ .. & .. & .. & .. & .. & \end{bmatrix}$

We see that we can reach to state 1 from each state and from state 1, we can reach to all the states. Thus, all states can communicate to each other and the MC is irreducible.

(b)

A positive recurrent Markov chain is one where the average number of steps needed to return to a state is a finite number.

For state $\infty$, in the next transaction it can either go to state 1 or state $\infty + 1$. From state $\infty + 1$, it can reach to state $\infty$ only through state 1. Now from state 1, average number of steps needed to reach state $\infty$ is not finite (as there are infinite number of states in between). Thus, the states are not positive recurrent.

(c)

Let $\pi = [a_1, a_2, ...., a_i, a_{i+1},....]$ be the invariant distribution vector.

Then, $\pi P = \pi$

and $a_1+ a_2 + ....+ a_i + a_{i+1} + ... = 1$ ----(1)

and

$a_1/2+ 2a_2/3 + ....+ ia_i/(i+1) + ... = a_1$

$a_1/2 = a_2$$\Rightarrow a_2 = a_1/2!$

$a_2/3 = a_3$   $\Rightarrow a_3 = a_1/2*3 = a_1/3!$

.....

$a_{i-1}/i = a_{i}$   $\Rightarrow a_{i} = a_1/i!$

$a_i/(i+1) = a_{i+1}$$\Rightarrow a_{i+1} = a_1/(i+1)!$

---

From (1), and Substituting values of a2, a3, ..., ai,... we get

$a_1+ a_2 + ....+ a_i + a_{i+1} + ... = 1$

$a_1+ a_1/2! + ....+ a_i /i!+ a_{i+1}/(i+1)! + ... = 1$

$a_1(1+ 1/2! + ....+ 1 /i!+ 1/(i+1)! + ...) = 1$

$a_1(e - 1) = 1$ where e is the exponential(1)

$a_1= 1/(e - 1)$

Hence,

$\Rightarrow a_2 = 1/2!(e-1)$

..

$\Rightarrow a_{i} = a_1/i!(e-1)$

Thus, the invariant distribution is,

$\pi = [1/1!(e - 1), 1/2!(e - 1) ...., 1/i!(e - 1),....]$