Is there one mixing time for a chain?

A tolerance-dependent family is defined; a single reported number often uses a conventional tolerance that should be stated.

Does reaching mixing time make samples independent?

No. It controls distance of the marginal distribution from stationarity, not all dependence between successive samples.

Can a chain fail to mix?

Yes. Its structure can prevent convergence from the starting states, even if a stationary distribution exists.

AI Glossary / Graphs and symbolic AI / Intermediate

Mixing time

Definition

Mixing time is the number of steps a Markov chain needs to bring its distribution sufficiently close to its stationary distribution, according to a specified distance and tolerance. A common definition uses the worst starting state and total variation distance. The tolerance is part of the definition, not an optional detail.

What it means

Starting a chain at one chosen state usually gives a different distribution from its long-run target. Mixing time quantifies how long that initial influence can persist. It concerns the distribution of the state after a number of transitions, not the moment when one particular simulated path has visited every state.
Different tolerances produce different mixing times. A starting-state-specific convergence time can also be shorter than the worst-case value. In a finite irreducible and aperiodic chain, convergence to a unique stationary distribution supports this standard analysis. Other chains require care because ordinary convergence may fail.

How it works

For each time t, measure the total variation distance between the t-step distribution from each starting state and the stationary distribution. Let d(t) be the largest of those distances. Then t_mix(epsilon) is the first nonnegative integer t for which d(t) is at most epsilon.
For finite distributions, total variation is half the sum of absolute probability differences across states. It can also be interpreted as the largest probability discrepancy assigned to an event. A frequently used convention takes epsilon = 1/4, but applications and analyses may use other tolerances. Always report which convention is meant.

Three practical examples

A theoretical sampling analysis can bound how many transitions are needed before initialization bias is below a chosen level.
A simulation designer can compare transition mechanisms using their worst-case convergence requirements.
A probability lesson can distinguish mixing time from the time to first reach a particular state or to visit every state.

Think of it this way

Think of stirring a mixture until it is sufficiently uniform under a stated measurement standard. A stricter standard can require longer stirring. The analogy is limited because a Markov chain need not target a uniform distribution, and a formal mixing time concerns distributions over possible runs rather than the appearance of one observed run.

Worked example

Consider an invented two-state chain with states A and B. Each step stays in the current state with probability 0.75 and switches with probability 0.25. The stationary distribution assigns probability 0.5 to each state.
Starting from A, the probability of A after t steps is 0.5 + 0.5 times 0.5 to the power t. Starting from B gives the symmetric expression with a minus sign. Both starts have the same total variation distance d(t) = 0.5 times 0.5 to the power t, so this is also the worst-case distance.
At t = 0, the distance is 0.5. At t = 1, it is 0.25. At t = 2, it is 0.125. At t = 3, it is 0.0625. For tolerance epsilon = 0.1, time 2 is insufficient and time 3 qualifies, giving t_mix(0.1) = 3.
For epsilon = 0.01, time 5 gives 0.015625, while time 6 gives 0.0078125. Thus t_mix(0.01) = 6. Under the conventional tolerance 1/4, the mixing time is 1 because equality with the tolerance is allowed.
These statements concern the probability distribution across possible runs. A particular run may still remain in A for all six transitions; that sequence has positive probability. The calculation also does not say that the sixth and seventh samples are independent. The chain's next-state probabilities still depend on its current state.
If each transition costs one millisecond in a toy implementation, three transitions take three milliseconds, but that timing assumption is external to the mathematical definition. Another implementation or transition rule can have a different cost per step.

Illustrative case study

In a fictional sampling project, Fern Analytics labels a fixed burn-in of one thousand steps as the mixing time without any supporting analysis. The same number is reused after the transition mechanism changes.
The team relabels it as a chosen burn-in setting and separately documents available convergence evidence and unresolved uncertainty. This invented case illustrates the distinction between an operational choice and a demonstrated property of a chain. It does not suggest that a single universal burn-in length is adequate.

Common misconceptions and mistakes

Mixing time is not hitting time, which concerns reaching a specified state or set, or cover time, which concerns visiting all states. Nor is it automatically the number of samples needed for an accurate estimate: dependence and the quantity being estimated also matter.
Do not omit the tolerance, distance measure, or starting-state convention. A visually stable statistic does not establish a worst-case mixing bound. Also, existence of a stationary distribution alone is insufficient for ordinary convergence; for example, a deterministic alternation between two states has a stationary distribution but oscillates forever when started at one state.

Business use

Mixing-time ideas help teams assess initialization bias in probabilistic computation. Distinguish a proven bound from an empirical estimate, a diagnostic impression, and an arbitrary run setting. Each supports a different strength of conclusion.
When comparing methods, account for the cost of each transition as well as the number of transitions. Examine whether the assumed chain matches the implementation, including adaptation or changing parameters. Keep sampling precision and convergence questions separate: running longer may reduce some uncertainty while still leaving poor exploration of an important region. Report assumptions and limitations alongside any claimed convergence threshold.

Check your understanding

Why is t_mix(0.1) equal to 3 rather than 2 in the worked example?

Answer: At two steps the worst-case distance is 0.125, which exceeds 0.1. At three it is 0.0625, which meets the tolerance.

Related terms

Mixing rate
Markov Chain
Total Variation Distance (Tvd)
Stationary distribution
Autocorrelation
total variation distance
burn-in
hitting time
cover time
MCMC
convergence bound

Learn next

Use the example's formula to find the mixing time for tolerance 0.02, checking the integer step immediately before your answer. Then compare a chain started at stationarity with the worst starting state and explain why their initial distances differ.

Sources

David Levin, Yuval Peres and Elizabeth Wilmer, Markov Chains and Mixing Times, original textbook, Section 4.5 and the preceding distance definitions: https://www.stat.berkeley.edu/~aldous/260-FMIE/Levin-Peres-Wilmer.pdf

Previous: Mixing rate Next: Mixture density