Q:

Question about positive recurrence of a Markov chain

Q) Let $\{X_n\}$ be an irreducible Markov chain on a countable set $S$. Suppose that for some $x_0$ and a non-negative function $f:S\to(0,\infty)$, there is a constant $0<\alpha<1$ s.t. 
$$\mathbb{E}_xf(X_1)\leq \alpha f(x)\text{ for all }x\neq x_0$$
Suppose also that $f(x_0)\leq f(x)$ for all $x$. Show that $\{X_n\}$ is positive recurrent.
Let $Y_n = f(X_n)/\alpha^n$ and I can show that $Y_n$ is a supermartingale using the hypothesis. But to show $X_n$ is positive recurrent, since $x_0$ is mentioned, I was thinking of the stopping time 
$$\tau = \inf\{n\geq 0:X_n = x_0\}$$
Then $Y_{n\wedge \tau}$ is also a supermartingale, $\mathbb{E}_xY_{n\wedge \tau}\leq f(x)$.
1) How can I show that $\mathbb{E}_x\tau < \infty$ which shows that $x_0$ is positive recurrent?
2) How does that show the chain is positive recurrent?

A:

You need to make use of the following theorem.
Theorem. If $X_n$ is a nonnegative supermartingale and $N \le \infty$ is a stopping time, then $EX_0 \ge EX_N$ where $X_\infty = \lim X_n$ (which exists by the martingale convergence theorem).
I will continue from where you left off. You've already proven that $E_xY_n$ is a nonnegative supermartingale, and $\tau$ is a stopping time. Hence
$$ f(x) = E_xY_0 \ge E_xY_\tau = E_x(Y_\tau;\tau=\infty) + E_x(Y_\tau;\tau<\infty)$$
$$\ge E_x(Y_\infty; \tau = \infty) = E_x(\lim_{n \rightarrow \infty}f(X_n)/\alpha^n; \tau=\infty) $$
$$ \ge E_x(\lim_{n \rightarrow \infty} f(x_0)/\alpha^n; \tau=\infty) . $$
Since $f(x_0) > 0, 0 < \alpha < 1$ and the term $f(x_0)/\alpha^n \rightarrow \infty$, it follows that $P_x(\tau = \infty) = 0$, and $P_x(\tau < \infty) = 1$ for all $x \in S$. Hence $P_x(X_n=x_0\; i.o.) =1$, and  $x_0$ is recurrent. 
Recall the chain is irreducible and $x_0$ is recurrent, hence all states $x \in S$ are recurrent (irreducibility $ \Rightarrow \rho_{x_0x} > 0$, additionally $x_0$ is recurrent $\Rightarrow \rho_{xx} = 1$ where $\rho_{xy}\equiv P_x(T_y < \infty)$).

