Prove the "high recurrence probability" of the Markov chain.

35 Views Asked by At

Let $p(x, y)$ be the (one-step) transition function of a Markov chain on a discrete state space $S$ and $p_n(x, y)$ be the $n$-step transition function. Show that for any positive integers $L$ and $N$ and any two states $x$ and $y$ we have $$\sum_{n=L}^{N+L}p_n(x,y)\le\sum_{n=0}^{N}p_n(y,y).$$$$$$ My intuition for this problem is counting how many steps the chain starting from $x$ to be at $y$ the chain needs to spend time to reach $y$ first, but this inequality shows that the probability for a recurrence in a Markov chain is "some what larger" than the probability for other cases, and I don't know how to handle this intuition because I don't know much about Markov inequalities. Also transforming this problem into a Matrix problem is not helping in my opinion, since it seemingly involves very large computation and I don't know what to deal with it. What could possible be the ways of continuing this problem? Thanks!