I am reading the proof of existence of stationary distribution in an irreducible markov chain from the book Markov Chains and Mixing Times by P. D. A. Levin, Y. Peres, E. L. Wilmer, and I have the following questions:
(1) First they are trying to prove that for any states $x,y$ of an irreducible markov chain, $E_x(T_{y}^{+})<\infty$. Here they claim that for $k>0$, $P_x(T_{y}^{+}>kr)\leq (1-\epsilon)P_x(T_{y}^{+}>(k-1)r)$and then repeated application of this inequality yields $P_x(T_{y}^{+}>kr)\leq (1-\epsilon)^k$ - how?
(2) Then I do not see how the following inequality holds: $\sum_{t\geq 0}P_x(T_{y}^{+}>t)\leq \sum_{k\geq 0}rP_x(T_{y}^{+}>kr)$. I feel I should explain what $r$ is here: from irreducibility there exists $r>0$ and $\epsilon>0$ such that $p^j(z,w)>\epsilon$ with $j\leq r$ for any states $z,w$.
(3) Final question: In the proof of the main theorem they claim : $P_z(X_t=x,X_{t+1}=y,T_{z}^{+}\geq t+1)=P_z(X_t=x,T_{z}^{+}\geq t+1)p(x,y)$, why is this true? Are they using markov property here?
Thank you so very much for your help.
For 1, we can write $$P_x(T_y^+ > kr) = \underbrace{P_x(T_y^+ > kr \mid T_y^+ > (k-1)r)}_Q P_x (T_y^+ (k-1)r).$$ We can compute $Q$ by conditioning on $X_{(k-1)r}$: $$Q = \sum_z \underbrace{P_x(T_y^+ > kr \mid X_{(k-1)r} = z, T_y^+ > (k-1)r) }_{A(z)}P_x(X_{(k-1)r} = z \mid T_y^+ > (k-1)r)$$ But $$\begin{align*}A(z) &= P_x(X_{(k-1)r} \ne y, \dots X_{kr} \ne y \mid X_0 \ne y, \dots, X_{(k-1)r} \ne y, X_{(k-1)r} = z)\\ &= P_z(X_{0} \ne y, \dots X_{r} \ne y) \quad \text{(Markov property)} \\ &\le P_z(X_r \ne y) \\ &= 1 - p^r(z,y) \\ &\le 1-\epsilon. \end{align*}$$ So $$Q \le (1-\epsilon) \underbrace{\sum_z P_x(X_{(k-1)r} = z \mid T_y^+ > (k-1)r)}_1.$$ For 2, note that for any $s \le t$ you have $P(T_y^+ > t) \le P(T_y^+ > s)$. So if $rk \le t < r(k+1)$ we have $P(T_y^+ > t) \le P(T_y^+ > rk)$. Summing gives $$\sum_{t=rk}^{r(k+1)-1} P(T_y^+ > t) \le r P(T_y^+ > rk) $$ and summing over $k$ gives the result, since now the double sum on the left ranges over all nonnegative integer values for $t$.
3 is definitely the Markov property. The way to see it will depend on exactly how the Markov property is stated in the text.