Finding $\lim_{n \rightarrow \infty} \mathbb{P} (X_{n} = 2 \mid X_{0} =1 ) $ and $\mathbb{E} [ s^{T} \mid X_{0} =1 ]$ for a Markov chain.

Question

I am working on Markov chains and I have problems with the following exercise. I think I have successfully solve the first two subproblems but I do not know how to solve the latter two. I include the work done, because I expect it to be informative for the last two subproblems (and maybe parts need to be used in there).

We are given the following Markov chain with state space $I= \{ 1,2,3,4,5,6 \}$ and one-step transition matrix

$ P= \begin{pmatrix} 1/2 & 1/5 & 1/10 & 0 &1/10 & 1/10 \\ 0 & 7/10 & 0 & 0 & 3/10 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1/10 & 0 & 9/10 & 0 & 0\\ 0 & 1/10 & 0 & 1/5 & 7/10 & 0\\ 3/10 & 0 & 0 & 0 & 0 & 7/10 \end{pmatrix} $

Now mind you, $p_{ij}$ represents the probability of going from state $i$ to state $j$.

a) Calculate the expected numbers of jumps to hit state 4 starting from state 2

b) Find all invariant distributions

c) Compute $\lim_{n \rightarrow \infty} \mathbb{P} (X_{n} = 2 \mid X_{0} =1 ) $

d) Let $T$ be the time when $X_{n}$ leaves states $1$ for the last time (i.e., never to return again). $T$ is undefined if state $1$ is never visited. Compute $\mathbb{E} [ s^{T} \mid X_{0} =1 ]$, for $s \in [0,1]$.

Now my work so far:

a) I define $k_{i}$ as the number of steps needed to go from state $i$ to state $4$. Then, when we start from state $2$ we find the following set of equations:

$ \begin{align} k_{2} &= 1 + \frac{7}{10} k_{2} + \frac{3}{10}k_{5}\\ k_{5} &= 1 + \frac{7}{10} k_{5} + \frac{1}{10} k_{2} + \frac{1}{5}k_{4} \end{align} $ and since $k_{4} = 0$ we can solve this and find $k_{2} = 10.$

b) I see we have two closed classes, namely $\{3\}$ and $\{2,4,5\}$. Obviously one invariant distribution is $(0,0,1,0,0,0)$, since this would keep us in state $3$. But to find the other one I made a new matrix, consisting of states $2,4,5$ from $P$ and hence defined:

$P^{*} = \begin{pmatrix} 7/10 & 0 & 3/10\\ 1/10 & 9/10 & 0\\ 1/10 & 1/5 & 7/10 \end{pmatrix}, $ since we are working with left-hand eigenvectors (or a steady state probability row vector), I find the eigenvector that corresponds with eigenvalue $1$ (which we know exists, since $P^{*}$ is irreducible) of the transpose of $P^{*}$, and I then find $(1,2,1)$ which gives me a distribution of $(\frac{1}{4}, \frac{1}{2}, \frac{1}{4})$. Hence I conclude all invariant distributions are given by $$ \pi = \alpha (0,0,1,0,0,0) + (1-\alpha) \left(0,\frac{1}{4}, 0, \frac{1}{2}, \frac{1}{4},0 \right)$$ for $\alpha \in [0,1]$

c) Now I do not know how to tackle this. I expect that I have to use the Markov property and hence condition on $X_{n-1}$ but I do not see how.

d) I expect to use a probability generating function, but I do not see how I can incorporate the idea of a stopping time with this...

Any help is much appreciated.

Answer 1

c)

Convergence to equilibrium theorem about Markov chains states that if a Markov chain has an irreducible and aperiodic transition matrix $P$ and $P$ has an invariant distribution $\pi$, then $$\lim_{n\to\infty}\mathbb{P}(X_n=j)=\pi_j$$ We want to apply this statement to answer point c). Note that the submatrix $P^*$ is aperiodic and irreducible and has the invariant distribution $\pi=(1/4,2/4,1/4)$ (it's a bit different from the one you found). Let's $T$ denote the time when the chain enters the closed class $\{2,4,5\}$. Using the above statement we get $$\lim_{n\to\infty}\mathbb{P}(X_n=2\vert T<\infty)=\pi_2=1/4$$ On the other hand, it is clear that $$\mathbb{P}(X_n=2\vert T=\infty)=0$$ Hence, we have $$\mathbb{P}(X_n=2\vert X_0=1)=\mathbb{P}(T<\infty\vert X_0=1)\mathbb{P}(X_n=2\vert T<\infty)+\mathbb{P}(T=\infty\vert X_0=1)\mathbb{P}(X_n=2\vert T=\infty)=\frac{1}{4}\mathbb{P}(T<\infty\vert X_0=1)=\frac{1}{4}\cdot\frac{3}{4}$$

d)

Note that $T$ is also the time when $X_n$ enters $A=\{2,3,4,5\}$ which is almost surely finite. Take $i\notin A$, then note that $$\mathbb{E}_i[s^T\vert X_1=j]=\begin{cases}s&\text{$j\in A$} \\ s\mathbb{E}_j[s^T]&\text{$j\notin A$}\end{cases}$$ Put $k_i:=\mathbb{E}_i[s^T]$ for $i\notin A$. We have$$k_i=\sum_{j\in I}\mathbb{P}_i(X_1=j)\,\mathbb{E}_i[s^T\vert X_1=j]=s\sum_{j\in A}p_{i,j}+s\sum_{j\notin A}p_{i,j}k_j$$ We have the system$$\begin{cases}k_1=s\frac{4}{10}+s(\frac{5}{10}k_1+\frac{1}{10}k_6)\\ k_6=s(\frac{3}{10}k_1+\frac{7}{10}k_6)\end{cases}$$The solution is $$k_1\equiv\mathbb{E}_1[s^T]=\frac{s(10-7s)}{8(5-2s)(5-4s)}$$

Answer 2

As an alternative to c) I found the following:

let $h_{i}$ be the hitting probability of state $i$ to state $\{2,4,5\}$. Then surely

$$ \lim_{n \rightarrow \infty} \mathbb{P}(X_{n} = 2 \mid X_{0} =1 ) = h_{1} \frac{1}{4},$$ where $\frac{1}{4}$ comes from part (b) (the probability of being in state $2$ once you are established in the closed class $\{2,4,5\})$. Now note $h_{2}=h_{4}=h_{5} = 1$ and $h_{3} = 0$.

Then we find $$ \begin{align} h_{1} &= \frac{1}{2} h_{1} + \frac{1}{5} h_{2} + \frac{1}{10}h_{3} +\frac{1}{10}h_{6} +\frac{1}{10}h_{5}\\ h_{1} &= \frac{1}{2}h_{1} + \frac{1}{10}h_{6} + \frac{3}{10}\\ h_{6} &= \frac{7}{10}h_{6} + \frac{3}{10}h_{1} = h_{1}, \end{align} $$ which together gives $h_{1} = \frac{3}{4}$ and thus

$$ \lim_{n \rightarrow \infty} \mathbb{P}(X_{n} = 2 \mid X_{0} =1 ) = \frac{3}{4} \frac{1}{4} = \frac{3}{16}.$$