Probability theory and stochastic processes Definition

Markov chain mixing time

Builds on Markov chain Transition matrix Stationary distribution Convergence to equilibrium of ergodic Markov chains

Definition

Let $S$ be a finite set and let $P$ be the transition matrix of an irreducible and aperiodic Markov chain on $S$ . Let $\pi$ be its stationary distribution. The total variation distance between probability distributions $\mu$ and $\nu$ on $S$ is $\norm{\mu - \nu}_{TV} = \max_{A \subseteq S} \abs{\mu(A) - \nu(A)} = \frac12 \sum_{x \in S} \abs{\mu(x) - \nu(x)}.$ For an integer $t \ge 0$ let $d(t) = \max_{x \in S} \norm{P^t(x, \cdot) - \pi}_{TV}$ , where $P^t(x, \cdot)$ is row $x$ of $P^t$ . For $\varepsilon \in (0, 1)$ , the mixing time is $t_{\mathrm{mix}}(\varepsilon) = \min\set{t \ge 0 : d(t) \le \varepsilon},$ and $t_{\mathrm{mix}} = t_{\mathrm{mix}}(1/4)$ .

Remarks

The minimum exists because $d(t) \to 0$ by the convergence theorem for ergodic chains. Example: on $S = \set{1, 2}$ let every entry of $P$ be $1/2$ . Then $\pi = (1/2, 1/2)$ , $d(0) = 1/2$ and $P^t(x, \cdot) = \pi$ for $t \ge 1$ , so $t_{\mathrm{mix}} = 1$ . Non-example: for $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ the chain is periodic, $d(t) = 1/2$ for all $t$ , and $t_{\mathrm{mix}}(\varepsilon)$ does not exist for $\varepsilon < 1/2$ . The function $d$ is nonincreasing, and $t_{\mathrm{mix}}(\varepsilon) \le \ceil{\log_2 (1/\varepsilon)} \, t_{\mathrm{mix}}$ .

Reading path

To understand this page from the ground up, read these 57 pages in order. The foundations come first.

Construction of the reals from Cauchy sequences concept
Coupling concept
Element definition
Integers object
Markov chain mixing time concept
Ordered field definition
Proposition concept
Random experiment concept
Rational numbers object
Real numbers object
Recurrence and transience of states concept
Stationary distribution concept
Transition matrix concept
Set definition
Ring of integers statement
Disjunction definition
Implication definition
Predicate definition
Ordered pair definition
Union definition
Sample space definition
Existential quantifier definition
Universal quantifier definition
The rationals form a field statement
Cartesian product definition
Subset definition
Uniqueness quantifier definition
The rationals form an ordered field statement
Binary relation definition
Universal set definition
Power set definition
Order on the reals definition
Function definition
Complement definition
Interval definition
Injective function definition
Preimage of a set definition
Sigma-algebra definition
Countable set definition
Event definition
Borel sigma-algebra definition
Probability axioms concept
Probability measure definition
Probability space definition
Conditional probability definition
Random variable definition
Independence of two events definition
Discrete random variable definition
Stochastic process concept
Random variable with a density definition
Conditional independence definition
Expected value definition
Conditional expectation definition
Markov property definition
Markov chain definition
Convergence to equilibrium of ergodic Markov chains statement
Markov chain mixing time definition

Tag	`J3D1T7F0CB`
URI	`m2://J3D1T7F0CB`
Kind	definition
Writing	W0 stub
MSC	60J10, 60J22
Defines	Markov chain mixing time
Uses	Markov chain, Transition matrix, Stationary distribution, Convergence to equilibrium of ergodic Markov chains
Changed	2 November 2026

Markov chain mixing time

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here