\documentclass[psamsfonts]{amsart}
\usepackage{amssymb,amsfonts}
\usepackage[all,arc]{xy}
\usepackage{enumerate}
\usepackage{mathrsfs}
\usepackage{mwhite}

%theoremstyle{plain} --- default
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{quest}[thm]{Question}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{defns}[thm]{Definitions}
\newtheorem{con}[thm]{Construction}
\newtheorem{exmp}[thm]{Example}
\newtheorem{exmps}[thm]{Examples}
\newtheorem{notn}[thm]{Notation}
\newtheorem{notns}[thm]{Notations}
\newtheorem{addm}[thm]{Addendum}
\newtheorem{exer}[thm]{Exercise}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{rems}[thm]{Remarks}
\newtheorem{warn}[thm]{Warning}
\newtheorem{sch}[thm]{Scholium}

\makeatletter
\let\c@equation\c@thm
\makeatother
\numberwithin{equation}{section}

\bibliographystyle{plain}

\title{Markov Chains and the Ergodic Theorem}

\author{Chad Casarotto}

\date{AUGUST 17, 2007}

\begin{document}

\begin{abstract}

This paper will explore the basics of discrete-time Markov chains used to prove the Ergodic Theorem. Definitions and basic theorems will allow us to prove the Ergodic Theorem without any prior knowledge of Markov chains, although some knowledge about Markov chains will allow the reader better insight about the intuitions behind the provided theorems. Even for those familiar with Markov chains, the provided definitions will be important in providing the uses for the various notations used in this paper.

\end{abstract}

\maketitle

\tableofcontents

\section{Basic Definitions and Properties of Markov Chains}

Markov chains often describe the movements of a system between various states. In this paper, we will discuss \emph{discrete-time} Markov chains, meaning that at each step our system can either stay in the state it is in or change to another state. We denote the random variable $X_n$ as a sort of marker of what state our system is in at step $n$. $X_n$ can take the value of any $i \in I$, where each $i$ is a \emph{state} in the \emph{state-space}, $I$. States are usually just denoted as numbers and our state-space as a countable set.

We will call $\lam = (\lam_{i_1}, \lam_{i_2}, \ldots) = (\lam_i \, | \, i \in I)$ the \emph{probability distribution} on $X_n$ if: $\lam_i = P(X_n = i)$ and $\sum_{i \in I} \lam_i = 1$. Also, a matrix $P = \{ p_{ij} \}$, where $i,j \in I$, is called \emph{stochastic} if $\sum_{j \in I} \lam_{ij} = 1$, $\forall i \in I$, i.e. every row of the matrix is a distribution. Now we can define a Markov chain explicitly. 
\begin{defn} $(X_0, X_1, \ldots) = (X_n)_{n \geq 0}$ is a \emph{Markov chain with initial distribution $\lam$ and transition matrix $P$}, shortened to \emph{Markov$(\lam , P)$}, if
\begin{itemize}
\item $\lam$ is the probability distribution on $X_0$;
\item given that $X_n = i$, $(p_{ij} \, | \, i,j \in I)$ is the probability distribution on $X_{n+1}$ and is independent of $X_k, 0 \leq k < n$, i.e. $P(X_{N+1}=j \, | \, X_n=i) = p_{ij}$.
\end{itemize}
\end{defn}

\begin{thm} $(X_n)_{0 \leq n \leq N}$ is Markov$(\lam, P)$ if and only if 
\begin{equation} P(X_0=i_0, X_1=i_1 \ldots , X_N=i_N) = \lam_{i_0}p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{N-1}i_N}.
\end{equation}
\end{thm}
\begin{proof} First, suppose $(X_n)_{0 \leq n \leq N}$ is Markov$(\lam, P)$, thus
\[ P(X_0=i_0,X_1=i_1, \ldots , X_N=i_N) \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\]
\[ \qquad \quad = P(X_0=i_0)P(X_1=i_1 \, | \, X_0=i_0) \cdots P(X_N=i_N\, | \, X_0=i_0, \ldots, X_{N-1}=i_{N-1})\]
\[ \! = P(X_0=i_0)P(X_1=i_1 \, | \, X_0=i_0) \cdots P(X_N=i_N\, | \, X_{N-1}=i_{N-1})\quad\]
\[\!\!\!\!\!\! = \lam_{i_0}p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{N-1}i_N} \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\]
Now assume that (1.3) holds for N, thus
\[P(X_0=i_0, X_1=i_1 \ldots , X_N=i_N) = \lam_{i_0}p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{N-1}i_N} \]
\[\sum_{i_N \in I} P(X_0=i_0, X_1=i_1 \ldots , X_N=i_N) = \sum_{i_N \in I} \lam_{i_0}p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{N-1}i_N} \]
\[\!P(X_0=i_0, X_1=i_1 \ldots , X_{N-1}=i_{N-1}) = \lam_{i_0}p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{N-2}i_{N-1}} \quad\]
And now by induction, (1.3) holds for all $0 \leq n \leq N$. From the formula for conditional probability, namely that $P(A\,|\,B)=P(A \cap B)/P(B)$, we can show that
\[P(X_{N+1}=i_{N+1}\, | \, X_0=i_0, \ldots, X_N=i_N) = \frac{P(X_0=i_0, \ldots ,  X_N=i_N, X_{N+1}=i_{N+1})}{P(X_0=i_0, \ldots , X_N=i_N)} \]
\[\qquad\qquad\qquad\qquad\qquad\qquad\quad\! = \frac{\lam_{i_0}p_{i_0i_1}\cdots p_{i_{N-1}i_N}p_{i_Ni_{N+1}}}{\lam_{i_0}p_{i_0i_1}\cdots p_{i_{N-1}i_N}} \]
\[ \qquad\qquad\quad \! \! \! = p_{i_Ni_{N+1}} \]
Thus, by definition, $(X_n)_{0 \leq n \leq N}$ is Markov$(\lam, P)$.
\end{proof}

The next theorem emphasizes the memorylessness of Markov chains. In the formulation of this theorem, we use the idea of the \emph{unit mass at} $i$. It is denoted as $\delta_i = (\delta_{ij})$ where
\[\delta_{ij} = \left\{ \begin{array}{ll} 
1 & \textrm{if $i=j$}\\ 
0 & \textrm{otherwise}
\end{array} \right. \]

\begin{thm} Let $(X_n)_{n \geq 0}$ be Markov$(\lam,P)$. Then, given that $X_m = i$, $(X_l)_{l \geq m}$ is Markov$(\delta_i,P)$ and is independent of $X_k, \: 0 \leq k < m$.
\end{thm}
\begin{proof} Let the event $A=\{X_m=i_m, \ldots, X_n=i_n\}$ and the event $B$ be any event determined by $X_0, \ldots, X_m$. To prove the theorem, we must show that 
\[P(A \cap B \, | \, X_m=i) = \delta_{ii_m}p_{i_mi_{m+1}}\cdots p_{i_{n-1}i_n}P(B\, | \, X_m=i)\]
 thus the result follows from Theorem 1.2. First, let us consider any elementary event 
\[ B=B_k=\{X_0=i_0, \ldots, X_m=i_m\}\]
Here we show that 
\[ P(A \cap B_k \: \textrm{and} \: i=i_m \,|\, X_m=i) = \frac{\delta_{ii_m}p_{i_mi_{m+1}}\cdots p_{i_{n-1}i_n}P(B_k)}{P(X_m=i)}\]
which follows from Theorem 1.2 and the definition of conditional probability. Any event, $B$, determined by $X_0, \ldots, X_m$ can be written as a disjoint union of elementary events, $B=\bigcup_{k=1}^{\infty} B_k$. Thus, we can prove our above identity by summing up all of the different $B_k$ for any given event.
\end{proof}

An additional idea that is going to be important later is the idea of conditioning on the initial state, $X_0$. We will let $P(A\,|\,X_0=i) = P_i(A)$. Similarly, we will let $E(A\,|\,X_0=i)=E_i(A)$.

\section{Stopping Times and the Strong Markov Property}

We start this section with the definition of a stopping time.
\begin{defn} A random variable $T$ is called a \emph{stopping time} if the event $\{T=n\}$ depends only on $X_0, \ldots, X_n$ for $n=0,1,2,\ldots$.
\end{defn}

An example of a stopping time would be the \emph{first passage time} 
\[ T_i = \inf \{n \geq 1 \, | \, X_n=i\}.\]
where we define $\inf \emptyset = \infty$. This is a stopping time since $\{T_i = n\} = \{ X_k \neq i , \\X_n=i \, | \, 0 < k < n\}$. Now we will define an expansion of this idea that we will use later.
\begin{defn} The \emph{rth passage time} $T_i^{(r)}$ to state $i$ is defined recursively using the first passage time.
\[T_i^{(0)}=0, \qquad T_i^{(1)}=T_i \]
and, for $r=1,2,\ldots$,
\[T_i^{(r+1)}=\inf\{n\geq T_i^{(r)}+1\,|\,X_n=i\}.\]
\end{defn} 
This leads to the natural definition of the \emph{length of the rth excursion} to $i$ as
\[ S_i^{(r)}= \left\{ \begin{array}{ll} 
T_i^{(r)}-T_i^{(r-1)} & \textrm{if}\:\:T_i^{(r-1)}<\infty\\ 
0 & \textrm{otherwise.}
\end{array} \right. \]
The following theorem shows how the Markov property holds at stopping times.

\begin{thm} Let $T$ be a stopping time of $(X_n)_{n \geq 0}$ which is Markov$(\lam,P)$. Then given $T < \infty$ and $X_T=i$, $(X_l)_{l \geq T}$ is Markov$(\delta_i,P)$ and independent of $X_k, \\0 \leq k < T$.
\end{thm}
\begin{proof} First, we already have that $(X_l)_{l \geq T}$ is Markov$(\delta_i,P)$ by Theorem 1.4, so we just need to show the independence condition. Let the event $A=\{X_T=i_0, \ldots, X_{T+n}=i_n\}$ and the event $B$ be any event determined by $X_0, \ldots, X_T$. It is important to notice that the event $B \cap \{T=m\}$ is determined by $X_0, \ldots, X_m$. We get that
\[P(A \cap B \cap \{T=m\} \cap \{X_T=i\})= P_i(X_0=i_0, \ldots, X_n=i_n)P(B \cap \{T=m\} \cap \{X_T=i\})\]
If we now sum over $m=0,1,2,\ldots$ and divide each side by $P(T<\infty,X_T=i)$ using the definition of conditional probability, we obtain
\[P(A\cap B \,|\,T<\infty,X_T=i)=P_i(X_0=i_0, \ldots, X_n=i_n)P(B\,|\,T<\infty,X_T=i)\]
which gives us the independence we desired.
\end{proof}

\section{Recurrence and Transience}
\begin{defn} Let $(X_n)_{n \geq 0}$ be Markov with transition matrix $P$. We say that a state $i$ is \emph{recurrent} if
\[P_i(X_n = i\: \textrm{for infinitely many}\: n)=1,\]
and we say that a state $i$ is \emph{transient} if
\[P_i(X_n = i\: \textrm{for infinitely many}\: n)=0.\]
\end{defn}
The following results allow us to show that any state is necessarily either recurrent or transient.

\begin{lem} For $r=2,3,\ldots$, given that $T_i^{(r-1)} < \infty, \:\,S_i^{(r)}$ is independent of $X_k, \: 0 \leq k \leq T_i^{(r-1)}$ and
\[P(S_i^{(r)}=n\,|\,T_i^{(r-1)} < \infty)=P_i(T_i=n).\]
\end{lem}
\begin{proof} We can directly apply Theorem 2.3 where $T_i^{(r-1)}$ is the stopping time $T$, since it is assured that $X_T=i$ when $T < \infty$. So, given that $T_i^{(r-1)} <  \infty, \:\,(X_l)_{ l\geq T}$ is Markov$(\delta_i,P)$ and independent of $X_k,\: 0 \leq k < T$, the independence wanted. Yet, we know
\[S_i^{(r)}=\inf\{l-T \geq 1\,|\,X_l=i\}\]
so $S_i^{(r)}$ is the first passage time of $(X_l)_{ l\geq T}$ to state $i$, giving us our desired equality.
\end{proof}

\begin{defn} The idea of the \emph{number of visits to i}, $V_i$, is intuitive and can be easily defined using the indicator function
\[V_i=\sum_{n=0}^{\infty}1_{\{X_n=i\}}\]
\end{defn}
A nice property of $V_i$ is that
\[E_i(V_i)=E_i \Big( \sum_{n=0}^{\infty}1_{\{X_n=i\}} \Big)=\sum_{n=0}^{\infty}E_i(1_{\{X_n=i\}})=\sum_{n=0}^{\infty}P_i(X_n=i).\]
\begin{defn} Another intuitive and useful term is the \emph{return probability to i}, defined as
\[f_i=P_i(T_i<\infty).\]
\end{defn}

\begin{lem} $P_i(V_i>r)=(f_i)^r$ for $r=0,1,2,\ldots.$
\end{lem}
\begin{proof} First, we know that our claim is necessarily true when $r=0$. Thus, we can use induction and the fact that if $X_0=i$ then $\{V_i>r\}=\{T_i^{(r)}<\infty\}$ to conclude that
\[P_i(V_i>r+1)=P_i(T_i^{(r+1)}<\infty) \qquad\qquad\qquad\qquad\]
\[\qquad\qquad\;\;\,=P_i(T_i^{(r)}<\infty \; \textrm{and} \; S_i^{(r+1)}<\infty)\]
\[\qquad\qquad\qquad\qquad\;\;\;\:=P_i(S_i^{(r+1)}<\infty\,|\,T_i^{(r)}<\infty)P_i(T_i^{(r)}<\infty)\]
\[\!\!\!=f_i\cdot(f_i)^r=(f_i)^{r+1}\]
using Lemma 3.2, so our claim is true for all $r$.
\end{proof}

\begin{thm} The following two cases hold and show that any state is either recurrent or transient:
\begin{enumerate}
\item if $P_i(T_i<\infty)=1$, then $i$ is recurrent and $\sum_{n=0}^{\infty}P_i(X_n=i)=\infty$;
\item if $P_i(T_i<\infty)<1$, then $i$ is transient and $\sum_{n=0}^{\infty}P_i(X_n=i)<\infty$.
\end{enumerate}
\end{thm}
\begin{proof} If $P_i(T_i<\infty)=f_i=1$ by Lemma 3.5, then
\[P_i(V_i=\infty)=\lim_{r \to \infty} P_i(V_i>r) = \lim_{r \to \infty} 1^r = 1 \]
so $i$ is recurrent and
\[\sum_{n=0}^{\infty}P_i(X_n=i)=E_i(V_i)=\infty.\]
In the other case, $f_i=P_i(T_i<\infty)<1$ then using our fact about $V_i$
\[\sum_{n=0}^{\infty}P_i(X_n=i)=E_i(V_i)=\sum_{n=1}^{\infty}nP_i(V_i=n)=\sum_{n=1}^{\infty}\sum_{r=0}^{n-1}P_i(V_i=n)\qquad\qquad\qquad\qquad\]
\[\qquad\qquad\qquad=\sum_{r=0}^{\infty}\sum_{n=r+1}^{\infty}P_i(V_i=n)=\sum_{r=0}^{\infty}P_i(V_i>r)=\sum_{r=0}^{\infty}(f_i)^r=\frac{1}{1-f_i}<\infty\]
so $P_i(V_i=\infty)=0$ and $i$ is transient.
\end{proof}

\section{Communication Classes and Recurrence}

\begin{defn} State $i$ \emph{can send to} state $j$, and we write $i \to j$ if
\[P_i(X_n=j \; \textrm{for some} \; n\geq0)>0.\]
Also $i$ \emph{communicates with} $j$, and we write $i \lr j$ if both $i \to j$ and $j \to i$.
\end{defn}

\begin{thm} For distinct states $i, j \in I$, $i \to j \iff p_{ii_1}p_{i_1i_2}\cdots p_{i_{n-1}j}>0$ for some states $i_1,i_2,\ldots,i_{n-1}$. Also, $\lr$ is an equivalence relation on $I$.
\end{thm}
\begin{proof} $(\limp)$
\[0<P_i(X_n=j \; \textrm{for some} \; n\geq0)\leq \sum_{n=0}^{\infty}P_i(X_n=j)= \sum_{n=0}^{\infty}\sum_{i_1,\ldots,i_{n-1}}p_{ii_1}p_{i_1i_2}\cdots p_{i_{n-1}j}\]
Thus, for some $p_{ii_1}p_{i_1i_2}\cdots p_{i_{n-1}j}>0$ for some states $i_1,i_2,\ldots,i_{n-1}$.\\
$(\pmil)$ Take some $i_1,i_2,\ldots,i_{n-1}$ such that 
\[0<p_{ii_1}p_{i_1i_2}\cdots p_{i_{n-1}j}\leq P_i(X_n=j)\leq P_i(X_n=j \; \textrm{for some} \; n\geq0).\]
Now it is clear from the proven inequality that $i \to j, j \to k \limp i \to k$. Also, it is true that $i \lr i$ for any state $i$ and that $i \lr j \limp j \lr i$. Thus, $\lr$ is an equivalence relation on $I$.
\end{proof}
\begin{defn} We say that $\lr$ partitions $I$ into \emph{communication classes}. Also, a Markov chain or transition matrix $P$ where $I$ is a single communication class is called \emph{irreducible}.
\end{defn}

\begin{thm} Let $C$ be a communication class. Either all states in $C$ are recurrent or all are transient.
\end{thm}

\begin{proof} Take any distinct pair of states $i,j \in C$ and suppose that $i$ is transient. Then there exist $n,m\geq0$ such that $P_i(X_n=j)>0$ and $P_j(X_m=i)>0$, and for all $r\geq0$
\[P_i(X_{n+r+m}=i) \geq P_i(X_n=j)P_j(X_r=j)P_j(X_m=i).\]
This implies that
\[\sum_{r=0}^{\infty}P_j(X_r=j)\leq \frac{1}{P_i(X_n=j)P_j(X_m=i)}\sum_{r=0}^{\infty}P_i(X_{n+r+m}=i)<\infty \]
by Theorem 3.6. So any arbitrary $j$ is transient, again by Theorem 3.6, so the whole of $C$ is transient. The only way for this not to be true is if all states in $C$ are recurrent.
\end{proof}
This theorem shows us that recurrence and transience is a class property, and we will refer to it in the future as such.

\begin{thm} Suppose $P$ is irreducible and recurrent. Then for all $i \in I$ we have $P(T_i<\infty)=1$.
\end{thm}
\begin{proof} By Theorem 2.3 we have
\[P(T_i<\infty)=\sum_{j\in I}P_j(T_i<\infty)P(X_0=j)\]
so we only need to show $P_j(T_i<\infty)=1$ for all $j \in I$. By the irreducibility of $P$, we can pick an $m$ such that $P_i(X_m=j)>0$. From Theorem 3.6, we have
\[\!\!\!\!\!\!\!1=P_i(X_n=i \; \textrm{for infinitely many} \; n)\qquad\qquad\qquad\qquad\qquad\]
\[\!\!\!\!\!\!=P_i(X_n=i \; \textrm{for some} \; n\geq m+1)\qquad\qquad\qquad\qquad\qquad\]
\[=\sum_{k \in I} P_i(X_n=i \; \textrm{for some} \; n\geq m+1\,|\, X_m=k)P_i(X_m=k)\]
\[\!\!\!\!\,=\sum_{k \in I} P_k(T_i<\infty)P_i(X_m=k)\qquad\qquad\qquad\qquad\qquad\qquad\]
using Theorem 2.3 again. Since $\sum_{k \in I} P_i(X_m=k)=1$ so we have that \\$P_j(T_i<\infty)=1$.
\end{proof}

\section{The Strong Law of Large Numbers and the Ergodic Theorem}
The Strong Law of Large Numbers will be presented here without proof although an elementary proof needing much more background can be found in the journal \emph{Wahrscheinlichketstheorie} by N. Etemadi (1981).
\begin{thm}[Strong Law of Large Numbers] Let $Y_1,Y_2,\ldots$ be a sequence of independent, identically distributed, non-negative, random variables where\\ $E(Y_k)=\mu$. Then
\[P\bigg(\frac{Y_1+\ldots+Y_n}{n} \to \mu \; \textrm{as} \; n \to \infty \bigg) = 1\]
\end{thm}

\begin{defn} We will expand on the idea of $V_i$ by defining
\[V_i(n)=\sum_{k=0}^{n-1}1_{\{X_k=i\}},\]
representing the number of visits to $i$ before step $n$.
\end{defn}

The Ergodic theorem examines the long-run value of the ratio ${V_i(n)}/{n}$, which is the proportion of time spent in state $i$ before step $n$.

\begin{thm}[Ergodic Theorem] Let $P$ be irreducible and let $\lam$ be any distribution. If $(X_n)_{0 \leq n \leq N}$ is Markov$(\lam, P)$ then
\[P\bigg(\frac{V_i(n)}{n} \to \frac{1}{m_i} \;\textrm{as}\; n \to \infty \bigg) = 1\]
where $m_i = E_i(T_i)$, i.e. the expected return time to state $i$.
\end{thm}

\begin{proof}
First, we will consider the case where P is transient. We then know that with probability 1, $V_i < \infty$, so
\[\frac{V_i(n)}{n} \leq \frac{V_i}{n} \to 0 = \frac{1}{m_i}. \]
Now, we will consider the case that P is recurrent, and we will fix a state $i$. Let $T=T_i$, and we have $P_i(T<\infty)=1$ by Theorem 3.6 and $(X_l)_{l \geq T}$ is Markov$(\delta_i,P)$ and independent of $X_k, \:0 \leq k < T$ by Theorem 2.3. Since the long-run proportion of time spent in state $i$ is the same for $(X_l)_{l \geq T}$ as for $(X_n)_{n \geq 0}$, we need to only consider the case where $\lam = \delta_i.$

By Lemma 3.2, we know that the non-negative, random variables $S_i^{(1)}\!,S_i^{(2)}\!,\ldots$ are independent and identically distributed with $E_i(S_i^{(r)})=E_i(T_i)=m_i.$ We know
\[T_i^{(V_i(n)-1)}=S_i^{(1)}+\ldots+S_i^{(V_i(n)-1)}\leq n-1,\]
where the left-hand side of the inequality is the step of the last visit to $i$ before step $n$. In addition,
\[T_i^{(V_i(n))}=S_i^{(1)}+\ldots+S_i^{(V_i(n))}\geq n,\]
where the left-hand side of the inequality is the step of the first visit to $i$ after step $n-1$. So we can squeeze the value of ${n}/{V_i(n)}$ using the following inequality:
\begin{equation} \frac{S_i^{(1)}+\ldots+S_i^{(V_i(n)-1)}}{(V_i(n))} \leq \frac{n}{V_i(n)} \leq \frac{S_i^{(1)}+\ldots+S_i^{(V_i(n))}}{(V_i(n))}
\end{equation}
Now we can use the Strong Law of Large Numbers to get
\[P\Bigg(\frac{S_i^{(1)}+\ldots+S_i^{(n)}}{n} \to m_i  \;\textrm{as}\; n \to \infty \Bigg) = 1,\]
and since $P$ is recurrent,
\[P(V_i(n) \to \infty \;\textrm{as}\; n \to \infty)=1.\]
Thus, if we let $n \to \infty$ in (5.4), we get
\[P\bigg(\frac{n}{V_i(n)} \to m_i  \;\textrm{as}\; n \to \infty \bigg) = 1,\]
which implies that
\[P\bigg(\frac{V_i(n)}{n} \to \frac{1}{m_i}  \;\textrm{as}\; n \to \infty \bigg) = 1,\]
\end{proof}




\begin{thebibliography}{9}

\bibitem{Norris}
Norris, James R.
\emph{Markov Chains}.
University of Cambridge Press.
1998.

\end{thebibliography}

\end{document}

