# Markov chain proof

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!!!

• You should have used a self-study tag to avoid getting the answer straight away. – Xi'an Feb 2 '17 at 21:37