Why is the sum of the transition probabilities of a Markov chain less than infinity

markov chainsprobabilitystochastic-processes

Define $$f_{jj}^n = P(X_{n}=j, X_{k} \ne j, 1\le k \le n-1 | X_{0} = j)$$. So $$f_{jj}^n$$ represents the first time that the Markov chain enters state $$j$$, given that it starts from state $$j$$. The problem is the following: If $$f_{jj}^* = \sum_{n=1}^\infty f_{jj}^n < 1$$, prove that $$\sum_{n=1}^\infty P_{ij}^n < \infty$$, where $$P_{ij}^n = P(X_{n} = j | X_{0} = i)$$.

Case where states $$i$$ and $$j$$ communicate

Since $$\sum_{n=1}^\infty f_{jj}^n < 1$$, state $$j$$ is transient. Transience of state $$j$$ implies $$\sum_{n=0}^\infty P_{jj}^n < \infty$$. And we have $$P_{jj}^n = \sum_{k} P_{jk}^r P_{kj}^s$$, for any non-negative r, s satisfying $$r + s = n$$. Also note that $$\sum_{k} P_{jk}^r P_{kj}^s \ge P_{ji}^r P_{ij}^s$$, because the sum over all possible $$k$$ is greater than one of its summands. Now, taking sum over $$s$$, we have $$\sum_{s=0}^\infty P_{jj}^n = \sum_{s=0}^\infty P_{jj}^{r+s} \ge \sum_{s=0}^\infty P_{ji}^r P_{ij}^s$$.

So, since $$\sum_{n=0}^\infty P_{jj}^n < \infty$$, we must have $$\sum_{n=1}^\infty P_{ij}^n < \infty$$.

Case where state j is accessible from state i, but state i is not accessible from state j

This part is where I am stuck. In this case, we have $$P_{ji}^r = 0$$ for any $$r$$, and the proof above does not seem to work, because we can still have $$\sum_{n=1}^\infty P_{ij}^n = \infty$$. Any hints for how I should proceed from here?

Given any state $$j$$, we define a random variable $$T_j:\Omega \to \{1,2,\ldots\}\cup\{\infty\}$$ (called "the first visiting instant") by $$T_j = \begin{cases} \min\{n\geq 1: X_n =j\} & \text{if X_n=j for some n\geq 1;}\\ \infty &\text{otherwise}. \end{cases}$$ Then we have $$f_{ij}^{m} = \mathbb P\left(T_j = m \mid X_0 =i\right), \quad m\geq 1.$$ Note that $$\left\{X_m =j \text{ for some j\geq 1}\right\} =\sum_{m=1}^\infty \left\{T_j =m \right\} \quad (\text{\sum" means disjoint union}),$$ thus $$$$f_{ij}^* = \mathbb{P}\left(X_m = j \text{ for some m\geq 1}\mid X_0=i\right).\tag{1}\label{eq1}$$$$

Lemma 1. If a state $$i$$ is recurrent, then $$f_{ii}^*=1$$; moreover, if the corresponding Markov chain is "time-homogeneous", then the converse is also true.

Proof. If state $$i$$ is recurrent, then $$\mathbb{P} \left( \limsup_{n\to\infty}\{X_n=i\} \mid X_0=i\right)=1.$$ Note that \begin{align*} &\limsup_{n\to\infty}\{X_n=i\}\\ ={}& \left\{\text{there exists a strictly increasing sequence \{n_k\}_{k=1}^\infty\subset \mathbb N such that X_{n_k}=i for all k\geq 1}\right\}\\ \subset{}& \sum_{m=1}^\infty \{T_i=m\} = \left\{X_m =i \text{ for some m\geq 1}\right\}, \end{align*} so that (by eq. (\ref{eq1})) $$f_{ii}^* = \mathbb{P}\left(X_m = i \text{ for some m\geq 1}\mid X_0=i\right) \geq \mathbb{P}\left( \limsup_{n\to\infty}\{X_n=i\} \mid X_0=i\right)=1,$$ i.e., $$f_{ii}^*=1$$.

If the Markov chain is "time-homogeneous" and $$f_{ii}^*=1$$, we show that $$i$$ is recurrent. Suppose by contradiction that $$i$$ is not recurrent, then there is a integer $$N\geq 0$$ such that $$\mathbb{P} \left(X_N=i \text{, and } X_{N+\ell}\neq i \text{ for all \ell\geq 1} \mid X_0=i\right) >0 ,$$ and then from Markov property and time-homogeneity, we get \begin{align*} &\mathbb{P} \left(X_N=i \text{, and } X_{N+\ell}\neq i \text{ for all \ell\geq 1} \mid X_0=i\right)\\ = {} & \mathbb P\left( X_N= i\mid X_0 =i \right) \cdot \mathbb{P} \left( X_{N+\ell}\neq i\text{ for all \ell\geq 1}\mid X_0=i, X_N=i\right)\\ ={} &\mathbb P\left( X_N= i\mid X_0 =i \right) \cdot \mathbb{P} \left( X_{N+\ell}\neq i\text{ for all \ell\geq 1}\mid X_N=i\right) \quad (\text{Markov property})\\ ={}& \mathbb P\left( X_N= i\mid X_0 =i \right) \cdot \mathbb{P} \left( X_{\ell}\neq i\text{ for all \ell\geq 1}\mid X_0=i\right) \quad (\text{time-homogeneity})\\ > {}&0, \end{align*} that is to say, $$\mathbb P\left( X_N= i\mid X_0 =i \right) >0, \quad \mathbb{P} \left( X_{\ell}\neq i\text{ for all \ell\geq 1}\mid X_0=i\right)>0.$$ Then $$f_{ii}^* = \mathbb{P}\left(X_m =i \text{ for some m\geq 1}\mid X_0=i\right)= 1- \mathbb{P}\left(X_m \neq i\text{ for all m\geq 1}\mid X_0=i\right) <1,$$ a contradiction.

Lemma 2. $$\displaystyle p_{ij}^n= \sum_{m=1}^\infty f_{ij}^m p_{jj}^{n-m}$$ for all $$n\geq 1$$.

Proof. This follows from that \begin{align*} p_{ij}^n & = \mathbb P\left(X_n = j\mid X_0 =i\right)\\ &= \mathbb P \left(X_1=j, X_n =j \mid X_0 = i\right)+ \mathbb P \left(X_1\neq j, X_n =j \mid X_0 = i\right)\\ &= \mathbb P \left(X_1=j, X_n =j \mid X_0 = i\right)+ \mathbb P \left(X_1\neq j,X_2=j, X_n =j \mid X_0 = i\right)\\ &\qquad+ \mathbb P \left(X_1\neq j,X_2\neq j, X_n =j \mid X_0 = i\right) \\ &\cdots\\ &= \mathbb P \left(X_1=j, X_n =j \mid X_0 = i\right)+ \mathbb P \left(X_1\neq j,X_2=j, X_n =j \mid X_0 = i\right)+\cdots+\\ &\qquad \mathbb P \left(X_1\neq j,X_2\neq j,\ldots, X_{n-1} \neq j,X_n=j \mid X_0 = i\right) \\ &= \sum_{m=1}^n f_{ij}^m p_{jj}^{n-m}, \end{align*} where $$p_{jj}^0=1$$.

Lemma 3. $$\displaystyle\sum_{n=1}^\infty p_{ij}^n = f_{ij}^* \sum_{n=0}^\infty p_{jj}^n$$.

Proof. Let $$N\geq 1$$ be fixed. By Lemma 2, we get \begin{align} \sum_{n=1}^N p_{ij}^n &= \sum_{n=1}^N \sum_{m=1}^n f_{ij}^m p_{jj}^{n-m} =\sum_{m=1}^Nf_{ij}^m \sum_{n=m}^Np_{jj}^{n-m} \tag{2}\label{eq2}\\ & = \sum_{m=1}^N f_{ij}^m \sum_{n=0}^{N-m} p_{jj}^n \leq \sum_{m=1}^N f_{ij}^m \sum_{n=0}^N p_{jj}^n. \tag{3}\label{eq3} \end{align} Note that when $$m\leq \left\lfloor \frac{N}{2}\right\rfloor$$, we have $$N-m\geq N - \left\lfloor \frac{N}{2}\right\rfloor\geq \left\lfloor \frac{N}{2}\right\rfloor$$, so that it follows from eq. (\ref{eq2}) that $$$$\sum_{n=1}^N p_{ij}^n = \sum_{m=1}^Nf_{ij}^m \sum_{n=m}^Np_{jj}^{n-m} \geq \sum_{m=1}^{\left\lfloor \frac{N}{2}\right\rfloor}f_{ij}^m \sum_{n=0}^{N-m} p_{jj}^n \geq \sum_{m=1}^{\left\lfloor \frac{N}{2}\right\rfloor} f_{ij}^m \sum_{n=0}^{\left\lfloor \frac{N}{2}\right\rfloor} p_{jj}^n.\tag{4}\label{eq4}$$$$ Letting $$N\to\infty$$, eq. (\ref{eq3}) and eq. (\ref{eq4}) imply that $$$$\sum_{n=1}^\infty p_{ij}^n = f_{ij}^* \sum_{n=0}^\infty p_{jj}^n, \tag{5}\label{eq5}$$$$ which completes the proof.

Theorem 1. A state $$i$$ is recurrent if and only if $$\sum_{n=1}^\infty p_{ii}^n=\infty$$.

Proof. By Borel--Cantelli lemma, the necessity is clear. If $$\sum_{n=1}^\infty p_{ii}^n=\infty$$, we prove that $$i$$ is recurrent. By Lemma 1, we only need to prove that $$f_{ii}^*=1$$. Suppose by contradiction that $$f_{ii}^*<1$$. let $$i=j$$ in eq. (\ref{eq3}), we have $$\sum_{n=1}^N p_{ii}^n \leq \sum_{m=1}^N f_{ii}^m \sum_{n=0}^N p_{ii}^n =\sum_{m=1}^N f_{ii}^m \left( 1+\sum_{n=1}^N p_{ii}^n \right),$$ i.e., (note that $$\sum_{m=1}^N f_{ii}^m\leq f_{ii}^*<1$$ for all $$N\geq 1$$) $$\sum_{n=1}^N p_{ii}^n \leq \frac{\sum_{m=1}^N f_{ii}^m}{1-\sum_{m=1}^Nf_{ii}^m}$$ for all $$N\geq 1$$. Let $$N\to\infty$$, since $$f_{ii}^*<1$$, we have $$\sum_{n=1}^\infty p_{ii}^n \leq \frac{f_{ii}^*}{1-f_{ii}^*}<\infty,$$ a contradiction. So that $$i$$ is recurrent.

Now we turn to your question. Since $$f_{jj}^*<1$$, we deduce that $$j$$ is not recurrent (by Lemma 1). So that $$\sum_{n=1}^\infty p_{jj}^n<\infty$$ (by Theorem 1). By eq. (\ref{eq5}) and note that $$f_{ij}^*\leq 1$$, we get $$\sum_{n=1}^\infty p_{ij}^n \leq \sum_{n=0}^\infty p_{jj}^n<\infty,$$ just as we desired.