Harris chain

Let ${\displaystyle \{X_{n}\}}$ be a Markov chain on a general state space ${\displaystyle \Omega }$ with stochastic kernel ${\displaystyle K}$. The kernel represents a generalized one-step transition probability law, so that ${\displaystyle P(X_{n+1}\in C\mid X_{n}=x)=K(x,C)}$ for all states ${\displaystyle x}$ in ${\displaystyle \Omega }$ and all measurable sets ${\displaystyle C\subseteq \Omega }$. The chain ${\displaystyle \{X_{n}\}}$ is a Harris chain[2] if there exists ${\displaystyle A\subseteq \Omega ,\varepsilon >0}$, and probability measure ${\displaystyle \rho }$ with ${\displaystyle \rho (\Omega )=1}$ such that

1. If ${\displaystyle \tau _{A}:=\inf\{n\geq 0:X_{n}\in A\}}$, then ${\displaystyle P(\tau _{A}<\infty \mid X_{0}=x)=1}$ for all ${\displaystyle x\in \Omega }$.
2. If ${\displaystyle x\in A}$ and ${\displaystyle C\subseteq \Omega }$ (where ${\displaystyle C}$ is measurable), then ${\displaystyle K(x,C)\geq \varepsilon \rho (C)}$.

The first part of the definition ensures that the chain returns to some state within ${\displaystyle A}$ with probability 1, regardless of where it starts. It follows that it visits state ${\displaystyle A}$ infinitely often (with probability 1). The second part implies that once the Markov chain is in state ${\displaystyle A}$, its next-state can be generated with the help of an independent Bernoulli coin flip. To see this, first note that the parameter ${\displaystyle \varepsilon }$ must be between 0 and 1 (this can be shown by applying the second part of the definition to the set ${\displaystyle C=\Omega }$). Now let ${\displaystyle x}$ be a point in ${\displaystyle A}$ and suppose ${\displaystyle X_{n}=x}$. To choose the next state ${\displaystyle X_{n+1}}$, independently flip a biased coin with success probability ${\displaystyle \varepsilon }$. If the coin flip is successful, choose the next state ${\displaystyle X_{n+1}\in \Omega }$ according to the probability measure ${\displaystyle \rho }$. Else (and if ${\displaystyle \varepsilon <1}$), choose the next state ${\displaystyle X_{n+1}}$ according to the measure ${\displaystyle P(X_{n+1}\in C\mid X_{n}=x)=(K(x,C)-\varepsilon \rho (C))/(1-\varepsilon )}$ (defined for all measurable subsets ${\displaystyle C\subseteq \Omega }$).

Two random processes ${\displaystyle \{X_{n}\}}$ and ${\displaystyle \{Y_{n}\}}$ that have the same probability law and are Harris chains according to the above definition can be coupled as follows: Suppose that ${\displaystyle X_{n}=x}$ and ${\displaystyle Y_{n}=y}$, where ${\displaystyle x}$ and ${\displaystyle y}$ are points in ${\displaystyle A}$. Using the same coin flip to decide the next-state of both processes, it follows that the next states are the same with probability at least ${\displaystyle \varepsilon }$.

In the following ${\displaystyle R:=\inf\{n\geq 1:X_{n}\in A\}}$; i.e. ${\displaystyle R}$ is the first time after time 0 that the process enters region ${\displaystyle A}$. Let ${\displaystyle \mu }$ denote the initial distribution of the Markov chain, i.e. ${\displaystyle X_{0}\sim \mu }$.

Definition: If for all ${\displaystyle \mu }$, ${\displaystyle P[R<\infty |X_{0}\in A]=1}$, then the Harris chain is called recurrent.

Definition: A recurrent Harris chain ${\displaystyle X_{n}}$ is aperiodic if ${\displaystyle \exists N}$, such that ${\displaystyle \forall n\geq N}$, ${\displaystyle \forall \mu ,P[X_{n}\in A|X_{0}\in A]>0}$

Theorem: Let ${\displaystyle X_{n}}$ be an aperiodic recurrent Harris chain with stationary distribution ${\displaystyle \pi }$. If ${\displaystyle P[R<\infty |X_{0}\in A]=1}$ then as ${\displaystyle n\rightarrow \infty }$, ${\displaystyle ||{\mathcal {L}}(X_{n}|X_{0})-\pi ||_{TV}\rightarrow 0}$ where ${\displaystyle ||\cdot ||_{TV}}$ denotes the total variation for signed measures defined on the same measurable space.