Initialization, Burn-In, and Warmup

Three Different Jobs

Starting an MCMC computation involves choices that are related but not interchangeable. Initialization selects one or more starting states. Burn-in means discarding an initial segment of the chain before estimating target quantities. Warmup is a period in which algorithm settings may be adapted, for example by tuning a proposal scale. Discarding iterations is a data-handling decision; it is not a mechanism that makes an invalid or non-exploring transition rule valid.

Let $(X_n)_{n\ge0}$ be a Markov chain on a finite state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. Its filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. Let $\pi$ be the target distribution, written as a row vector. For the fixed-kernel discussion, assume $\pi P=\pi$; this invariance equation alone does not guarantee that the chain will reach every part of the target from every starting state.

Definition: An initialization is the distribution $\mu_0$ of $X_0$, or a specified starting state. A burn-in of length $b$ discards $X_0,\ldots,X_{b-1}$ and begins estimation with $X_b$. Adaptive warmup is a period during which the transition rule or its tuning parameters can depend on the history. Once adaptation stops and a fixed kernel is used, the resulting production chain can be analyzed as a Markov chain with that kernel.

A dispersed initialization uses multiple starting states chosen to cover meaningfully different regions of the target. It can reveal sensitivity to starting location: if chains started in different regions continue to behave differently, that is evidence against trusting a single run. But dispersed starts do not prove convergence. In particular, a collection of starts can all miss a region, or a transition rule can make a region inaccessible.

For a fixed kernel, the relevant question after discarding $b$ steps is how close the distribution of $X_b$ is to $\pi$. Define total variation distance on a finite state space by $\|\mu-\pi\|_{\mathrm{TV}}=\sup_{A\subseteq S}|\mu(A)-\pi(A)|$. A small distance controls the bias of bounded function estimates at that time, but does not on its own provide a universal burn-in length.

What Burn-In Can and Cannot Guarantee

Proposition (finite-time burn-in bound): Suppose $P$ has stationary distribution $\pi$, and $X_0\sim\mu_0$. For any $b\ge0$, the distribution of $X_b$ is $\mu_0P^b$. For any function $f:S\to\mathbb{R}$ with $\|f\|_\infty=\max_{i\in S}|f(i)|<\infty$, $$ \left|\mathbb{E}[f(X_b)]-\sum_{i\in S}\pi_i f(i)\right| \le 2\|f\|_\infty\|\mu_0P^b-\pi\|_{\mathrm{TV}}. $$ Thus, if a bound on the distance to stationarity is available, it gives a bound on the bias of the single-time estimate $f(X_b)$.

Proof. The Markov property and the row-vector convention give the distribution of $X_b$ as $\mu_0P^b$. Set $\nu=\mu_0P^b-\pi$. Since both distributions have total mass one, $\sum_i\nu_i=0$. Let $A_+=\{i:\nu_i\ge0\}$. The sum of the positive entries of $\nu$ equals the absolute sum of its negative entries, and both equal $\|\mu_0P^b-\pi\|_{\mathrm{TV}}$: on a finite set, the supremum over subsets is attained by the set of positive entries. Therefore \[ \left|\sum_i \nu_i f(i)\right| \le \|f\|_\infty\sum_i|\nu_i| =2\|f\|_\infty\|\mu_0P^b-\pi\|_{\mathrm{TV}}. \] The left side is the stated difference of expectations. $\square$

This bound concerns a particular time $b$. For estimates averaged over many dependent draws, additional conditions are needed. A standard finite-state Markov-chain convergence theorem says that if $P$ is irreducible and aperiodic, then it has a unique stationary distribution and $\|\mu_0P^n-\pi\|_{\mathrm{TV}}\to0$ for every initial distribution $\mu_0$. The corresponding ergodic theorem says that for any $f:S\to\mathbb{R}$, the time average of $f(X_n)$ converges almost surely to $\sum_i\pi_i f(i)$, from every initial state. These are standard results from finite-state Markov-chain convergence. Neither result supplies a universal finite $b$ that makes the remaining error zero, or even small without further quantitative information.

In particular, burn-in does not change the transition matrix. If the chain stays forever in a proper subset of the target space, no finite or infinite initial discard can make the later draws represent the full target.

Proposition (a closed class cannot be repaired by burn-in): Let $C$ be a nonempty proper subset of $S$ such that $p_{ij}=0$ whenever $i\in C$ and $j\notin C$. If $X_0\in C$ almost surely, then $X_n\in C$ almost surely for every $n$. If $\pi(C)<1$, the distribution of every $X_n$ remains at total variation distance at least $1-\pi(C)$ from $\pi$.

Proof. The claim holds at $n=0$ by assumption. If $X_n\in C$, then the probability of moving outside $C$ is $\sum_{j\notin C}p_{X_nj}=0$. Hence $X_{n+1}\in C$ almost surely. Induction gives the first claim for every $n$. For the second, take $A=C$ in the definition of total variation. The law of $X_n$ assigns probability one to $C$, so its distance from $\pi$ is at least $|1-\pi(C)|=1-\pi(C)$. $\square$

Worked Examples

Worked Example: A Burn-In Bound Is Not Exact Stationarity

Consider $S=\{0,1\}$ and $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}. $$ Each row sums to $\tfrac34+\tfrac14=1$, so this is a transition matrix. The distribution $\pi=(\tfrac12,\tfrac12)$ is stationary: its first coordinate after one transition is $\tfrac12\cdot\tfrac34+\tfrac12\cdot\tfrac14=\tfrac12$, and its second coordinate is $\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac34=\tfrac12$.

Start at $X_0=0$. If $a_n=\mathbb{P}(X_n=0)$, then $a_{n+1}=\tfrac34a_n+\tfrac14(1-a_n)=\tfrac12+\tfrac12(a_n-\tfrac12)$. Since $a_0=1$, repeated substitution gives $a_n=\tfrac12+\tfrac12(\tfrac12)^n$. For $b=3$, $a_3=\tfrac12+\tfrac12\cdot\tfrac18=\tfrac12+\tfrac1{16}=\tfrac9{16}$. Thus the total variation distance at time 3 is $|\tfrac9{16}-\tfrac12|=\tfrac1{16}$. For $f(i)=\mathbf{1}_{\{0\}}(i)$, the expectation is $\tfrac9{16}$ while the target expectation is $\tfrac12$, so the bias is $\tfrac1{16}$.

Check: The recurrence gives $a_1=\tfrac34$, $a_2=\tfrac12+\tfrac12(\tfrac14)=\tfrac58$, and $a_3=\tfrac12+\tfrac12(\tfrac18)=\tfrac9{16}$, consistent with the formula. Three discarded transitions reduce the initial discrepancy, but do not make the distribution exactly stationary.

Worked Example: Dispersed Starts Do Not Fix Inaccessible Modes

Let $S=\{1,2,3,4\}$, with $$ P=\begin{bmatrix} \tfrac34&\tfrac14&0&0\\ \tfrac14&\tfrac34&0&0\\ 0&0&\tfrac34&\tfrac14\\ 0&0&\tfrac14&\tfrac34 \end{bmatrix}. $$ Every row sums to $\tfrac34+\tfrac14=1$. The uniform distribution $\pi=(\tfrac14,\tfrac14,\tfrac14,\tfrac14)$ is stationary: for each column, the two nonzero contributions are $\tfrac14\cdot\tfrac34+\tfrac14\cdot\tfrac14=\tfrac14$. The set $C=\{1,2\}$ is closed.

Start a chain at state 1. It remains in $C$, so $\mathbb{P}(X_n\in C)=1$ at every $n$, whereas $\pi(C)=\tfrac14+\tfrac14=\tfrac12$. Taking $A=C$ shows that the total variation distance from $\pi$ is at least $1-\tfrac12=\tfrac12$ at every time. For the target quantity $f(i)=\mathbf{1}_{\{1,2\}}(i)$, every observed value is 1, while its target expectation is $\tfrac12$.

Check: The row sums are all 1, and the stationary probability of $C$ is $\tfrac12$; the chain started in $C$ assigns probability 1 to $C$ after any number of transitions. Starting another chain in $\{3,4\}$ is more dispersed, but each chain still remains in its own closed set. Discarding any number of initial draws cannot resolve this failure of exploration.

Worked Example: Freeze Adaptation Before Production

Take target $\pi=(\tfrac12,\tfrac12)$ on $S=\{0,1\}$. During a one-step warmup, use the kernel $$ K=\begin{bmatrix}1&0\\1&0\end{bmatrix}. $$ Each row sums to 1, but $\pi K=(1,0)\ne\pi$, so this warmup kernel does not preserve the target. Start at $X_0=1$; after the warmup transition, $X_1=0$ with probability 1. Then freeze adaptation and use the production kernel $$ P=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}, $$ whose rows sum to 1 and whose stationary distribution is $\pi$, as checked in the preceding example.

Suppose, incorrectly, that the warmup value $X_1$ is included with the first production value $X_2$ to estimate $\pi(\{0\})$. From $X_1=0$, the production transition gives $\mathbb{P}(X_2=0)=\tfrac34$. Therefore $\mathbb{E}[(\mathbf{1}_{\{0\}}(X_1)+\mathbf{1}_{\{0\}}(X_2))/2]=(1+\tfrac34)/2=\tfrac78$, rather than the target value $\tfrac12$. The warmup draw reflects a non-target-preserving kernel, and the first production draw still reflects a nonstationary starting state.

If $r$ production transitions have occurred since $X_1=0$, the same recurrence as in the first example gives $\mathbb{P}(X_{1+r}=0)=\tfrac12+\tfrac12(\tfrac12)^r$. This tends to $\tfrac12$, but is not equal to $\tfrac12$ for any finite $r$. A practical procedure is to use warmup output to choose settings, freeze those settings, and then assess whether the fixed production kernel explores and targets $\pi$. Discarding warmup is appropriate when it is not generated under the final sampling procedure; it is not, by itself, a proof that the production output is reliable.

Check: At $r=1$, the formula gives $\tfrac12+\tfrac12\cdot\tfrac12=\tfrac34$, matching the production transition from 0. At $r=0$, it gives 1, matching the warmup endpoint.

Which Draws May Be Used?

For a fixed, target-invariant kernel that is irreducible and aperiodic on a finite state space, the post-warmup chain satisfies the finite-state convergence and ergodic results stated above. Under those conditions, a finite initial segment may be discarded, and the average of a sufficiently long production run estimates target expectations asymptotically. If the chain is initialized exactly from $\pi$, every fixed-kernel draw has marginal distribution $\pi$, though draws are generally dependent. Exact initialization is uncommon in applications.

If adaptation continues during the values used for estimation, the output is generally not a homogeneous Markov chain with one fixed transition matrix. Validity then requires specific theory for the adaptive algorithm; it does not follow merely from calling an interval “warmup.” Conditions such as diminishing adaptation and containment are used in standard adaptive-MCMC results, but their hypotheses are algorithm-specific and their proofs are beyond this tutorial. A safer basic design is a finite adaptation phase followed by a frozen kernel, then production sampling under that kernel.

Nor is “discard the first 10%” or any other universal fraction a convergence theorem. The amount of transient bias depends on the kernel, starting distribution, and quantity being estimated. Diagnostics can expose persistent dependence on initialization or poor exploration, but passing diagnostics does not prove that every relevant region has been visited. In particular, a chain trapped in one mode can produce a stable-looking trace and a precise estimate of the wrong conditional region.

Common mistake. A tempting calculation is: “The chain has run for $b$ steps, so the retained chain starts from $\pi$.” This substitutes $\mu_0P^b=\pi$ without justification. In the two-state example, taking $b=3$ actually gives $\mathbb{P}(X_3=0)=\tfrac9{16}$, not $\tfrac12$. The correction is to treat burn-in as a possible reduction of initialization effects, establish appropriate convergence conditions, and avoid claiming exact stationarity from a chosen discard length alone.

Practical rule: Use warmup draws to tune only when the adaptation is part of a justified adaptive procedure; otherwise freeze the kernel before the estimation phase. Use post-freeze draws for estimation only when the frozen kernel has the desired target and can explore it. Discarding early draws can reduce transient effects under those conditions, but cannot repair a wrong target, an inaccessible mode, or a non-ergodic transition rule.

Check Your Understanding

Answer each question by identifying the assumptions that matter, not only by naming a procedure.

For a fixed kernel with stationary distribution $\pi$, what does the finite-time burn-in bound control, and what does it not guarantee about an averaged estimate?
Why does a chain started in a closed proper subset $C$ fail to estimate a target with $\pi(C)<1$, regardless of burn-in length?
In the adaptive warmup example, why is including $X_1$ in the estimate problematic even though the production kernel has stationary distribution $\pi$?
What conditions allow the standard finite-state ergodic theorem to justify long-run production averages?
Give one reason dispersed initial states are useful and one reason they cannot prove that the chain has explored the full target.

Initialization, Burn-In, and Warmup

What You'll Learn