Markov chain proof

Question

I am working on the following problem:

I want to show that for a Markov chain with state space $S$, $\sum_0^\infty P^n(x,y) \le \sum_0^\infty P^n(y,y)$ holds $\forall x,y \in S$. I am able to prove this for the case where $y$ is recurrent, by using the result $\sum_1^\infty P^n(x,y) = \frac{\rho_{xy}}{1-\rho_{yy}}$. However, I am having difficulties proving it for the case where $y$ is transient. It was suggested that we use the equation $P^n(x,y) = \sum_{m=1}^n P_x(T_y=m)P^{n-m}(y,y)$ (for both the recurrent and transient cases), but I am having trouble figuring out how this is useful. Thanks!!!

Answer 1

\begin{align*} \sum_{n=0}^\infty P^n(x,y)&=\sum_{n=0}^\infty \sum_{m=1}^nP_x(T_y=m)P^{n-m}(y,y)\\ &=\sum_{m=1}^\infty \sum_{n=m}^\infty P_x(T_y=m)P^{n-m}(y,y)\\ &= \sum_{m=1}^\infty P_x(T_y=m) \sum_{n=m}^\infty P^{n-m}(y,y)\\ &= \sum_{m=1}^\infty P_x(T_y=m) \sum_{n=0}^\infty P^{n}(y,y)\\ &=[1-P_x(T_y=\infty)]\sum_{n=0}^\infty P^{n}(y,y). \end{align*}