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?
Best Answer
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 \begin{equation} f_{ij}^* = \mathbb{P}\left(X_m = j \text{ for some $m\geq 1$}\mid X_0=i\right).\tag{1}\label{eq1} \end{equation}
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 \begin{equation} \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} \end{equation} Letting $N\to\infty$, eq. (\ref{eq3}) and eq. (\ref{eq4}) imply that \begin{equation} \sum_{n=1}^\infty p_{ij}^n = f_{ij}^* \sum_{n=0}^\infty p_{jj}^n, \tag{5}\label{eq5} \end{equation} 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.