Markov Chain

Elements of Markov Chain

  • A measurable state space \(\mathcal{X}\).
  • A transition kernel \(T: \mathcal{X} \mapsto \mathcal{X}\).

For discrete state space \(\mathcal{X}\), the transition kernel can also be written as a transition matrix, where \(P_{ij}\) is the probability of state \(i\) transit to state \(j\).

Given an initial state distribution \(\pi_0(x)\), the distribution after \(k\)-cycle MCMC transition is \(\pi_k(x)\), defined as: \[ \pi_k(x) = (T \pi_{k-1})(x) = \int_{\mathcal{X}} \pi_{k-1}(y) \,T(y, x)\,dy \] We shall use \(T^k\) to denote such a \(k\)-cycle transition, such that: \[ \pi_k(x) = (T^k \pi_0)(x) = \int_{\mathcal{X}} \pi_0(y) \,T^k(y, x)\,dy \]

  • Stationary distribution: if there exists \(\pi(x)\) such that \(\pi = T\pi\), then \(\pi\) is a stationary distribution of the Markov chain derived by \(T\), denoted as \(\pi^{\star}(x)\).

Ergodicity of Markov Chain

TODO: Write about ergodicity, instead of separated "irreducible" and "aperiodic".

A state i is said to be ergodic if it is aperiodic and positive recurrent.

-- https://en.wikipedia.org/wiki/Markov_chain#Ergodicity

Existence and Uniqueness of the Stationary Distribution

The necessary condition for a unique stationary distribution \(\pi^{\star}(x)\) of a Markov chain to exist is that the chain is irreducible and aperiodic.

  • Irreducible:
    • A Markov chain is irreducible if \(\forall x,\,y\), there exists \(k \in \mathbb{N}\), such that \(T^k(x,y) > 0\).
  • Aperiodic:
    • The period of a state \(x\) is defined as: \(\mathrm{gcd}\left\{k > 0 : T^k(x,x) > 0\right\}\).
    • A state \(x\) is aperiodic if the period of \(x\) is 1.
    • A Markov chain is aperiodic if every state of this chain is aperiodic.
    • If there is an aperiodic state in an irreducible Markov chain, then all states of this Markov chain is aperiodic.

Detailed Balance Condition

In practice, the transition kernel is often chosen to satisfy the detailed balance condition. If there exists a state distribution \(\pi(x)\), such that \(\forall x, \, y\), \[ \pi(x) \, T(x,y) = \pi(y) \, T(y, x) \]

We say that \(T\) satisfies the detailed balance condition. Furthermore, in such situation, \(\pi\) is the stationary distribution of the Markov chain, and the chain is reversible.

If the Markov chain is further irreducible and aperiodic, then \(\pi\) is the unique stationary distribution.

Hybird Markov Chain

If \(T_1\) and \(T_2\) are two kernels with the same stationary distribution \(\pi^{\star}\), and if \(T_1\) produces an irreducible Markov chain, then the mixture kernel: \[ T = \alpha T_1 + (1-\alpha) T_2 \qquad\qquad (0 < \alpha < 1) \] is also irreducible.