# 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

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.