- Harris chain
In the mathematical study of
stochastic process es, a Harris chain is aMarkov chain satisfying an additional property.Definition
A
Markov chain {"Xn"} on state space Ω withkernel "K" is a "Harris chain" [R. Durrett. "Probability: Theory and Examples". Thomson, 2005. ISBN 0-534-42441-4.] if there exist "A", "B" ⊆ Ω, ϵ > 0, andprobability measure ρ with ρ("B") = 1 such that
# If τ"A" := inf {"n" ≥ 0 : "Xn" ∈ "A"}, then P(τ"A" < ∞|"X"0 = "x") > 0 for all "x" ∈ Ω.
# If "x" ∈ "A" and "C" ⊆ "B" then "K"("x", "C") ≥ "ερ"("C").In essence, this technical definition can be rephrased as follows: given two points "x"1 and "x"2 in "A", then there is at least an ϵ chance that they can be moved together to the same point at the next time step.
Another way to say it is that suppose that "x" and "y" are in "A". Then at the next time step I first flip a Bernoulli with parameter ϵ. If it comes up one, I move the points to a point chosen using ρ. If it comes up zero, the points move independently, with "x" moving according to P("X""n"+1 ∈ C|"Xn" = "x") = "K"("x", "C") − "ερ"("C") and "y" moving according to P("Y""n"+1 ∈ "C"|"Y""n" = "y") = "K"("y", "C") − "ερ"("C").
Examples
Example 1: Countable state space
Given a countable set "S" and a pair ("A"′, "B"′ ) satisfying (1) and (2) in the above definition, we can without loss of generality take "B"′ to be a single point "b". Upon setting "A" = {"b"}, pick "c" such that "K"("b", "c") > 0 and set "B" = {"c"}. Then, (1) and (2) hold with "A" and "B" as singletons.
Example 2: Chains with continuous densities
Let {"X""n"}, "X""n" ∈ R"d" be a
Markov Chain with akernel that isabsolutely continuous with respect toLebesgue measure :: "K"("x", "dy") = "K"("x", "y") "dy"
such that "K"("x", "y") is a
continuous function .Pick ("x"0, "y"0) such that "K"("x"0, "y"0 ) > 0, and let "A" and "B" be
open sets containing "x"0 and "y"0 respectively that are sufficiently small so that "K"("x", "y") ≥ "ε" > 0 on "A" × "B". Letting "ρ"("C") = |"B" ∩ "C"|/|"B"| where |"B"| is theLebesgue measure of "B", we have that (2) in the above definition holds. If (1) holds, then {"X""n"} is a Harris chain.Reducibility and periodicity
In the following, "R" := inf {"n" ≥ 1 : "Xn" ∈ "A"}; i.e. "R" is the first time after time 0 that the process enters region "A".
Definition: If for all "L"("X"0), "P"("R" < ∞|"X"0 ∈ "A") = 1, then the Harris chain is called "recurrent."
Definition: A recurrent Harris chain "Xn" is "aperiodic" if ∃"N", such that ∀"n" ≥ "N", ∀"L"("X"0), P("Xn" ∈ "A"|"X"0 ∈ "A") > 0.
Theorem: Let "Xn" be an aperiodic recurrent Harris chain with stationary distribution π. If P("R" < ∞|"X"0 = "x") then as "n" → ∞, distTV ("L"("Xn"|"X"0 = "x"), π) → 0.
References
Wikimedia Foundation. 2010.