# limit and stationary distribution of a Markov chain

Consider a Markov chain on the non-negative integers with transition probabilities 􏰀$$1/2$$ if $$y=x+1$$ and $$1/2$$ if $$y=0$$. Find $$\lim_{n \to \infty} P(X_{n}=0)$$.

Is this limit the same as the stationary distribution? What's the relationship between the two?

Given is the Markov Chain $$\{X_n, n\ge1\}$$, with its T.P.M described as,

$$p_{ij}^{(1)} = P(X_n = j \mid X_{n-1} = i) = \begin{cases} \frac{1}{2} & \text{if j = i + 1}\\ \frac{1}{2} & \text{if j = 0}\\ 0 & \text{otherwise} \end{cases}$$

We need to obtain the limiting distribution of the Markov Chain, i.e. $$\displaystyle \lim_{n\to\infty} p_{ij}^{(n)}$$ where $$p_{ij}^{(n)}$$ is the n-step transition probability.

Consider this,

$$p_{ij}^{(n)} = P(X_n = j \mid X_0 = i) = \displaystyle \sum_{k = 0}^{\infty}P(X_n = j \mid X_{n-1} = k).P(X_{n-1} = k \mid X_0 = i) ; j \ne 0$$

$$p_{ij}^{(n)} = \displaystyle \sum_{k = 0}^{\infty}p_{kj}^{(1)}.p_{ik}^{(n-1)} ; j \ne 0$$

But $$p_{kj}^{(1)} = \frac{1}{2}$$ if $$k = j - 1$$ and $$0$$ otherwise, so we get the following recurrence relation,

$$p_{ij}^{(n)} = \dfrac{1}{2}.p_{ij-1}^{(n-1)} ; j \ne 0$$.

Denote by $$p_{ij}$$ the limiting probability $$\displaystyle \lim_{n\to\infty}p_{ij}^{(n)}$$. Taking the limits of the above equation, we get

\begin{align} \displaystyle \lim_{n\to\infty}p_{ij}^{(n)} = \displaystyle \lim_{n\to\infty} \dfrac{1}{2}.p_{ij-1}^{(n-1)} \\ p_{ij} = \dfrac{1}{2}.p_{ij-1} = \left( \frac{1}{2}\right)^jp_{i0} \tag 1\\ \end{align}

$$\text{ where } p_{i0} = \displaystyle \lim_{n\to\infty}P(X_n = 0 \mid X_0 = i) \text{ and } j \ne 0$$

Again, $$P(X_n = 0 \mid X_0 = i) = \displaystyle \sum_{k = 0}^{\infty}P(X_n = 0 \mid X_{n-1} = k).P(X_{n-1} = k \mid X_0 = i)$$

$$p_{i0}^{(n)} = \displaystyle \sum_{k = 0}^{\infty}p_{k0}^{(1)}.p_{ik}^{(n-1)}$$

But $$p_{k0}^{(1)} = \frac{1}{2} \text{ for all } k \text{ and } \displaystyle \sum_{k = 0}^{\infty}p_{ik}^{(n-1)} = 1$$, we get $$p_{i0}^{(n)} = \frac{1}{2}$$. And thus,

$$p_{i0} = \displaystyle \lim_{n\to\infty}p_{i0}^{(n)} = \dfrac{1}{2}$$. Now putting this value in $$(1)$$, we get,

$$p_{ij} = \left(\dfrac{1}{2}\right)^{j+1}$$.

From this, we notice that the limiting probability $$p_{ij}$$ is independent of the initial state $$i$$. And thus all the rows in the corresponding TPM will be identical, making it also the stationary probabilities.