Harris chain

Let $\backslash \{X\_n\backslash \}$ be a Markov chain on a general state space $\backslash Omega$ with stochastic kernel $K$. The kernel represents a generalized one-step transition probability law, so that $P(X\_\{n+1\}\backslash in\; C\backslash mid\; X\_n=x)=K(x,C)$ for all states $x$ in $\backslash Omega$ and all measurable sets $C\backslash subseteq\; \backslash Omega$. The chain $\backslash \{X\_n\backslash \}$ is a Harris chainR. Durrett. Probability: Theory and Examples. Thomson, 2005. {{ISBN|0-534-42441-4}}. if there exists $A\backslash subseteq\backslash Omega,\backslash varepsilon>0$, and probability measure $\backslash rho$ with $\backslash rho(\backslash Omega)=1$ such that

1. If $\backslash tau\_A:=\backslash inf\; \backslash \{n\backslash geq\; 0:X\_n\backslash in\; A\backslash \}$, then for all $x\backslash in\backslash Omega$.
2. If $x\backslash in\; A$ and $C\backslash subseteq\backslash Omega$ (where $C$ is measurable), then $K(x,\; C)\backslash geq\; \backslash varepsilon\backslash rho(C)$.

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

Two random processes $\backslash \{X\_n\backslash \}$ and $\backslash \{Y\_n\backslash \}$ that have the same probability law and are Harris chains according to the above definition can be coupled as follows: Suppose that $X\_n=x$ and $Y\_n=y$, where $x$ and $y$ are points in $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 $\backslash varepsilon$.

Let Ω be a countable state space. The kernel K is defined by the one-step conditional transition probabilities P[X_n+1 = y | X_n = x] for x,y ∈ Ω. The measure ρ is a probability mass function on the states, so that ρ(x) ≥ 0 for all x ∈ Ω, and the sum of the ρ(x) probabilities is equal to one. Suppose the above definition is satisfied for

a given set A ⊆ Ω and a given parameter ε > 0. Then P[X_n+1 = c | X_n = x] ≥ ερ(c) for all x ∈ A and all c ∈ Ω.

Let {X_n}, X_n ∈ R^d be a Markov chain with a kernel that is absolutely continuous with respect to Lebesgue measure:

: K(x, dy) = K(x, y) dy

such that K(x, y) is a continuous function.

Pick (x₀, y₀) such that K(x₀, y₀ ) > 0, and let A and Ω be open sets containing x₀ and y₀ respectively that are sufficiently small so that K(x, y) ≥ ε > 0 on A ×  Ω. Letting ρ(C) = |Ω ∩ C|/|Ω| where |Ω| is the Lebesgue measure of Ω, we have that (2) in the above definition holds. If (1) holds, then {X_n} is a Harris chain.

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

Definition: If for all $\backslash mu$, , then the Harris chain is called recurrent.

Definition: A recurrent Harris chain $X\_n$ is aperiodic if $\backslash exists\; N$, such that $\backslash forall\; n\backslash ge\; N$, $\backslash forall\; \backslash mu,\; P[X\_n\backslash in\; A\; |\; X\_0\; \backslash in\; A]>0$

Theorem: Let $X\_n$ be an aperiodic recurrent Harris chain with stationary distribution $\backslash pi$. If then as $n\backslash rightarrow\backslash infty$, $||\backslash mathcal\{L\}(X\_n|X\_0)-\backslash pi||\_\{TV\}\backslash rightarrow\; 0$ where $||\backslash cdot||\_\{TV\}$ denotes the total variation for signed measures defined on the same measurable space.

Category:Markov processes