Markov Chain and Martingale properties Suppose $X_n$ is a Markov chain (w.r.t $\mathcal{F_n}$) with transition probability $P(x,A)$, $x\in E$ and $A\in \varepsilon$. $f$: $E\to\mathbb{R}$ is a bounded measurable function. Define $Pf(x)=\int_{E}P(x,dy)f(y)$ and $$M_{n}=\sum_{k=0}^{n-1} \frac{1}{k+1}\left(P f\left(X_{k}\right)-f\left(X_{k+1}\right)\right).$$ Try to prove: 


*

*$M_n(n\geq1)$ is a martingale.

*$\sup_{n\geq1}E(M_n^2)<\infty$

*$\frac{1}{n} \sum_{k=0}^{n-1}\left(P f\left(X_{k}\right)-f\left(X_{k+1}\right)\right) \stackrel{a . s.}{\rightarrow} 0$

The first question is easy for me because $E(f(X_{n+1})|\mathcal{F_n})=\int_EP(X_n,dy)f(y)=Pf(X_n)$, so I can easily get $M_n$ is a martingale. For the second question I try to use Cauchy's Inequality: 
\begin{align}
E(M_n^2)&=E\left(\sum_{k=0}^{n-1} \frac{1}{k+1}\left(P f\left(X_{k}\right)-f\left(X_{k+1}\right)\right)\right)^2
\\&\leq \sum_{k=0}^{n-1}\frac{1}{(k+1)^2}E\left(\sum_{k=0}^{n-1}\left(P f\left(X_{k}\right)-f\left(X_{k+1}\right)\right)^2\right)
\end{align}
and then I have no idea to continue. For the third question I think if we can get $\sup_{n\geq1}E(M_n^2)<\infty$ then we can know that $M_n$ is uniformly integrable, thus we can use the convergence of martingale, but I don't know how to improve my idea. So any help is welcome!
 A: Hints:
Part (b):


*

*Show that $$\mathbb{E} \bigg[ (Pf(X_k)-f(X_{k+1})) (Pf(X_j)-f(X_{j+1})) \bigg]=0$$ for all $j \neq k$. Hint: Assume without loss of generality that $j<k$ and use the tower property to condition on $\mathcal{F}_k$.

*Deduce from Step 1 that $$\mathbb{E}(M_n^2) = \mathbb{E} \sum_{k=0}^{n-1} \frac{1}{(k+1)^2} (Pf(X_k)-f(X_{k+1}))^2.$$ Use the boundedness of $f$ to prove that the series on the right-hand side converges.


Part (c):


*

*Recall Kronecker's lemma: If $(a_i)_{i \geq 1}$ is an increasing sequence and $(x_i)_{i \geq 1}$ such that the series $\sum_{i=1}^{\infty} \frac{x_i}{a_i}$ converges, then $$\lim_{n \to \infty} \frac{1}{a_n} \sum_{i=1}^n x_i = 0.$$

*Part (a)+(b) show that $(M_n)_{n \in \mathbb{N}}$ is an $L^2$-bounded martingale. Conclude that $(M_n)_{n \in \mathbb{N}}$ is an $L^1$-bounded martingale and deduce from the martingale convergence theorem that $M_n \to M_{\infty}$ almost surely.

*Apply Kronecker's lemma to conclude that $\frac{1}{n} \sum_k (Pf(X_k)-f(X_{k+1})) \to 0$ a.s.

