\section{Ergodicity and nonergodicity of a Markov chain}

\begin{assumption}
\label{assumption1}
In the sequel $\{X_n\}$ is a Markov chain with state space
$S=\{0,1,2,\ldots\}$,
$\{X_n\}$
is aperiodic and irreducible,
 and stationary transition probabilities
$\forall i,j\in S$, $P_{ij}\geq 0$.
\end{assumption}




\begin{theorem}(A sufficient condition for ergodicity \cite{pakes1969some,kaplan1979sufficient})
Assume Assumption \ref{assumption1},
 and there exist constants
$N> 0$, $B> 0$, such that
\begin{equation}
\forall i\geq 0, \sum_{j\in S}(j-i)P_{ij}<\infty,
\end{equation}
\begin{equation}
\forall i\geq N, \sum_{j\in S}(j-i)P_{ij}<-B,
\end{equation}
$\{X_n\}$ is ergodic.
\end{theorem}

请昕闻基于第一个定理完成 sutton 1998年书上 random walk 例子（书中图6.5）的遍历性证明。

\begin{theorem}(A sufficient condition for nonergodicity \cite{kaplan1979sufficient})
Assume Assumption \ref{assumption1}, if for some integer $N\geq 0$ and constants $B\geq 0$,
$c\in[0,1]$ the following two conditions hold, then
$\{X_n\}$ is not ergodic:
\begin{equation}
 \forall i\geq N, \sum_{j\in S} (j-i)P_{ij}>0, 
\end{equation}
\begin{equation}
 \forall i\geq N, \forall z\in[c,1], z^i-\sum_{j\in S}P_{ij}z^j\geq -B(1-z).
  \end{equation}
\end{theorem}

请昕闻基于第二个定理完成 sutton 1998年书上 cliff-walking task 例子（书中图6.13）的非遍历性证明。
以及圣彼得堡悖论的非遍历性证明。


\textcolor{red}{注意：证明过程应该是把Markov Chain写成N个状态（状态到底是第几个也需要明确定义），状态之间的转移概率是
一个矩阵，需要把矩阵元素明确定义出来，然后基于两个定理，明确推导出两个公式是否满足}



