The logistic regression of diabetes on age and obesity in 5,107 adults of the National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 (National Center for Health Statistics, 2020) was fitted by maximum likelihood in Iteratively Reweighted Least Squares. Given a prior for its three coefficients, the posterior distribution is proportional to the prior times the likelihood, and that product can be evaluated at any point. Its normalizing constant, the integral of the product over all three coefficients, has no closed form, and neither do the posterior means and intervals, which are integrals of the same kind. How can we draw values from a distribution that we can evaluate only up to a constant, and how can we tell whether the draws describe it well enough? We can, by running a Markov chain built so that the posterior is its long-run distribution; and we can tell, imperfectly, by measuring how correlated the draws are and whether separate chains agree.
Markov chain Monte Carlo (MCMC) constructs a sequence $\theta^{(0)}, \theta^{(1)}, \theta^{(2)}, \ldots$ in which each value is drawn from a distribution that depends only on the one before. The sequence is arranged so that the posterior distribution is stationary: a value drawn from the posterior is followed by another value drawn from the posterior. Averages along the sequence then estimate posterior expectations. The two standard constructions are the Metropolis–Hastings algorithm, which proposes a move and accepts it with a carefully chosen probability, and Gibbs sampling, which redraws one block of unknowns at a time from its distribution given the rest.
First we define Markov chains on a continuous state space and their stationary distributions, and prove that a condition called detailed balance implies stationarity. Then we prove that the Metropolis–Hastings algorithm satisfies detailed balance, and that Gibbs sampling is the case where every proposal is accepted. Next we state, with their sources, the theorems that make the averages converge, and check a Gibbs sampler against an exact posterior. Then we define the diagnostics: warm-up, autocorrelation and effective sample size, and the split R-hat statistic. Finally we sample the logistic regression posterior with random-walk proposals of eight sizes, 30 seeds each. The article assumes Priors, Posteriors and Conjugate Families for the unit's notation and the conjugate posteriors, and uses PageRank, the site's home for Markov chains on finitely many states.
Notation
The unit's notation is kept: model $f(\mathbf{x} \mid \theta)$, prior $\pi(\theta)$, posterior $\pi(\theta \mid \mathbf{x}) = f(\mathbf{x} \mid \theta)\pi(\theta)/m(\mathbf{x})$, with $m(\mathbf{x})$ the marginal likelihood. The data are fixed throughout, so the target density is written $\pi(\theta)$ for $\pi(\theta \mid \mathbf{x})$ in the sections on general theory. All the algorithms use the target only through ratios $\pi(\theta')/\pi(\theta)$, in which $m(\mathbf{x})$ cancels: they need $f(\mathbf{x} \mid \theta)\pi(\theta)$ and nothing else. The unknowns $\theta$ range over a set $\Theta$, usually an open subset of $\mathbb{R}^d$. Normal distributions are described in words, or as $N(\mu, \sigma)$ with the standard deviation as the second argument, as on The Normal Distribution.
Markov chains and stationary distributions
A Markov chain on $\Theta$ is a sequence of random values $\theta^{(0)}, \theta^{(1)}, \ldots$ such that, given all of $\theta^{(0)}, \ldots, \theta^{(t)}$, the distribution of $\theta^{(t+1)}$ depends only on $\theta^{(t)}$, through a fixed transition kernel $K$: $K(\theta, A)$ is the probability that the next value lies in the set $A$ when the current value is $\theta$. On finitely many states the kernel is a matrix of transition probabilities, and PageRank treats that case in full, including the stationary distribution as a left eigenvector and power iteration. The kernels of MCMC on a continuous space have a particular form: with some probability the chain moves, to a point spread out with a density, and otherwise it stays where it is. So
$$K(\theta, A) = \int_A k(\theta, \theta')\,d\theta' + r(\theta)\,\mathbf{1}\{\theta \in A\}, \qquad r(\theta) = 1 - \int_\Theta k(\theta, \theta')\,d\theta', \qquad (1)$$
with $k(\theta, \theta') \ge 0$ the density of moves and $r(\theta)$ the probability of staying put.
A distribution with density $\pi$ is stationary (or invariant) for $K$ if
$$\int_\Theta \pi(\theta)\,K(\theta, A)\,d\theta = \pi(A) \quad \text{for every set } A, \qquad (2)$$
where $\pi(A) = \int_A \pi(\theta)\,d\theta$. The left side is the probability that $\theta^{(t+1)} \in A$ when $\theta^{(t)}$ has density $\pi$. So a chain started from the stationary distribution, or arriving there, has that distribution at every later step. Two ways of combining kernels keep it.
Lemma 1 (composition and mixture). If $\pi$ is stationary for kernels $K_1, \ldots, K_J$, it is stationary for the kernel that applies $K_1$, then $K_2$, and so on to $K_J$; and for the mixture $\sum_j w_jK_j$ that picks kernel $j$ with probability $w_j$.
Proof. If $\theta$ has density $\pi$, one step of $K_1$ leaves the new value with distribution $\pi$ by (2), so the step of $K_2$ starts from $\pi$ and ends at $\pi$, and so on. For the mixture, $\int\pi(\theta)\sum_jw_jK_j(\theta, A)\,d\theta = \sum_jw_j\pi(A) = \pi(A)$. $\square$
Stationarity alone does not make a chain useful. The kernel that never moves, $K(\theta, A) = \mathbf{1}\{\theta \in A\}$, has every distribution as a stationary one. What else is needed is the subject of the section on convergence. First, how to build a kernel with a given $\pi$ stationary when $\pi$ is known only up to a constant.
Detailed balance
Here is the idea. Imagine a large population of independent chains, distributed according to $\pi$, each taking one step. If, for every pair of points, as many chains move from the first to the second as from the second to the first, the population's distribution cannot change. That pairwise balance is easy to check, because it involves the kernel at two points only.
A kernel of the form (1) satisfies detailed balance with respect to $\pi$ if
$$\pi(\theta)\,k(\theta, \theta') = \pi(\theta')\,k(\theta', \theta) \quad \text{for all } \theta \ne \theta'. \qquad (3)$$
A chain is called reversible with respect to $\pi$ if, started from $\pi$, the pair $(\theta^{(t)}, \theta^{(t+1)})$ has the same distribution as $(\theta^{(t+1)}, \theta^{(t)})$. For a kernel of the form (1), detailed balance implies it. For any set $C$ of pairs,
$$P\big((\theta^{(t)}, \theta^{(t+1)}) \in C\big) = \iint_C \pi(\theta)\,k(\theta, \theta')\,d\theta\,d\theta' + \int\pi(\theta)\,r(\theta)\,\mathbf{1}\{(\theta, \theta) \in C\}\,d\theta.$$
By (3) the first integrand is unchanged, off the diagonal $\theta = \theta'$ (a set of zero volume), when $\theta$ and $\theta'$ are exchanged, and the second term involves only pairs with both entries equal, so the probability is the same for the reversed pair.
Theorem 1 (detailed balance implies stationarity). If a kernel of the form (1) satisfies detailed balance (3) with respect to a probability density $\pi$, then $\pi$ is stationary for it.
Proof. Fix a set $A$. By (1), the left side of (2) is
$$\int_\Theta\pi(\theta)\int_A k(\theta, \theta')\,d\theta'\,d\theta + \int_A \pi(\theta)\,r(\theta)\,d\theta.$$
In the first term the integrand is nonnegative, so the order of integration may be exchanged (Tonelli's theorem, which the Probability Theory unit cites rather than proves; see Random Variables and Distribution Functions, section "What is proved here, what is cited, and what measure theory would add"). Then apply (3) inside, which is allowed because the single point $\theta = \theta'$ contributes nothing to the inner integral:
$$\int_A\int_\Theta\pi(\theta)\,k(\theta, \theta')\,d\theta\,d\theta' = \int_A\int_\Theta\pi(\theta')\,k(\theta', \theta)\,d\theta\,d\theta' = \int_A\pi(\theta')\big[1 - r(\theta')\big]\,d\theta'.$$
Adding the second term, $\int_A\pi(\theta')[1 - r(\theta')]\,d\theta' + \int_A\pi(\theta)r(\theta)\,d\theta = \int_A\pi(\theta)\,d\theta = \pi(A)$. $\square$
For finitely many states the same computation reads $\sum_i\pi_iP_{ij} = \sum_i\pi_jP_{ji} = \pi_j$, with the sums in place of integrals and no separate term for staying put. Bishop (2006, §11.2.1, eq. 11.41) gives that form; Roberts and Rosenthal (2004, Proposition 1) give the general one. Detailed balance is sufficient and not necessary: the systematic-scan Gibbs sampler below has $\pi$ stationary without it.
The Metropolis–Hastings algorithm
Choose a proposal density $q(\theta, \theta')$: for each current point $\theta$, a density in $\theta'$ that is easy to sample. A common choice is a normal density centered at $\theta$. The chain moves as follows.
- From the current value $\theta^{(t)} = \theta$, draw a proposal $\theta'$ from $q(\theta, \cdot)$.
- Compute the acceptance probability $$\alpha(\theta, \theta') = \min\Big\{1,\ \frac{\pi(\theta')\,q(\theta', \theta)}{\pi(\theta)\,q(\theta, \theta')}\Big\},$$ with $\alpha = 1$ when the denominator is 0.
- With probability $\alpha(\theta, \theta')$ set $\theta^{(t+1)} = \theta'$ (the proposal is accepted); otherwise set $\theta^{(t+1)} = \theta$ (it is rejected, and the current value is repeated).
The target enters only through the ratio $\pi(\theta')/\pi(\theta)$, in which the marginal likelihood cancels. A proposal is symmetric when $q(\theta, \theta') = q(\theta', \theta)$, as for a normal density centered at the current point. Then the ratio of proposals is 1, and the rule is the one Bishop (2006, §11.2) credits to Metropolis, Rosenbluth, Rosenbluth, Teller and Teller (1953): always accept a move uphill, and accept a move downhill with probability equal to the ratio of the densities. Hastings (1970) allowed asymmetric proposals by adding the ratio $q(\theta', \theta)/q(\theta, \theta')$. The resulting chain has the form (1), with move density $k(\theta, \theta') = q(\theta, \theta')\,\alpha(\theta, \theta')$ and staying probability $r(\theta) = 1 - \int q(\theta, \theta')\alpha(\theta, \theta')\,d\theta'$, the chance that the proposal is rejected.
Theorem 2 (Metropolis–Hastings satisfies detailed balance). For any target density $\pi$ and any proposal density $q$, the Metropolis–Hastings kernel satisfies detailed balance with respect to $\pi$. Hence $\pi$ is stationary for it.
Proof. Let $\theta \ne \theta'$, and write $u = \pi(\theta)q(\theta, \theta')$ and $v = \pi(\theta')q(\theta', \theta)$. If $u > 0$, then $\pi(\theta)\,k(\theta, \theta') = u\min\{1, v/u\} = \min\{u, v\}$. If $u = 0$, the left side is 0, which is again $\min\{u, v\}$ since $v \ge 0$. By the same argument with the roles exchanged, $\pi(\theta')\,k(\theta', \theta) = \min\{v, u\}$. The two are equal, which is (3), and Theorem 1 gives stationarity. $\square$
The proof is that of Roberts and Rosenthal (2004, Proposition 2) and of Bishop (2006, eq. 11.45). It explains the acceptance probability: of the two flows between $\theta$ and $\theta'$, the larger is cut down to the smaller, and that is all the rule does. Notice what the theorem does not require. The proposal can be almost anything, and the target need not be normalized. What the proposal does affect is how fast the chain explores, the subject of the last sections.
Gibbs sampling
Split $\theta$ into blocks $\theta_1, \ldots, \theta_J$, and write $\theta_{-j}$ for all the blocks except the $j$-th. The full conditional of block $j$ is its distribution given the rest, $\pi(\theta_j \mid \theta_{-j})$, proportional to $\pi(\theta)$ as a function of $\theta_j$. The Gibbs update of block $j$ replaces $\theta_j$ by a draw from its full conditional and leaves the other blocks alone. A systematic scan updates the blocks in a fixed order, $1, 2, \ldots, J$, and repeats. A random scan updates one block chosen at random.
Theorem 3 (the Gibbs update). For each $j$:
- The Gibbs update of block $j$ is the Metropolis–Hastings move whose proposal draws $\theta_j'$ from the full conditional and keeps $\theta_{-j}$, and its acceptance probability is 1.
- The update leaves $\pi$ stationary, and it is reversible: if $\theta$ has distribution $\pi$ and $\theta'$ is the updated value, $(\theta, \theta')$ and $(\theta', \theta)$ have the same distribution.
Consequently the systematic scan and the random scan both have $\pi$ stationary, and the random scan is reversible.
Proof. (1) The proposal moves from $\theta = (\theta_j, \theta_{-j})$ to $\theta' = (\theta_j', \theta_{-j})$ with density $\pi(\theta_j' \mid \theta_{-j})$. Since $\pi(\theta) = \pi(\theta_{-j})\,\pi(\theta_j \mid \theta_{-j})$, where $\pi(\theta_{-j})$ is the density of the other blocks,
$$\frac{\pi(\theta')\,q(\theta', \theta)}{\pi(\theta)\,q(\theta, \theta')} = \frac{\pi(\theta_{-j})\,\pi(\theta_j' \mid \theta_{-j})\,\pi(\theta_j \mid \theta_{-j})}{\pi(\theta_{-j})\,\pi(\theta_j \mid \theta_{-j})\,\pi(\theta_j' \mid \theta_{-j})} = 1.$$
Here $q$ is a density in $\theta_j'$ alone, on the slice where $\theta_{-j}$ is fixed, so the kernel is not of the form (1) when there is more than one block, and Theorem 2 does not apply as stated. Part 2 proves directly what Theorem 2 would give.
(2) Let $\theta$ have density $\pi$. Then $\theta_{-j}$ has density $\pi(\theta_{-j})$, and given $\theta_{-j}$ the old value $\theta_j$ and the new value $\theta_j'$ are two independent draws from the same full conditional. The triple $(\theta_{-j}, \theta_j, \theta_j')$ therefore has the density $\pi(\theta_{-j})\,\pi(\theta_j \mid \theta_{-j})\,\pi(\theta_j' \mid \theta_{-j})$, which is unchanged when $\theta_j$ and $\theta_j'$ are exchanged. So $(\theta, \theta')$ and $(\theta', \theta)$ have the same distribution. In particular $\theta'$ has the same distribution as $\theta$, which is $\pi$.
For the scans: a systematic scan is the composition of the $J$ updates and a random scan their mixture, so Lemma 1 gives stationarity. For the random scan, let $\theta$ have distribution $\pi$ and let the block $j$ be chosen with probability $w_j$, independently of $\theta$. For any set $C$ of pairs, $P((\theta, \theta') \in C) = \sum_jw_jP((\theta, \theta') \in C \mid j)$, and by part 2 each term is unchanged when the pair is reversed. So the pair is exchangeable, and the random scan is reversible. $\square$
The stationarity half of part 2 is the argument that Latent Dirichlet Allocation gives for its collapsed Gibbs sampler, there on finitely many states. Bishop (2006, §11.3, eq. 11.49) shows part 1 the same way, and Roberts and Rosenthal (2004, §2.3) note both parts and the two scans. The sampler was named by Geman and Geman (1984), whose setting the LDA article describes.
Example (a systematic scan that is not reversible). Take two binary variables with joint probabilities $\pi(0,0) = 0.4$, $\pi(0,1) = 0.1$, $\pi(1,0) = 0.2$ and $\pi(1,1) = 0.3$, and the systematic scan that updates the first variable and then the second. From $(0,0)$ the scan reaches $(1,1)$ if the first update gives 1, with probability $\pi(1,0)/[\pi(0,0) + \pi(1,0)] = 1/3$, and the second then gives 1, with probability $\pi(1,1)/[\pi(1,0) + \pi(1,1)] = 3/5$: in all 0.200. From $(1,1)$ it reaches $(0,0)$ with probability $\frac{\pi(0,1)}{\pi(0,1) + \pi(1,1)} \cdot \frac{\pi(0,0)}{\pi(0,0) + \pi(0,1)} = \frac14 \cdot \frac45$, also 0.200. The flows are $0.4 \times 0.2 = 0.080$ and $0.3 \times 0.2 = 0.060$, which are not equal, so detailed balance fails. The script checks in exact fractions that $\pi$ is nevertheless stationary for the scan, as Lemma 1 says, and that each single update and the random scan do satisfy detailed balance. Roberts and Rosenthal (2004, §2.3) state that the deterministic-scan sampler "usually is not" reversible.
Does the chain reach the posterior?
Stationarity says that a chain started from $\pi$ stays at $\pi$. A sampler is started somewhere else, and it needs two more things: that the distribution of $\theta^{(t)}$ approaches $\pi$ from wherever it starts, and that averages along one path approach posterior expectations. Both hold under conditions that MCMC algorithms usually meet. We state the results and do not prove them; the proofs need the theory of Markov chains on general spaces.
Two failures show what the conditions exclude. A chain may be unable to get from one region to another: a Gibbs sampler on a target whose probability sits in two separated blocks of the plane, each with positive probability, cannot leave the block it starts in. And a chain may cycle with a fixed period, as a deterministic rotation among three states does. Roberts and Rosenthal (2004, §3.2, Examples 1 and 2) give both as three-state examples. Two conditions rule them out.
- $\phi$-irreducibility. There is a nonzero $\sigma$-finite measure $\phi$ (for example volume) such that every set $A$ with $\phi(A) > 0$ is reached from every starting point, with positive probability, in some number of steps.
- Aperiodicity. The space cannot be split into $d \ge 2$ disjoint pieces, the first with positive probability under $\pi$, which the chain visits in a fixed cycle.
Theorem (convergence; cited). Suppose a Markov chain on a state space with a countably generated collection of events (true for subsets of $\mathbb{R}^d$) is $\phi$-irreducible and aperiodic, and has a stationary distribution $\pi$. Then for $\pi$-almost every starting point $\theta$, the distribution of $\theta^{(t)}$ converges to $\pi$ in total variation: $\sup_A\lvert P(\theta^{(t)} \in A) - \pi(A)\rvert \to 0$. If in addition $h$ is a function with $E_\pi\lvert h(\theta)\rvert < \infty$, then $\frac1N\sum_{t=1}^N h(\theta^{(t)}) \to E_\pi[h(\theta)]$ with probability 1.
The first part is Theorem 4 of Roberts and Rosenthal (2004), proved there by coupling; the second, a strong law of large numbers for the chain, is their Fact 5, which they take from Meyn and Tweedie (1993, Theorem 17.0.1). The conditions are usually easy to check. Take a Metropolis–Hastings chain whose proposal density is positive and continuous everywhere, for a target whose density is finite everywhere. Roberts and Rosenthal (2004, §3.2) show that it is $\phi$-irreducible with $\phi = \pi$ itself (for a target positive everywhere, such as the posteriors here, the sets with $\pi(A) > 0$ are those of positive volume), and aperiodic. The normal random-walk proposals below are of that kind. For finitely many states with all transition probabilities positive, Latent Dirichlet Allocation (section "Why the sampler reaches the posterior") proves convergence in full, with a geometric rate.
The averages also have a central limit theorem under stronger conditions. Roberts and Rosenthal (2004, §5) say that $h$ satisfies a central limit theorem if $\sqrt{N}\,[\frac1N\sum_t h(\theta^{(t)}) - E_\pi h]$ converges in distribution to a normal with mean 0 and some variance $\sigma_h^2$. They collect sufficient conditions:
- a chain converging at a rate that does not depend on the start (uniformly ergodic), with $E_\pi[h^2] < \infty$ (their Theorem 23);
- a chain converging at a geometric rate (geometrically ergodic), with $E_\pi\lvert h\rvert^{2+\delta} < \infty$ for some $\delta > 0$ (Theorem 24);
- a geometrically ergodic reversible chain, with $E_\pi[h^2] < \infty$ (Theorem 25).
The variance is then
$$\sigma_h^2 = \operatorname{Var}_\pi(h)\Big(1 + 2\sum_{t=1}^\infty\rho_t\Big), \qquad (4)$$
where $\rho_t$ is the correlation between $h(\theta^{(0)})$ and $h(\theta^{(t)})$ for the chain started in $\pi$. They write $\sigma_h^2 = \tau\operatorname{Var}_\pi(h)$ and call $\tau$ the integrated autocorrelation time. A finite variance of $h$ is not enough by itself: their Theorem 22 shows that a chain that rejects too often can have no such limit at all.
None of these results says how many iterations are enough. That is the job of the diagnostics. First, a check on a posterior that is known exactly.
Gibbs sampling on the blood pressures
Twenty-five adults drawn from the survey (the sample of Priors, Posteriors and Conjugate Families, NumPy generator with seed 1) have systolic pressures from 90.67 to 166.67 mm Hg, with mean $\bar x = 128.69$ and standard deviation 19.11; their sum of squares about the mean is $S = 8{,}763.1$. Model them as independent and normal with mean $\mu$ and precision $\tau = 1/\sigma^2$, with a prior from the normal–inverse-gamma family of that article (its Theorem 7 gives the posterior). The prior's values are our choice: $\mu_0 = 120$, the round value of that article's known-variance example, with $\kappa_0 = 1$ (worth one observation about the mean), $\nu_0 = 4$ and $\sigma_0^2 = 400$ (worth four observations about the variance, at a standard deviation of 20). In terms of $\tau$, $\mu$ given $\tau$ is normal with mean $\mu_0$ and variance $1/(\kappa_0\tau)$, and $\tau$ is gamma with shape $a_0 = 2$ and rate $b_0 = 800$.
The exact answer. By Theorem 7 of that article the posterior has $\kappa_n = 26$, $\mu_n = 128.36$, shape $a_n = a_0 + n/2 = 14.5$ and rate $b_n = b_0 + \tfrac12[S + \kappa_0n(\bar x - \mu_0)^2/\kappa_n] = 5{,}217.9$ for $\tau$. The mean $\mu$ is Student $t$ with 29 degrees of freedom: posterior mean 128.36, standard deviation 3.86, central 95% interval (120.75, 135.97). The posterior mean of $\tau$ is $a_n/b_n$, 2.779 per thousand, and that of $\sigma$ is $\sqrt{b_n}\,\Gamma(a_n - \tfrac12)/\Gamma(a_n) = 19.48$.
The full conditionals. The joint density of data and unknowns is, as a function of $(\mu, \tau)$, proportional to
$$\tau^{a_0 + (n+1)/2 - 1}\exp\Big\{-\tau\Big[b_0 + \tfrac12\sum_i(x_i - \mu)^2 + \tfrac12\kappa_0(\mu - \mu_0)^2\Big]\Big\}.$$
For fixed $\mu$ this is a gamma kernel in $\tau$: $\tau$ given $\mu$ is gamma with shape $a_0 + (n+1)/2 = 15$ and rate $b_0 + \tfrac12[\sum_i(x_i - \mu)^2 + \kappa_0(\mu - \mu_0)^2]$. For fixed $\tau$ the exponent is quadratic in $\mu$, and completing the square as in the conjugate-priors article gives $\mu$ given $\tau$ normal with mean $\mu_n$ and variance $1/(\kappa_n\tau)$. The Gibbs sampler alternates the two draws.
This posterior can be sampled exactly without a Markov chain: draw $\tau$ from its gamma marginal and then $\mu$ given $\tau$. The Gibbs sampler is run here because its answer can be compared with the exact one.
A trace. One chain started at $\mu = 200$ (seed 1, the fourth of four chains): the first draw of $\tau$ given $\mu = 200$ has the large rate that the distant mean produces, and gives $\sigma = 75.2$; the draw of $\mu$ given that $\tau$ is 136.4, already near the data. Then $\sigma = 22.6$ and $\mu = 132.8$, then $\sigma = 19.6$ and $\mu = 130.8$. Within three iterations the chain has forgotten its start.
Against the exact answer. We ran 30 seeds (1 to 30), each with four chains started at $\mu = 80, 100, 160$ and $200$, for 2,000 iterations, and kept the second 1,000 of each chain, 4,000 draws per run. Median over the 30 runs, with the interquartile range:
| Quantity | Exact | Gibbs sampler, median (IQR) |
|---|---|---|
| Posterior mean of $\mu$ | 128.36 | 128.36 (128.33 to 128.41) |
| Posterior standard deviation of $\mu$ | 3.86 | 3.86 (3.81 to 3.89) |
| 2.5% point of $\mu$ | 120.75 | 120.71 (120.62 to 120.92) |
| 97.5% point of $\mu$ | 135.97 | 135.92 (135.84 to 136.02) |
| Posterior mean of $\sigma$ | 19.48 | 19.47 (19.45 to 19.49) |
The effective sample size of the 4,000 draws of $\mu$, defined in the next section, had median 3,895 (IQR 3,791 to 3,991). Its true value is 4,000. Whatever $\tau$ the sampler has just drawn, the next $\mu$ is drawn with mean $\mu_n$, so the expectation of $\mu^{(t+1)}$ given everything before it is $\mu_n$, and every autocorrelation of the $\mu$-chain is exactly 0. (The draws are uncorrelated but not independent: the spread of the next $\mu$ depends on $\tau$, which was drawn given the previous $\mu$; a $\mu$ far from $\mu_n$ makes a small $\tau$, and so a widely spread next $\mu$, more likely, as Worked problem 3 shows.) The lag-1 sample autocorrelation of $\mu$ had median 0.006 over the 30 runs. The estimates fall a little short of 4,000, in 23 of the 30 runs below 4,000, because the estimator of the next section is biased slightly low when the true autocorrelations are 0: it always counts $\hat\rho_1$, and keeps adding pairs of lags while their estimated sum is positive, so it selects positive noise. Applied to 30 sets of independent standard normal draws of the same shape, four columns of 1,000 (seeds 2001 to 2030), it gave median 3,899 (IQR 3,755 to 4,007), with 21 of the 30 below 4,000: the Gibbs runs show the same small downward bias and nothing more. The largest split R-hat over the 30 runs was 1.002. The Monte Carlo standard error of the posterior mean, the posterior standard deviation divided by the square root of the effective sample size, had median 0.062. In 28 of the 30 runs the estimated mean was within two of its own Monte Carlo standard errors of the exact 128.36, against 28.6 expected ($30 \times 0.9545$) if the errors were normal with that standard deviation.
Measuring the error: autocorrelation and effective sample size
How precise is an average of correlated draws? If $\theta^{(1)}, \ldots, \theta^{(N)}$ were independent draws from the posterior, the average of $h(\theta^{(t)})$ would have variance $\operatorname{Var}_\pi(h)/N$. Draws from a chain are correlated, usually positively, and each new draw carries less new information.
Suppose the chain has reached stationarity, so that the sequence $h_t = h(\theta^{(t)})$ is a stationary series with variance $\sigma^2$ and autocorrelations $\rho_t$. The Bootstrap for Dependent Data, Theorem 1, proves that the mean $\bar h_N$ of $N$ consecutive values has variance
$$\operatorname{Var}(\bar h_N) = \frac{\sigma^2}{N}\Big[1 + 2\sum_{t=1}^{N-1}\Big(1 - \frac tN\Big)\rho_t\Big],$$
and that $N\operatorname{Var}(\bar h_N) \to \sigma^2(1 + 2\sum_{t\ge1}\rho_t)$ when the autocorrelations are absolutely summable: the variance (4) of the central limit theorem. The effective sample size is the number of independent draws that would give the same variance:
$$N_{\text{eff}} = \frac{N}{1 + 2\sum_{t=1}^{\infty}\rho_t}. \qquad (5)$$
This is the definition of Gelman et al. (2013, §11.5, eqs. 11.5 and 11.6), stated for the average as an estimate of the posterior mean. The Monte Carlo standard error of the average is then $\sqrt{\operatorname{Var}_\pi(h)/N_{\text{eff}}}$, estimated with the sample variance. Correlation among draws does not bias the average once the chain is stationary; it inflates its variance.
Estimating it. The autocorrelations must be estimated from the draws, and the estimates for large lags are noise. Gelman et al. (2013, §11.5) estimate them from $m$ sequences of length $n$ (after splitting each chain in half, as below) through the variogram at lag $t$,
$$V_t = \frac{1}{m(n - t)}\sum_{j=1}^m\sum_{i=t+1}^n\big(\psi_{ij} - \psi_{i-t,j}\big)^2,$$
with $\psi_{ij}$ the $i$-th draw of sequence $j$. Since $E(\psi_i - \psi_{i-t})^2 = 2(1 - \rho_t)\operatorname{Var}(\psi)$ under stationarity, they set $\hat\rho_t = 1 - V_t/(2\,\widehat{\operatorname{var}}^+)$ (their eq. 11.7), where $\widehat{\operatorname{var}}^+$ is the variance estimate of the next section. They sum $\hat\rho_t$ from lag 1 up to $T$, the first odd integer for which $\hat\rho_{T+1} + \hat\rho_{T+2}$ is negative, and estimate $\hat N_{\text{eff}} = mn/(1 + 2\sum_{t=1}^T\hat\rho_t)$ (eq. 11.8). Stopping at the first negative pair is a truncation that Vehtari et al. (2021, §3.2) attribute to Geyer (1992). Vehtari, Gelman, Simpson, Carpenter and Bürkner (2021, §3.2) explain it: for the Markov chains typically used in MCMC, the sum of the autocorrelations at two consecutive lags, starting from lag 0, is positive apart from estimation noise, so a negative estimated pair marks where noise has taken over. The script implements eq. 11.8 as stated.
A check where the answer is known. Let the target be a pair $(\theta_1, \theta_2)$ of standard normal variables with correlation $\rho = 0.9$, sampled by a systematic-scan Gibbs sampler. Worked problem 2 proves that the successive values of $\theta_1$ form an autoregressive series with $\rho_t = \rho^{2t}$, so that by (5)
$$N_{\text{eff}} = N\,\frac{1 - \rho^2}{1 + \rho^2},$$
a fraction 0.105 of the draws when $\rho = 0.9$. For four chains of 5,000 iterations, started from the stationary distribution, that is 2,099 of 20,000 draws. Over 30 seeds the estimate of eq. 11.8 had median 2,110 (interquartile range 1,991 to 2,155), and the lag-1 autocorrelation had median 0.811, against $\rho^2 = 0.81$.
Example (correlated draws are not wrong draws). A common reading of a high autocorrelation is that the draws are biased and should be thinned, keeping every $k$-th, until they look independent. Once the chain is stationary, every draw has the posterior distribution, and the average is unbiased whatever the correlation; what the correlation costs is variance, which (5) measures. Thinning makes the kept draws less correlated, but it discards draws that were already computed. In the correlated-pair check above, keeping every tenth of the 20,000 draws leaves 2,000 draws whose autocorrelations are $\rho^{20t}$, and by (5) their effective sample size is $2{,}000\,(1 - 0.81^{10})/(1 + 0.81^{10}) = 1{,}566$, against 2,099 for all the draws. Gelman et al. (2013, §11.4) thin only to save storage, in problems with many parameters.
Warm-up and the split R-hat
The averages above assumed a chain already at its stationary distribution. A chain started elsewhere spends its first iterations travelling toward the region where the posterior has its probability, and those iterations describe the start, not the posterior. Discarding them is called warm-up (the older term is burn-in). Gelman et al. (2013, §11.4) discard the first half of each chain by default, "as a conservative choice". Their footnote explains why they now say warm-up: burn-in "draws a misleading analogy to industrial processes in which products are stressed in order to reveal defects".
How long is long enough? No single chain can say, because a chain stuck in one region looks stable. The remedy is to run several chains from widely dispersed starting points and compare them. Gelman et al. (2013, §11.4) define the statistic as follows, for one scalar summary $\psi$ at a time. Discard the warm-up, split each remaining chain into its first and second halves, and let $m$ be the number of halves and $n$ their length; write $\psi_{ij}$ for draw $i$ of half $j$, $\bar\psi_{\cdot j}$ for the mean of half $j$ and $\bar\psi_{\cdot\cdot}$ for the mean of those means. Then
$$B = \frac{n}{m - 1}\sum_{j=1}^m\big(\bar\psi_{\cdot j} - \bar\psi_{\cdot\cdot}\big)^2, \qquad W = \frac1m\sum_{j=1}^m s_j^2, \qquad s_j^2 = \frac{1}{n - 1}\sum_{i=1}^n\big(\psi_{ij} - \bar\psi_{\cdot j}\big)^2,$$
$$\widehat{\operatorname{var}}^+ = \frac{n - 1}{n}W + \frac1nB, \qquad \hat R = \sqrt{\frac{\widehat{\operatorname{var}}^+}{W}} \qquad \text{(their eqs. 11.3 and 11.4).}$$
$B$ measures the variation between the halves and $W$ within them. If the halves have not mixed, $B$ is large and $\hat R$ is well above 1; as the chains converge it approaches 1. Splitting each chain catches a chain that is still drifting, whose two halves differ. The statistic descends, as Vehtari et al. (2021) describe, from the potential scale reduction factor of Gelman and Rubin (1992). Gelman et al. (2013, §11.5, p. 287) "generally have been satisfied with setting 1.1 as a threshold". Vehtari et al. (2021) propose computing it on rank-normalized draws, which works for heavy-tailed posteriors as well, and recommend using a sample only if $\hat R < 1.01$, with at least four chains and a rank-normalized effective sample size above 400. They write that the tighter threshold reflects "lessons learnt over more than 25 years of use". Worked problem 4 computes $\hat R$ by hand for two short chains.
The diagnostics on the logistic regression. The sampler of the next section was started 30 times (seeds 1001 to 1030), each time with four chains placed far out: at the posterior mode plus 30 times a draw from the Laplace approximation of the next section, scaled by its covariance. At the starts the log posterior was a median of 1,141 below its maximum. Each chain was counted as arrived when its log posterior first came within 10 of the maximum: after a median of 91 iterations, and at most 237. The split R-hat of the first 200 iterations, taking the largest over the three coefficients, had median 2.50 and was never below 1.51; it flags the unfinished warm-up at once. On iterations 1,001 to 2,000, after discarding the first half, its median was 1.010 and its largest value 1.033. Seventeen of the 30 runs were above 1.01 although every chain had arrived hundreds of iterations earlier. Four chains of 1,000 correlated draws are too few for the statistic to settle that close to 1, which is why Vehtari et al. (2021) ask for an effective sample size of at least 400 before $\hat R$ is trusted. With 4,000 kept iterations per chain, in the next section, the largest value at the best step size was 1.006.
A posterior without a closed form: logistic regression
Back to the opening problem. For the 5,107 adults, with $y_i = 1$ for diagnosed diabetes, the model of Link Functions makes $y_i$ Bernoulli with
$$\ln\frac{P(y_i = 1)}{P(y_i = 0)} = \beta_0 + \beta_1\,\text{age}_i + \beta_2\,\text{obese}_i,$$
age in years and obese 1 for a body mass index of 30 or more. The prior makes the three coefficients independent and normal with mean 0 and standard deviation 10, which is weak on the scale of these coefficients. The log posterior, up to a constant, is
$$\ln\pi(\beta \mid \mathbf{y}) = \sum_i\big[y_i\eta_i - \ln(1 + e^{\eta_i})\big] - \frac{1}{2 \times 10^2}\sum_j\beta_j^2 + \text{const}, \qquad \eta_i = \beta_0 + \beta_1\,\text{age}_i + \beta_2\,\text{obese}_i.$$
Three reference answers. The maximum likelihood estimate, as in the Generalized Linear Models unit, is $(-5.2876, 0.05695, 0.8051)$. The posterior mode, found by Newton's method on the log posterior, is $(-5.2857, 0.05693, 0.8047)$: the prior pulls it only in the fourth significant figure. The Laplace approximation is the normal distribution centered at the mode whose covariance is the inverse of minus the matrix of second derivatives of the log posterior there; Bayes Factors and Posterior Model Probabilities derives Laplace's method. Its standard deviations are 0.1870, 0.00281 and 0.0840, and its correlations are −0.947 between the intercept and the age coefficient, −0.357 between the intercept and the obesity coefficient, and 0.135 between age and obesity. The intercept and the age slope are strongly tied because age is measured from 0: a steeper slope has to be balanced by a lower intercept to fit adults whose ages center near 50.
For a third answer we computed the posterior itself by quadrature. In coordinates $\mathbf{z}$ with $\beta = \hat\beta + L\mathbf{z}$, where $\hat\beta$ is the mode and $LL^{\mathsf T}$ the Laplace covariance, a grid of step 0.25 from $-6$ to 6 in each coordinate has $49^3 = 117{,}649$ points. The posterior was evaluated at each and the rectangle rule applied. Repeating with a grid of step 0.35 from $-7$ to 7 changed no mean or standard deviation by more than $10^{-6}$ of a posterior standard deviation. The grid gives posterior means $(-5.2929, 0.05701, 0.8057)$ and standard deviations $(0.1872, 0.00281, 0.0840)$. The posterior means differ from the mode by 0.038, 0.030 and 0.011 posterior standard deviation, and the central 95% interval for the obesity coefficient is (0.641, 0.971), against (0.640, 0.969) from the Laplace approximation. The posterior is very nearly normal, as expected with 5,107 observations and 3 coefficients. The odds ratio for obesity at a given age, evaluated at the posterior mean of its coefficient, is $e^{0.8057} = 2.24$; the posterior mean of the odds ratio itself, $E[e^{\beta_2} \mid \mathbf{y}]$ from the same grid, is 2.25, larger because the exponential is convex.
So here the sampler is not needed, and that is the point: its answers can be checked. With 30 coefficients instead of 3, a grid with 49 points per coordinate would need $49^{30}$ evaluations, and the sampler's cost would grow only with the number of iterations needed and the cost of one evaluation.
How large a step
The sampler is random-walk Metropolis: from $\beta$, propose $\beta' = \beta + cL\mathbf{u}$ with $\mathbf{u}$ three independent standard normal variables, a normal proposal centered at the current point with covariance $c^2$ times the Laplace covariance. The proposal is symmetric, so the acceptance probability is $\min\{1, \pi(\beta' \mid \mathbf{y})/\pi(\beta \mid \mathbf{y})\}$. The one free choice is the scale $c$.
Small steps are nearly always accepted but move little, and the chain explores by a slow random walk. Large steps leap far but land in the tails and are rejected, and the chain stands still. Somewhere between is a best $c$. Theory gives a guide. For a target whose $d$ coordinates are independent with a common smooth density, Roberts, Gelman and Gilks (1997) showed, in the account of Roberts and Rosenthal (2004, §6.1), that as $d \to \infty$ the most efficient random-walk proposal has an asymptotic acceptance rate of 0.234. For a normal target and a normal proposal shaped like it, Gelman et al. (2013, §12.2) give the optimal scale as about $2.4/\sqrt d$, an efficiency relative to independent draws of about $0.3/d$, and an acceptance rate "around 0.44 in one dimension, declining to about 0.23 in high dimensions (roughly d > 5)". For $d = 3$ the suggested scale is $2.4/\sqrt3 = 1.39$.
The experiment. For each of eight values of $c$ we ran 30 seeds (1 to 30), each with four chains started at the mode plus twice a draw from the Laplace approximation, for 5,000 iterations, and kept the last 4,000 of each chain: 16,000 draws per run. The same random numbers were used for every $c$, so the comparisons are paired. For each run we computed the acceptance rate and the effective sample size of each coefficient by eq. 11.8, and report the smallest of the three. Median over the 30 runs, with the interquartile range:
| $c$ | Acceptance rate | Smallest effective sample size | Effective sample size, obesity coefficient |
|---|---|---|---|
| 0.10 | 0.937 (0.935 to 0.938) | 28 (21 to 34) | 39 |
| 0.30 | 0.812 (0.810 to 0.814) | 238 (208 to 265) | 270 |
| 0.60 | 0.640 (0.637 to 0.643) | 707 (671 to 754) | 745 |
| 1.00 | 0.451 (0.448 to 0.453) | 1,213 (1,102 to 1,279) | 1,281 |
| 1.39 | 0.319 (0.314 to 0.320) | 1,375 (1,336 to 1,485) | 1,488 |
| 2.00 | 0.186 (0.181 to 0.186) | 1,225 (1,044 to 1,281) | 1,304 |
| 3.00 | 0.081 (0.079 to 0.084) | 605 (549 to 665) | 667 |
| 5.00 | 0.022 (0.021 to 0.024) | 157 (120 to 190) | 192 |
The best of the eight scales was $c = 1.39$, the value of the rule $2.4/\sqrt d$, with an acceptance rate of 0.319, between the one-dimensional 0.44 and the high-dimensional 0.23; its 16,000 draws were worth about 1,375 independent ones, an efficiency of 0.086, against the $0.3/d = 0.1$ of the normal theory. The efficiency is flat near the optimum: anything from $c = 1$ to $c = 2$, with acceptance from 0.45 to 0.19, lost less than 12% of it. Far from the optimum it collapses in both directions. Each coefficient's estimated mean was within two Monte Carlo standard errors of the grid's mean in 87 of the 90 cases at $c = 1.39$ (three coefficients in 30 runs; 85.9 expected), so the error estimates were honest. The largest split R-hat at any scale from 0.6 up was 1.040; at $c = 0.1$ it reached 1.275.
Example (a high acceptance rate is not a sign of a good sampler). "Most of my proposals are accepted, so the chain is mixing well" is a natural reading and the wrong one. At $c = 0.1$ the acceptance rate was 0.937, and the chains were worth about 28 independent draws out of 16,000. The steps were so small that the chain crept through the posterior. Acceptance measures how often the chain moves, not how far.
The shape of the proposal. The runs above used the Laplace covariance to shape the proposal. Without it, a proposal with the same standard deviation $s$ in every coordinate has to be small enough for the narrowest direction of the posterior. The age coefficient has posterior standard deviation 0.00281 and the intercept 0.187, and their correlation of −0.947 makes the narrowest direction narrower still. With the same seeds, starts and lengths (medians over the 30 runs):
| $s$ | Acceptance rate | Effective sample size: intercept, age, obesity | Largest split R-hat |
|---|---|---|---|
| 0.003 | 0.266 | 4, 4, 4 | 10.63 |
| 0.01 | 0.084 | 4, 5, 7 | 4.70 |
| 0.03 | 0.027 | 5, 6, 9 | 2.54 |
At $s = 0.003$ the acceptance rate, 0.266, is near the textbook target, yet the four chains of each run, started apart, never came together in 5,000 iterations: the median of the largest split R-hat was 10.63, and the effective sample sizes of 4 are what eq. 11.8 returns for sequences that disagree. The diagnostics did their job here, and no estimate from these runs should be used. A larger $s$ moves the long direction faster but is rejected more, and none of the three came near the shaped proposal. Bishop (2006, §11.2.2) describes the mechanism: the scale must be of the order of the smallest length scale of the target, and the chain then explores the long directions by a random walk whose number of steps grows like the square of the ratio of the largest to the smallest scale. Shaping the proposal like the posterior, or reparametrizing so that the posterior is round, removes that ratio.
What is proved, what is cited, what the experiment shows
Proved on this page: that the composition and mixture of kernels with a common stationary distribution keep it (Lemma 1); that detailed balance implies stationarity for kernels with a density of moves and a probability of staying (Theorem 1); that the Metropolis–Hastings kernel satisfies detailed balance for any target and proposal (Theorem 2); that a Gibbs update is a Metropolis–Hastings move with acceptance probability 1, is reversible and leaves the target stationary, so that both scans do (Theorem 3); the failure of detailed balance for a systematic scan, in exact fractions; the full conditionals of the normal model; the effective sample size of the Gibbs sampler for a correlated normal pair (Worked problem 2); the exact behavior of the three-state chain (Worked problem 1).
Used from other pages: the variance of the mean of a stationary series and its limit (The Bootstrap for Dependent Data, Theorem 1); the normal–inverse-gamma posterior (Priors, Posteriors and Conjugate Families, Theorem 7); Laplace's method (Bayes Factors and Posterior Model Probabilities); Markov chains on finitely many states and their convergence with positive transition probabilities (PageRank, Latent Dirichlet Allocation); Tonelli's theorem, cited by the Probability Theory unit.
Cited, not proved: convergence in total variation and the strong law of large numbers for $\phi$-irreducible aperiodic chains (Roberts and Rosenthal, 2004, Theorem 4 and Fact 5, the latter from Meyn and Tweedie, 1993); the irreducibility and aperiodicity of Metropolis–Hastings with positive continuous proposals (Roberts and Rosenthal, 2004, §3.2); the central limit theorems for Markov chains and the formula for their variance (their Theorems 23 to 25), and their counterexample (Theorem 22); the optimal scaling results (Roberts, Gelman and Gilks, 1997, as reported by Roberts and Rosenthal, 2004, §6.1; Gelman et al., 2013, §12.2); the definitions of warm-up, effective sample size and split R-hat (Gelman et al., 2013, §§11.4 and 11.5), the truncation that Vehtari et al. (2021) attribute to Geyer (1992), and the recommendations of Vehtari et al. (2021). The origin of the algorithms is attributed to Metropolis et al. (1953) and Hastings (1970) as Bishop (2006) attributes it, and the origin of R-hat and of the truncation to Gelman and Rubin (1992) and Geyer (1992) as Vehtari et al. (2021) attribute them; we did not read those four papers.
Observed in the experiments: the Gibbs sampler reproduced the exact posterior of the normal model within its Monte Carlo error in 28 of 30 runs; the estimated effective sample size matched the exact one for the correlated pair; for the logistic regression the efficiency of random-walk Metropolis was highest among the eight scales tried at $c = 1.39$, near $2.4/\sqrt d$, with acceptance 0.319 (the neighboring scales 1.0 and 2.0 were within 12% of it), fell steeply farther out, and collapsed with a round proposal; R-hat flagged unfinished warm-up and unmixed chains, and was noisy above 1.01 with 4,000 draws. These are results for two posteriors, one with three coefficients. Every number on this page is produced by tools/experiments/statistics/markov-chain-monte-carlo.py.
Worked problems
These problems are posed for this article on small exact cases and on the unit's data; the unit has no course assignments. The script recomputes every number, the first and last in exact fractions.
Problem 1 (Metropolis–Hastings on three states). The target gives states 1, 2 and 3 the probabilities $1/6$, $2/6$ and $3/6$. The proposal picks one of the two other states, each with probability $1/2$. Find the transition matrix, check detailed balance and stationarity, and find how fast the chain started at state 1 approaches the target.
Solution. The proposal is symmetric, so a move from $i$ to $j$ is proposed with probability $1/2$ and accepted with probability $\min\{1, \pi_j/\pi_i\}$. From state 1 every move is uphill: $P_{12} = P_{13} = 0.500$ and $P_{11} = 0$. From state 2, a move to 1 is accepted with probability $1/2$, so $P_{21} = 1/4$; a move to 3 always, $P_{23} = 1/2$; and $P_{22} = 1/4$. From state 3, $P_{31} = \frac12 \cdot \frac13 = 1/6$, $P_{32} = \frac12 \cdot \frac23 = 1/3$ and $P_{33} = 1/2$. Detailed balance: $\pi_1P_{12} = \frac16 \cdot \frac12 = \frac1{12} = \frac26 \cdot \frac14 = \pi_2P_{21}$; $\pi_1P_{13} = \frac1{12} = \frac36 \cdot \frac16 = \pi_3P_{31}$; $\pi_2P_{23} = \frac16 = \frac36 \cdot \frac13 = \pi_3P_{32}$. Summing columns, $\sum_i\pi_iP_{i1} = 0 + \frac1{12} + \frac1{12} = \frac16$, and likewise for the others, as Theorem 1 says. In equilibrium the chain moves with probability $\frac16 \cdot 1 + \frac26 \cdot \frac34 + \frac36 \cdot \frac12 = 2/3$ per step.
For the approach, the matrix has eigenvalues 1, $-1/4$ and 0, with left eigenvectors $\pi$, $(1, -1, 0)$ and $(-1, -2, 3)$; the last two are checked by multiplying them by $P$. The deviation of the starting distribution from the target is $(1, 0, 0) - \pi = (\frac56, -\frac13, -\frac12) = \frac23(1, -1, 0) - \frac16(-1, -2, 3)$. After $n \ge 1$ steps the second part has been multiplied by $0^n = 0$ and the first by $(-\frac14)^n$, so the distribution is $\pi + \frac23(-\frac14)^n(1, -1, 0)$. The total variation distance, half the sum of the absolute deviations, is $\frac23(\frac14)^n = \frac16(\frac14)^{n-1}$: 0.167 after one step, 0.042 after two, and a factor of 4 smaller with every further step. The sign alternates: state 1's probability is below its share $1/6$ after odd numbers of steps and above it after even numbers (0 after one step, $5/24$ after two).
Problem 2 (the Gibbs sampler for a correlated pair). Let $(\theta_1, \theta_2)$ be standard normal with correlation $\rho$, sampled by a systematic scan that draws $\theta_2$ given $\theta_1$ and then $\theta_1$ given $\theta_2$. Show that the successive values of $\theta_1$ form a stationary autoregressive series with autocorrelations $\rho^{2t}$, and find its effective sample size.
Solution. For a standard bivariate normal, $\theta_2$ given $\theta_1$ is normal with mean $\rho\theta_1$ and variance $1 - \rho^2$, and symmetrically. So one sweep gives $\theta_2' = \rho\theta_1 + \sqrt{1 - \rho^2}\,e$ and $\theta_1' = \rho\theta_2' + \sqrt{1 - \rho^2}\,e'$, with $e$ and $e'$ independent standard normal, independent of the past. Substituting, $\theta_1' = \rho^2\theta_1 + \varepsilon$ with $\varepsilon = \rho\sqrt{1 - \rho^2}\,e + \sqrt{1 - \rho^2}\,e'$, whose variance is $\rho^2(1 - \rho^2) + (1 - \rho^2) = 1 - \rho^4$. If $\theta_1$ has variance 1, $\theta_1'$ has variance $\rho^4 + 1 - \rho^4 = 1$, so the series is stationary when started from the target. Repeating, $\theta_1^{(t)} = \rho^{2t}\theta_1^{(0)} + (\text{terms independent of } \theta_1^{(0)})$, so the correlation at lag $t$ is $\rho^{2t}$. Then $1 + 2\sum_{t\ge1}\rho^{2t} = 1 + 2\rho^2/(1 - \rho^2) = (1 + \rho^2)/(1 - \rho^2)$, and by (5) $N_{\text{eff}} = N(1 - \rho^2)/(1 + \rho^2)$. For $\rho = 0.9$ this is 0.105 of the draws; the script's runs are in the section on effective sample size. The slow mixing comes from the correlation, not from the sampler's moves, each of which is an exact draw: with $\rho$ near 1, each conditional is narrow and a sweep moves the pair only a short way along the long axis. Variational Inference (Worked problem 3) finds the same factor $\rho^2$ as the rate of coordinate ascent on this target.
Problem 3 (a full conditional at the posterior mean). For the 25 blood pressures, find the full conditional of $\tau$ when $\mu = \mu_n$, and compare it with the marginal posterior of $\tau$.
Solution. By the section on Gibbs sampling, $\tau$ given $\mu$ is gamma with shape $a_0 + (n+1)/2 = 15$ and rate $b_0 + \tfrac12[\sum_i(x_i - \mu)^2 + \kappa_0(\mu - \mu_0)^2]$. With $\sum_i(x_i - \mu)^2 = S + n(\bar x - \mu)^2$, at $\mu = \mu_n = 128.36$ the bracket is $8{,}763.1 + 2.79 + 69.87 = 8{,}835.8$: here $n(\bar x - \mu_n)^2 = 25 \times (128.69 - 128.36)^2$ and $\kappa_0(\mu_n - \mu_0)^2 = (128.36 - 120)^2$, computed from unrounded values. The rate is $800 + 4{,}417.9 = 5{,}217.9$, which is $b_n$ exactly. That is no accident: by identity (4) of Priors, Posteriors and Conjugate Families, $n(\bar x - \mu)^2 + \kappa_0(\mu - \mu_0)^2 = \kappa_n(\mu - \mu_n)^2 + \kappa_0n(\bar x - \mu_0)^2/\kappa_n$, which at $\mu = \mu_n$ leaves exactly the term in $b_n$. So at the posterior mean of $\mu$ the conditional of $\tau$ has the marginal's rate and a shape larger by $1/2$: knowing $\mu$ exactly adds half an observation's worth of information about $\tau$. Away from $\mu_n$ the rate grows by $\kappa_n(\mu - \mu_n)^2/2$, so a sampler that strays in $\mu$ draws smaller precisions, which make the next draw of $\mu$, centered at $\mu_n$ as always, more spread out.
Problem 4 (split R-hat by hand). Two chains, after warm-up, are $(1, 2, 3, 4)$ and $(3, 4, 5, 6)$. Compute the split R-hat.
Solution. Splitting gives $m = 4$ sequences of length $n = 2$: $(1, 2)$, $(3, 4)$, $(3, 4)$ and $(5, 6)$, with means 1.5, 3.5, 3.5 and 5.5 and grand mean 3.5. Then $B = \frac{2}{3}[(-2)^2 + 0 + 0 + 2^2] = 16/3$. Each sequence has variance $s_j^2 = [(-0.5)^2 + 0.5^2]/1 = 1/2$, so $W = 1/2$. Then $\widehat{\operatorname{var}}^+ = \frac12 \cdot \frac12 + \frac12 \cdot \frac{16}{3} = \frac{35}{12}$ and $\hat R = \sqrt{(35/12)/(1/2)} = \sqrt{35/6} = 2.42$. The chains disagree about where the distribution is, and each also drifts, so the halves differ in both ways. Unsplit, the two chains have means 2.5 and 4.5 and variances $5/3$ each, giving $B = 4 \times 2 = 8$, $W = 5/3$, $\widehat{\operatorname{var}}^+ = \frac34 \cdot \frac53 + \frac84 = \frac{13}{4}$ and $\hat R = \sqrt{39/20} = 1.40$: splitting exposes the drift within each chain, which raises the statistic.
Summary
- A kernel satisfies detailed balance with respect to $\pi$ if $\pi(\theta)k(\theta, \theta') = \pi(\theta')k(\theta', \theta)$; then $\pi$ is stationary (Theorem 1). Compositions and mixtures of kernels keep a common stationary distribution (Lemma 1).
- Metropolis–Hastings proposes $\theta' \sim q(\theta, \cdot)$ and accepts with probability $\min\{1, \pi(\theta')q(\theta', \theta)/[\pi(\theta)q(\theta, \theta')]\}$. It satisfies detailed balance for any proposal and needs the target only up to a constant (Theorem 2).
- A Gibbs update draws one block from its full conditional; it is Metropolis–Hastings with acceptance probability 1 and is reversible. A systematic scan keeps the target stationary but need not be reversible (Theorem 3).
- Irreducibility and aperiodicity give convergence in total variation and a law of large numbers; geometric ergodicity with moment conditions gives a central limit theorem with variance $\operatorname{Var}_\pi(h)(1 + 2\sum\rho_t)$ (cited).
- Effective sample size $N/(1 + 2\sum\rho_t)$ and split R-hat measure the precision and the convergence, estimated as Gelman et al. (2013, eqs. 11.3, 11.4, 11.8) define them.
- On the logistic regression, random-walk Metropolis was most efficient, of the eight scales tried, at $c = 1.39$, near $2.4/\sqrt d$ (acceptance 0.319, 1,375 effective draws of 16,000), and an unshaped proposal never mixed.
What we have learned
A posterior that can be evaluated only up to a constant can still be sampled, because the Metropolis–Hastings rule balances the flow between every pair of points and needs only ratios. The guarantee is about the long run. Detailed balance makes the posterior stationary, and the cited ergodic theorems make the chain approach it and its averages converge. How long the run must be is a separate question, answered empirically by the effective sample size and by agreement between chains. On the blood pressures the Gibbs sampler reproduced the exact posterior within its stated error. On the logistic regression the same posterior was reached at very different costs: the best proposal turned 16,000 draws into about 1,375 independent ones, a poorly scaled one into 28, and a proposal that ignored the posterior's shape into chains that never met.
Sampling buys accuracy with computation, and its error shrinks as the run grows. Variational Inference makes the other trade: it replaces the posterior by the closest member of a simpler family, found by optimization, with an error that does not shrink, and on the same normal model it reports a spread for the mean that every one of our Gibbs runs exceeded.
References
- Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Sections 11.2 and 11.3. record · 10 pages
- Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A., and Rubin, D. B. (2013). Bayesian Data Analysis (3rd ed.). CRC Press. Sections 11.4, 11.5 and 12.2. record · 7 pages
- Gelman, A., and Rubin, D. B. (1992). Inference from iterative simulation using multiple sequences. Statistical Science, 7(4), 457–472. https://doi.org/10.1214/ss/1177011136 record
- Geman, S., and Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6), 721–741. record · 3 pages
- Geyer, C. J. (1992). Practical Markov chain Monte Carlo. Statistical Science, 7(4), 473–483. https://doi.org/10.1214/ss/1177011137 record
- Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), 97–109. https://doi.org/10.1093/biomet/57.1.97 record
- Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6), 1087–1092. https://doi.org/10.1063/1.1699114 record · 2 pages
- Meyn, S. P., and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Springer. record
- National Center for Health Statistics (2020). National Health and Nutrition Examination Survey 2017–2018: DEMO_J, BPX_J, BPQ_J, BMX_J, DIQ_J and SMQ_J data files and documentation. Centers for Disease Control and Prevention. https://wwwn.cdc.gov/nchs/nhanes/continuousnhanes/default.aspx?BeginYear=2017 record · 95 pages
- Roberts, G. O., Gelman, A., and Gilks, W. R. (1997). Weak convergence and optimal scaling of random walk Metropolis algorithms. The Annals of Applied Probability, 7(1), 110–120. https://doi.org/10.1214/aoap/1034625254 record
- Roberts, G. O., and Rosenthal, J. S. (2004). General state space Markov chains and MCMC algorithms. Probability Surveys, 1, 20–71. https://doi.org/10.1214/154957804100000024 record
- Vehtari, A., Gelman, A., Simpson, D., Carpenter, B., and Bürkner, P.-C. (2021). Rank-normalization, folding, and localization: An improved $\widehat{R}$ for assessing convergence of MCMC. Bayesian Analysis, 16(2), 667–718. https://doi.org/10.1214/20-BA1221 record