# Markov Chain

## Essential properties of Markov Chain

In the setup of MCMC algorithms, we construct Markov chains from a transition kernel $$K$$, a conditional probability density such that $$X\_{n+1}\sim K(X\_n,X\_{n+1})$$.

The chain encountered in MCMC settings enjoy a very strong stability property, namely a **stationary probability distribution**; that is, a distribution $$\pi$$ such that if $$X\_n\sim\pi$$, then $$X\_{n+1}\sim \pi$$, if the kernel $$K$$ allows for free moves all over the state space. This freedom is called **irreducibility** in the theory of Markov chains and is formalized as the existence of $$n\in\mathbb{N}$$ such that $$P(X\_n\in A\mid X\_0)>0$$ for every $$A$$ such that $$\pi(A)>0$$. This property also ensures that most of the chains involved in MCMC algorithms are **recurrent** (that is, that the average number of visits to an arbitrary set $$A$$ is infinite), or even **Harris recurrent** (that is, such that the probability of an infinite number of returns to $$A$$ is 1).

**Harris recurrence** ensures that the chain has the same limiting behavior for every starting value instead of almost every starting value.

The stationary distribution is also a limiting distribution in the sense that the limiting distribution of $$X\_{n+1}$$ is $$\pi$$ under the total variation norm, notwithstanding the initial value of $$X\_0$$.

Strong forms of convergence are also encountered in MCMC settings, like geometric and uniform convergences.

If the marginals are proper, for convergence we only need our chain to be aperiodic. A sufficient condition is that $$K(x\_n,\cdot)>0$$ (or, equivalently, $$f(\cdot\mid x\_n)>0$$) in a neighborhood of $$x\_n$$.

If the marginal are not proper, or if they do not exist, then the chain is not positive recurrent. It is either null recurrent, and both cases are bad.

The [detailed balance condition](https://github.com/szcf-weiya/MonteCarlo/tree/a8a19b34ad8646f12cf5d7a4e4bfa9919c392451/MarkovChain/detailed_balance_condition.png) is **not necessary** for $$f$$ to be a stationary measure associated with the transition kernel $$K$$, but it provides a sufficient condition that is often easy to check and that can be used for most MCMC algorithms.

Ergodicity: independence of initial conditions

* [geometrically h-ergodic](https://github.com/szcf-weiya/MonteCarlo/tree/a8a19b34ad8646f12cf5d7a4e4bfa9919c392451/MarkovChain/def_geometrical_h_ergodic.png): decreasing at least at a geometric speed.
* [uniform ergodicity](https://github.com/szcf-weiya/MonteCarlo/tree/a8a19b34ad8646f12cf5d7a4e4bfa9919c392451/MarkovChain/def_uniform_ergodic.png): stronger than geometric ergodicity in the sense that the rate of geometric convergence must be uniform over the whole space.

Irreducibility + Aperiodic = Ergodicity ?

## Basic Notions

![](/files/-LX1zwX_SlG1OoZ8kk5t)

![](/files/-LX1zwXdq7UQeIbmqdl1)

## Bernoulli-Laplace Model

![](/files/-LX1zwXbQGKRNn-5z67E)

The finite chain is indeed irreducible since it is possible to connect the status $$x$$ and $$y$$ in $$\vert x-y\vert$$ steps with probability

$$
\prod\_{i=x\land y}^{x\vee y-1}\Big(\frac{M-i}{M}\Big)^2,.
$$

The Bernoulli-Laplace chain is [aperiodic](https://github.com/szcf-weiya/MonteCarlo/tree/a8a19b34ad8646f12cf5d7a4e4bfa9919c392451/MarkovChain/def_period_discrete.png) and even [strongly aperiodic](https://github.com/szcf-weiya/MonteCarlo/tree/a8a19b34ad8646f12cf5d7a4e4bfa9919c392451/MarkovChain/def_period.png) since the diagonal terms satisfy $$P\_{xx}>0$$ for every $$x\in {0,\ldots,K}$$.

Given the quasi-diagonal shape of the transition matrix, it is possible to directly determine the invariant distribution, $$\pi=(\pi\_0,\ldots,\pi\_K)$$. From the equation $$\pi P = \pi$$,

$$
\begin{aligned}
\pi\_0 &= P\_{00}\pi\_0 + P\_{10}\pi\_1\\
\pi\_1 &= P\_{01}\pi\_1 + P\_{11}\pi\_1 + P\_{21}\pi\_2\\
\cdots &=\cdots\\
\pi\_K &= P\_{(K-1)K}\pi\_{K-1} + P\_{KK}\pi\_K,.
\end{aligned}
$$

Thus,

$$
\pi\_k=\binom{K}{k}^2\pi\_0,,\qquad k=0,\ldots,K,,
$$

and through normalization,

$$
\pi\_k=\frac{\binom{K}{k}^2}{\binom{2K}{K}},,
$$

by using [Chu-Vandermonde identity](https://en.wikipedia.org/wiki/Vandermonde's_identity)

$$
\binom{m+n}{r}=\sum\_{k=0}^r\binom{m}{k}\binom{n}{r-k}
$$

with $$m=n=r=K$$. It turns out that the hypergeometric distribution $$H(2K,K,1/2)$$ is the [invariant distribution](https://github.com/szcf-weiya/MonteCarlo/tree/a8a19b34ad8646f12cf5d7a4e4bfa9919c392451/MarkovChain/def_invariant.png) for the Bernoulli-Laplace model.

## AR(1) Models

A simple illustration of Markov chains on continuous state-space.

$$
X\_n = \theta X\_{n-1}+\varepsilon\_n;,\theta\in \mathrm{I!R},,
$$

with $$\varepsilon\_n\in N(0,\sigma^2)$$, and if the $$\varepsilon\_n$$'s are independent, $$X\_n$$ is indeed independent from $$X\_{n-2},X\_{n-3},\ldots$$ conditionally on $$X\_{n-1}$$.

* The Markovian properties of an AR(q) can be derived from $$(X\_n,\ldots,X\_{n-q+1})$$.
* ARMA(p, q) doesn't fit in the Markovian framework.

Since $$X\_n\mid x\_{n-1}\sim N(\theta x\_{n-1},\sigma^2)$$, consider the lower bound of the transition kernel ($$\theta > 0$$):

$$
\begin{aligned}
K(x\_{n-1},x\_n) &= \frac{1}{\sqrt{2\pi}}\exp\Big{-\frac{1}{2\sigma^2}(x\_n-\theta x\_{n-1})^2\Big}\\
&\ge \frac{1}{\sqrt{2\pi}\sigma}\exp\Big{-\frac{1}{2\sigma^2}\max{(x\_n-\theta \underline w)^2, (x\_n-\theta \bar w)^2}\Big}\\
&\ge \frac{1}{\sqrt{2\pi}\sigma}\exp\Big{-\frac{1}{2\sigma^2}\Big\[ \max{-2\theta x\_n\underline w,-2\theta x\_n\bar w}+x\_n^2 + \theta^2\underline w^2\land \bar w^2 \Big]\Big}\\
&=\begin{cases}
\frac{1}{\sqrt{2\pi}\sigma}\exp\Big{-\frac{1}{2\sigma^2}\Big\[ -2\theta x\_n\underline w+x\_n^2 + \theta^2\underline w^2\land \bar w^2 \Big]\Big}& \text{if }x\_n>0\\
\frac{1}{\sqrt{2\pi}\sigma}\exp\Big{-\frac{1}{2\sigma^2}\Big\[ -2\theta x\_n\bar w+x\_n^2 + \theta^2\underline w^2\land \bar w^2 \Big]\Big}& \text{if }x\_n<0
\end{cases},,
\end{aligned}
$$

when $$x\_{n-1}\in\[\underline w, \bar w]$$. The set $$C = \[\underline w, \bar w]$$ is a [small set](https://github.com/szcf-weiya/MonteCarlo/tree/a8a19b34ad8646f12cf5d7a4e4bfa9919c392451/MarkovChain/def_small.png), as the measure $$\nu\_1$$ with density

$$
\frac{\exp{(-x^2+2\theta x\underline w)/2\sigma^2}I\_{x>0} + \exp{(-x^2+2\theta x\bar w)/2\sigma^2}I\_{x<0} }{\sqrt{2\pi}\sigma{\[1-\Phi(-\theta\underline w/\sigma^2)]\exp(\theta^2\underline w^2/2\sigma^2)+\Phi(-\theta\bar w/\sigma)\exp(\theta^2\bar w^2/2\sigma^2)}},,
$$

satisfy

$$
K^1(x,A)\ge \nu\_1(A),\qquad \forall x\in C, \forall A\in {\cal B(X)},.
$$

Given that the transition kernel corresponds to the $$N(\theta x\_{n-1},\sigma^2)$$ distribution, a normal distribution $$N(\mu,\tau^2)$$ is stationary for the AR(1) chain only if

$$
\mu=\theta\mu\qquad\text{and}\qquad \tau^2=\tau^2\theta^2+\sigma^2,.
$$

These conditions imply that $$\mu=0$$ and that $$\tau^2=\sigma^2/(1-\theta^2)$$, which can only occur for $$\vert \theta\vert < 1$$. In this case, $$N(0,\sigma^2/(1-\theta^2))$$ is indeed the unique stationary distribution of the AR(1) chain.

## Branching process

![](/files/-LX4VIo9tpwvAyiNqljv)

* If $$\phi$$ doesn't have a constant term, i.e., $$P(X\_1=0)=0$$, then chain $$S\_t$$ is necessarily transient since it is increasing.
* If $$P(X\_1=0)>0$$, the probability of a return to 0 at time $$t$$ is $$\rho(t)=P(S\_t=0)=g\_t(0)$$, which thus satisfies the recurrence equation $$\rho\_t=\phi(\rho\_{t-1})$$. There exists a limit $$\rho$$ different from 1, such that $$\rho=\phi(\rho)$$, iff $$\phi'(1)>1$$; namely if $$E\[X]>1$$. The chain is thus transient when the average number of siblings per individual is larger than 1. If there exists a restarting mechanism in 0, $$S\_{t+1}\mid S\_t=0\sim\phi$$, it is easily shown that when $$\phi'(1)>1$$, the number of returns to 0 follows a geometric distribution with parameter $$\rho$$.

![](/files/-LX4VIoBfrKP5hf5FwYM)

* If $$\phi'(1)\le 1$$, the chain is recurrent.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mc.hohoweiya.xyz/markovchain.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.