Transition matrix exercise

Denote by $V_x = \sum_{n=0}^\infty \mathbf{1}_{\{X_n = x\}}$ the number of visits of state $x$. Then what you want to prove is $$ \mathbb{E}_y [V_x] \leq \mathbb{E}_x[V_x].$$

To do this the idea is to apply the strong Markov property at the hitting time of $x$: $$T_x = \inf\{n\geq 1\colon \, X_n = x\}.$$

First notice that on $\{T_x = \infty\}$, we have $V_x = 0$ $\mathbb{P}_y$-a.s. Then $$\begin{align} \mathbb{E}_y[V_x] &= \mathbb{E}_y[V_x \mathbf{1}_{\{T_x<\infty\}}]\\ &= \mathbb{E}_y[ \mathbf{1}_{\{T_x<\infty\}}\mathbb{E}_y[V_x|\mathcal{F}_{T_x}]]. \end{align}$$ By the strong Markov property, $\mathbb{E}_y[V_x|\mathcal{F}_{T_x}] = \mathbb{E}_x[V_x].$ This gives $$\mathbb{E}_y[V_x] = \mathbb{P}_y(T_x<\infty)\mathbb{E}_x[V_x]\leq \mathbb{E}_x[V_x].$$