## 16.1 Markov chains

A Markov chain is a sequence of random variables $$\theta^{(1)}, \theta^{(2)},\ldots$$ where each variable is conditionally independent of all other variables given the value of the previous value. Thus if $$\theta = \theta^{(1)}, \theta^{(2)},\ldots, \theta^{(N)}$$, then

$p(\theta) = p(\theta^{(1)}) \prod_{n=2}^N p(\theta^{(n)}|\theta^{(n-1)}).$

Stan uses Hamiltonian Monte Carlo to generate a next state in a manner described in the Hamiltonian Monte Carlo chapter.

The Markov chains Stan and other MCMC samplers generate are ergodic in the sense required by the Markov chain central limit theorem, meaning roughly that there is a reasonable chance of reaching one value of $$\theta$$ from another. The Markov chains are also stationary, meaning that the transition probabilities do not change at different positions in the chain, so that for $$n, n' \geq 0$$, the probability function $$p(\theta^{(n+1)}|\theta^{(n)})$$ is the same as $$p(\theta^{(n'+1)}|\theta^{(n')})$$ (following the convention of overloading random and bound variables and picking out a probability function by its arguments).

Stationary Markov chains have an equilibrium distribution on states in which each has the same marginal probability function, so that $$p(\theta^{(n)})$$ is the same probability function as $$p(\theta^{(n+1)})$$. In Stan, this equilibrium distribution $$p(\theta^{(n)})$$ is the target density $$p(\theta)$$ defined by a Stan program, which is typically a proper Bayesian posterior density $$p(\theta | y)$$ defined on the log scale up to a constant.

Using MCMC methods introduces two difficulties that are not faced by independent sample Monte Carlo methods. The first problem is determining when a randomly initialized Markov chain has converged to its equilibrium distribution. The second problem is that the draws from a Markov chain may be correlated or even anti-correlated, and thus the central limit theorem’s bound on estimation error no longer applies. These problems are addressed in the next two sections.

Stan’s posterior analysis tools compute a number of summary statistics, estimates, and diagnostics for Markov chain Monte Carlo (MCMC) samples. Stan’s estimators and diagnostics are more robust in the face of non-convergence, antithetical sampling, and long-term Markov chain correlations than most of the other tools available. The algorithms Stan uses to achieve this are described in this chapter.