Infinite expected return time implies return probabilities tend to zero For a Markov chain $X_n$ I want to prove that if
$$ \mathbb{E} (\min\{n \geq 1:X_n = i\}\mid X_0 = i) = \infty$$
(that is, if $i$ is transient or null recurrent), then
$$ p_{ii}^{(n)} \equiv \mathbb{P}(X_n = i \mid X_0 = i) \to 0 \quad \mathrm{as} \quad n \to \infty .$$
My intuition is that if the above expected value is infinite, then the probability that the first return to $i$ occurs at $n$ must decay relatively slowly with $n$, which means it's 'fairly likely' that the chain won't have returned to $i$ in the first $n$ steps. Hence the return probabilities are small. However, I can't turn this into a proof that they decay to zero. Please be as elementary as possible!

If $i$ is transient then the theorem is easy to prove. Transience is equivalent to the sum of the $p_{ii}^{(n)}$ being finite, which means they must tend to zero. The null recurrent case is proving more stubborn.
 A: Here is one proof that I found in Section 1.8 of James Norris' Markov Chains. It's far more sophisticated than I thought would be necessary; if anybody has a more straightforward proof to offer it would be much appreciated.
Suppose $X_n$ is null recurrent. If it is periodic with period $d$, we can consider the aperiodic subchain $X_{dn}$ and prove that return probabilities for this chain tend to zero, thereby proving that all return probabilities tend to zero. Hence assume the chain is aperiodic.
Let $T_j$ be the first return time to state $j$. We know that
$$ \infty = \sum_{k = 0}^\infty k \,\mathbb{P}_j(T_j = k) = \sum_{k = 0}^\infty \mathbb{P}_j(T_j > k) \,.$$
Given $\varepsilon > 0$ choose $K$ such that
$$ \sum_{k=0}^K \mathbb{P}_j(T_j > k) \geq \frac{1}{\varepsilon} \,.$$
Then, for $n \geq K$,
$$
\begin{align}1 &\geq \sum_{k =n-K}^n\mathbb{P}(X_k = j, X_m \neq j \;\text{for}\; m=k+1,\ldots,n) \\ 
&= \sum_{k =n-K}^n \mathbb{P}(X_k = j)\mathbb{P}_j(T_j > n - k) \\
&=\sum_{k =0}^K \mathbb{P}(X_{n-k} = j)\mathbb{P}_j(T_j > k)\,.\end{align}$$
Hence we must have $\mathbb{P}_j(X_{n-k} = j)\leq \varepsilon$ for some $k = 0,1,\ldots,K$.
Now we make a coupling argument. Let $Y_n$ be a chain with the same transition probabilities as $X_n$ and an initial distribution to be defined later. The chain $W_n = (X_n,Y_n)$ is irreducible by virtue of the aperiodicity of $X_n$. If $W_n$ is transient then by setting $X_n$ and $Y_n$ to have the same initial distribution we can easily show that return probabilities tend to zero.
So assume that $W_n$ is recurrent. But an irreducible recurrent chain explores all states with unit probability, so the two chains $X_n$ and $Y_n$ meet almost surely. Set $Z_n$ to equal $X_n$ before the two chains meet (at $n = T$, say) and $Y_n$ thereafter. Then $X_n$ and $Z_n$ have the same distribution so
$$\begin{align}|\mathbb{P}(X_n = j) - \mathbb{P}(Y_n = j)| &= |\mathbb{P}(Z_n = j) - \mathbb{P}(Y_n = j)| \\
&=|\mathbb{P}(X_n = j, n < T) - \mathbb{P}(Y_n = j, n < T)| \\
& \leq \mathbb{P}(n < T) \to 0 \,.
\end{align} $$
Hence the two chains $X_n$ and $Y_n$ have converging return probabilities. Now we just need to exploit the fact that we are free to choose the initial distribution for $Y_n$. If $X_n$ has initial distribution $\lambda$ let $Y_n$ have initial distribution $\lambda P^k$ for $k = 1,\ldots,K$, so that $\mathbb{P}(Y_n = j) = \mathbb{P}(X_{n+k} = j)$. Since the two chains have convergent probabilities, we can find $N$ such that for $n \geq N$ and $k=1,\ldots,K$,
$$ | \mathbb{P}(X_n = j) - \mathbb{P}(X_{n+k} = j)| \leq \varepsilon \,.$$
Finally, we know from before that in any interval of length $K$ there is some $k$ such that $\mathbb{P}(X_k = j) \leq \varepsilon$, and hence
$$ \mathbb{P}(X_n = j) \leq 2 \varepsilon \,.$$
Since $\varepsilon > 0$ was arbitrary we have proved the result.
A: Here is another proof taken from Chapter 3 of Karlin and Taylor's A First Course in Stochastic Processes. It is more elementary but perhaps less illuminating. Let $X_n$ be an aperiodic, null recurrent Markov chain (see other answer for reducing to the aperiodic case). Let $T_j$ be the first return time to state $j$ and define the sequences
$$a_n = \mathbb{P}_j(T_j = n) \quad \text{and} \quad u_n = p_{jj}^{(n)}\,.$$
These satisfy the equation
$$ u_n - \sum_{k=0}^{n-1}u_k \,a_{n-k}  = 0 \quad n\geq 1\tag{1}\,.$$
Now $u_n$ is a bounded sequence so $\lambda = \lim \sup u_n$ is finite, and we can find a subsequence $u_{n_j}$ that converges to $\lambda$. Since $X_n$ is aperiodic we know that $u_d > 0$ for all sufficiently large $d$, and along with null recurrence this implies $a_d > 0$ for all sufficiently large $d$. We prove that for such $d$, the sequence $u_{n_j-d}$ converges to the same limit $\lambda$.

Suppose the contrary is true. Then there exists some $\mu < \lambda$ such that $u_{n_j-d} < \mu$ for infinitely many $j$. Set $\varepsilon = a_d(\lambda-\mu)/3 > 0$. We have, by null recurrence,
$$ \sum_{n=1}^\infty a_n = 1 \quad \implies \quad \exists N \geq d\quad \text{with} \quad\sum_{n=1}^N a_n > 1 - \varepsilon \,.$$
Now let $j$ be such that $n_j \geq N$, $u_{n_j} > \lambda - \varepsilon$, $u_{n_j-d} < \mu$, and $u_n < \lambda + \varepsilon$ for all $n \geq n_j - N$. Then applying these inequalities to the recursion equation $(1)$ yields
$$ \begin{align}
u_{n_j} &<\sum_{k=0}^{n_j - N - 1} \,a_{n_j-k} + \sum_{k=n_j - N}^{n_j-1} u_k a_{n_j-k} < \varepsilon + \sum_{k=n_j - N}^{n_j-1}u_k \,a_{n_j-k} \\
&< \varepsilon + (\lambda + \varepsilon)(a_1 + \cdots a_{d-1} + a_{d+1} + \cdots + a_N) + a_d \mu \\
&<\varepsilon + (\lambda+ \varepsilon)(1- a_d) + a_d \mu <2 \varepsilon + \lambda - a_d(\lambda - \mu) = \lambda - \varepsilon \,.
\end{align}$$
But this contradicts $u_{n_j} > \lambda - \varepsilon$.

Now let $r_n = a_{n+1} + a_{n+2} + \cdots$, such that $r_0 = 1$ and $a_n = r_{n-1}-r_n$. By null recurrence we have
$$\sum_{n=0}^\infty r_n = \infty \tag{2} \,.$$
Then from equation $(1)$ we find
$$ r_0 u_n + r_1 u_{n-1} + \cdots + r_n u_0 = r_0 u_{n-1} + r_1 u_{n-2} + \cdots + r_{n-1} u_0 \,.$$
Setting the left hand side equal to $A_n$, this can be written
$A_n = A_{n-1}$, where $A_0 = r_0 u_0 = 1$. Hence for fixed $n_j \geq N \geq d$ we have
$$ r_{d} u_{n_j-d} + r_{d+1} u_{n_j-d-1}  + \cdots + r_{N} u_{n_j - N} \leq A_{n_j}= 1 \,. $$
Now taking the limit $j \to \infty$ leads to
$$ (r_d + r_{d+1} + \cdots +r_N) \lambda \leq 1 \,.$$
Finally, since $N$ is arbitrary, equation $(2)$ tells us $\lambda = 0$. Hence
$$ \lim_{n\to \infty} u_n = 0 \,.$$
A: This is more of an extended comment than an answer, but I wanted to say how the Karlin and Taylor proof can be seen as quite illuminating. The idea of looking at a "local limit" along $n_k$ is a general technique in ergodic theory. There is a way to do all the epsilon management up front that I think makes the proof clearer.
Given a sequence $n_k$, consider trying to define limiting local statistics $$p_{-d}=\lim_{\substack{k\to\infty\\ n_k\geq d}} p_{ii}^{(n_k-d)}\text{ for $d\geq 0$}$$
These limits might not converge for a general sequence $n_k$, but we can successively pass to smaller subsequences such that the limit for $d$ exists, and finally diagonalize to get a sequence where all the limits converge. In more detail: define $n^{0}_k=n_k$, and for each $d\geq 0$ pick a subsequence $n^{d+1}_k$ of $n^d_k$ such that $p_{ii}^{(n^{d+1}_k-d)}$ converges as $k\to\infty$. Then all the limits exist along the diagonal sequence $n^k_k$.
Even more abstractly, the limits can be conjured automatically from the Hahn-Banach theorem, or its other guises as the compactness theorem or ultrafilter lemma. This limit preserves some properties of the original sequences:

Lemma.
Consider a sequence of weights $w_d\geq 0$, $d\in\mathbb Z$, and assume that the limit $L=\lim_{k\to\infty}\sum_{d=0}^{\infty} w_d p_{ii}^{(n_k-d)}$ exists. Then:
  
  
*
  
*$\sum_{d=0}^\infty w_dp_{-d}\leq L$.
  
*If $\sum_{d=0}^\infty w_d$ converges then $\sum_{d=0}^\infty w_dp_{-d}=L$.
  
  
  Proof. For each $N$ the sum $\sum_{d=0}^N w_d p_{ii}^{(n_k-d)}$ is a continuous function of the $N$-tuple $(p_{ii}^{(n_k-0)},\dots,p_{ii}^{(n_k-N)})$, and the lim sup is at most $L$, so the limit is at most $L$. For the second point, note that the error term $\sum_{d=N+1}^\infty w_d p_{ii}^{(n_k-d)}$ is at most $\sum_{d=N+1}^\infty w_d$, which tends to zero as $N\to\infty$.

The Karlin and Taylor argument can be put in this setting as follows. We can find a sequence $n_k$ giving limits satisfying $p_0=\lambda>0$ and $p_{-d}\leq\lambda$ for all $d$. Then, using the above lemma, and notation from your answer:


*

*$\sum_{d=0}^\infty r_d p_{-d}\leq 1$

*$\sum_{d=1}^\infty a_d p_{-d}=\lambda$

*$p_{-d}\leq \lambda$ for each $d$ (it's a limit of values with lim sup at most $\lambda$)


The condition $\sum_{d=1}^\infty a_d p_{-d}=\lambda$ is a convex combination of the values $p_{-d}\leq\lambda$, which forces $p_{-d}=\lambda$ whenever $a_d>0$. But $\{d\mid a_d>0\}$ has bounded gaps, which means $\lambda\sum_{d:a_d>0} r_d$ diverges, contradicting $\sum_{d=0}^\infty r_d p_{-d}\leq 1$.
