Return time estimates in countable state Markov chains

Question

Consider a countable-state Markov chain; for the sake of concreteness identify the set of states with the set of nonnegative integers {0, 1, 2, ... }. Suppose the transition probabilities $P_{ij} = \mathbb{P}(j \to i)$ are such that the chain has a stationary probability distribution $(\pi_j)$: that is, $\pi_j \geq 0$, $\sum_j \pi_j = 1$, and $\sum_j P_{ij} \pi_j = \pi_i$ for every $i$; in other words, the chain is positive recurrent.

Let $\tau_1$ denote the first return time to the state labeled 1. Suppose that we also know the extra fact that $\pi_j$ decays exponentially in $j$: that is, there are $C,\lambda>0$ such that $\pi_j \leq C e^{-\lambda j}$ for every $j$. Does it follow that the return time distribution satisfies $$ \mathbb{P}(\tau_1 > n ) \leq C' e^{-\lambda' n} $$ for some $C',\lambda'>0$?

If it makes any difference, the examples we are interested in have the property that $P_{ij}=0$ whenever $|i-j|>1$, so one can really think of them as a random walk on the nonnegative numbers, where at each step you can either go left, right, or stay where you are, and the transition probabilities depend only on your current location, but can vary from location to location.

Answer 1

Assume $p_{i(i+1)}>0$ for all $i$. For any fixed $k$, you have $\mathbb{P}(\tau_1>n)\geq p_{12}p_{23}\dots p_{(k-1)k}p_{kk}^n$ for all $n$. So if $\sup_k p_{kk}=1$, then the exponential tail bound that you want for the return time can't hold.

But you can still get exponential decay of the stationary probabilities by making $\limsup_{k\to\infty} \frac{p_{k(k+1)}}{p_{(k+1)k}}$ bounded away from $1$. (For a nearest-neighbour chain, $\frac{\pi_{k+1}}{\pi_k}=\frac{p_{k(k+1)}}{p_{(k+1)k}}$ by detailed balance.)

For example try $p_{k(k+1)}=\frac{1}{3k}$, $p_{k(k-1)}=\frac{2}{3k}$, $p_{kk}=1-\frac{1}{k}$. (With, say, $p_{01}=1$.)