Show that $\lim_{n \rightarrow \infty} \frac{N_n(i,j)}{N_n(i)}=P_{ij}$

Question

Let $X_n$ be an irreducible finite state Markov chain with the transition matrix $P=(P_{ij})$. Set for any $i, j$ $$N_n(i)=\sum_{m=0}^{n} I_{\{X_m=i\}}$$ and similarly define: $$N_n(i,j)=\sum_{m=0}^{n} I_{\{X_m=i,X_{m+1}=j\}}$$

Show that: $\quad$ $\displaystyle{\lim_{n \rightarrow \infty} \frac{N_n(i,j)}{N_n(i)}}=P_{ij}$

I believe that we could use the fact that since the state space is finite and the Markov Chain is irreducible, the states are recurrent. Hence for large $n$, we can guarantee that $N_n(i) \neq 0$.

Now, the Markov Chain Law of Large Numbers states that: $$ \frac{N_n(i)}{n} \rightarrow \frac{1}{E_i(T_i)} \ \text{almost surely}$$

where $E_i(T_i)$ is the expected time of the first return to state $i$.

I was thinking if I can take another chain $Y_n=(X_n,X_{n+1})$ and say the same about $N_n (i,j)$ but I am doubtful about how to formulate this. Can anyone help out?

My Approach:

For any initial distribution $\pi$, we can write: $$\frac{1}{n} \sum_{m=0}^{n-1} I_{\{X_m=i\}} \rightarrow \pi_i$$.

Also using the SLLN,

$$\frac{1}{n} \sum_{m=0}^{n-1} I_{\{X_m=i, X_{m+1}=j\}} \rightarrow \pi_i.P_{ij}$$.

Taking the ratio we can say that $\frac{N_n(i,j)}{N_n(i)} \rightarrow P_{ij}$. Is this correct? Or am I missing something major?

Answer 1

This answer is just using what you found and a stupid application of the continuous mapping theorem, nothing fancy.

Observe that $\pi_i>0$ by irreducibility. You can use the fact that you mention (MCLLN and SLLN), i.e. $\frac{N_n(i)}{n}\to \pi_i$ and $\frac{N(i,j)}{n}\to \pi_i\cdot P_{i,j}$, both almost surely, and the continuous mapping theorem. Observe that the couple $(X_n,Y_n)=\left( \frac{N_n(i,j)}{n}, \frac{N_n(i)}{n} \right)$ converges almost surely to $(\pi_i\cdot P_{i,j},\pi_i)$, now the function $g:(x,y)\in[0,\infty^2[\to\frac{x}{y}$ has discontinuity set $D_g=\{ (x,0) ; x\in[0,\infty[ \}$ and since $\pi_i >0$, we have $\mathbb P[(\pi_i\cdot P_{i,j}, \pi_i)\in D_g]=0$, hence the theorem applies and $\frac{X_n}{Y_n}=g(X_n,Y_n)\to g(\pi_i\cdot P_{i,j},\pi_i) = P_{i,j}$ almost surely.