In Levin and Peres' Markov Chains and Mixing Times, lemma 1.13 states:
For any states $x$ and $y$ of an irreducible chain, $E_x(\tau^+_y)<\infty$ where $\tau^+_x := \min\{t \geq 1 : X_t = x\}$.
The proof in the text is:
The definition of irreducibility implies that there exist an integer $r > 0$
and a real $\epsilon > 0$ with the following property: for any states $z, w \in \mathcal{X}$ , there exists a $j \leq r$ with $P^j(z, w) >\epsilon$. Thus for any value of $X_t$ , the probability of hitting state $y$ at a time between $t$ and $t + r$ is at least $\epsilon$. Hence for $k > 0$ we have (1.17):
\begin{equation}
P_x\{\tau^+_y > kr\} ≤ (1 − \epsilon)P_x\left\{\tau^+_y > (k-1)r\right\}
\end{equation}
Repeated application of (1.17) yields:
$$P_x\{\tau^+_y > kr\} \leq (1 − \epsilon)^k$$
Lastly:
$$E_x(\tau^+_y) =\sum_{t\geq0}P_x\{\tau^+_y > t\} ≤\sum_{k\geq0}rP_x\{\tau^+_y> kr\}≤ r(1 − \epsilon)^k <\infty.$$
How do we prove (1.17)?. It seems induction is the way to go. (1.17) holds when $k=1$ but showing that (1.17) holds for $k+1$ if it holds for $k$ is more complicated. Also in the last sentence of the proof, why is the first inequality true?
Best Answer
The first inequality is using two observations:
In symbols, we write $P_x(\tau_y^+>kr)=P_x(\tau_y^+>kr \mid \tau_y^+>(k-1)r) P_x(\tau_y^+>(k-1)r)$. We get the first inequality by noticing that the first factor is less than $1-\epsilon$, and then we continue recursively, picking up another factor of $1-\epsilon$ each time.
The second inequality is just replacing $\{ \tau_y^+>t \}$ with $\{ \tau_y^+>r\lfloor t/r \rfloor \}$ and the latter is a superset of the former.