Markov Property and Markov Chains
Consider a sequence of random variables $x^{(1)}, x^{(2)}, x^{(3)}, \dots$ at discrete time steps $t=1, 2, 3, \dots$.
- Markov Chain: A system where the sequence of random variables $x^{(1)}, x^{(2)}, x^{(3)}, \dots$ is generated according to a certain rule.
- Markov Property: The property that the state at a given time depends only on the immediately preceding state (or a limited number of past states), rather than on the entire history.
- First-order Markov property: The state $x^{(t)}$ depends only on $x^{(t-1)}$.
- $n$-th order Markov property: The state $x^{(t)}$ depends only on $x^{(t-1)}, \dots, x^{(t-n)}$.
- Transition probability $p(x^{(t)}|x^{(t-1)})$: The probability of transitioning from state $x^{(t-1)}$ at time $t-1$ to state $x^{(t)}$ at time $t$.
- Stationary distribution $\pi(x)$: The probability distribution over states that a Markov chain converges to after running for a sufficiently long time. The stationary distribution satisfies the following balance equation: $$ \pi(y) = \sum_x p(y|x)\pi(x) $$
Markov Chain Monte Carlo (MCMC)
MCMC is a method for generating samples from complex probability distributions that are difficult to sample from directly. It works by designing transition probabilities so that the stationary distribution of a Markov chain matches the target distribution, and then simulating that Markov chain to generate samples.
Among the sequence of samples $x^{(1)}, x^{(2)}, \dots$ generated by MCMC, the initial samples are strongly influenced by the starting value of the Markov chain. These are discarded as the burn-in period. Samples from after a sufficiently long burn-in period ($x^{(t)}, x^{(t+1)}, \dots$ for sufficiently large $t$) are used for inference.
One of the most widely used MCMC algorithms is the Metropolis-Hastings algorithm.
Metropolis-Hastings Algorithm
Suppose we want to obtain samples from a target distribution $p(x)$.
- Set an initial state $x^{(1)}$ randomly.
- Repeat the following steps ($t=1, 2, \dots$): a. From the current state $x^{(t)}$, sample a new candidate state $\hat{y}$ from the proposal distribution $q(\hat{y}|x^{(t)})$. b. Compute the acceptance probability $\alpha(x^{(t)}, \hat{y})$. $$ \alpha(x^{(t)}, \hat{y}) = \min\left(1, \frac{p(\hat{y})q(x^{(t)}|\hat{y})}{p(x^{(t)})q(\hat{y}|x^{(t)})}\right) $$ Here, $p(x)$ is the target distribution. c. Generate a uniform random number $u$ from $[0, 1]$. If $u < \alpha(x^{(t)}, \hat{y})$, accept the candidate $\hat{y}$ as the next state $x^{(t+1)}$. Otherwise, set $x^{(t+1)} = x^{(t)}$ and remain in the current state.
By repeating this process, the generated sequence converges to the target distribution $p(x)$.
References
- Taro Tezuka, “Understanding Bayesian Statistics and Machine Learning,” Kodansha (2017)