Editing Markov chain Monte Carlo (section)

=== Total Variation Distance ===

Formally, let <math>\pi</math> denote the stationary distribution and <math>P^t(x, \cdot)</math> the distribution of the Markov chain after <math>t</math> steps starting from state <math>x</math>. Theoretically, convergence can be quantified by measuring the  [[Total variation distance of probability measures|total variation distance]]:

:<math>
d_{\text{TV}}(P^t(x,\cdot), \pi) = \sup_{A} |P^t(x,A) - \pi(A)|
</math>

A chain is said to mix rapidly if <math>d_{\text{TV}}(P^t(x,\cdot),\pi) \leq \epsilon</math> for all <math>x \in \mathcal{X}</math> within a small number of steps <math>t</math> under a pre-defined tolerance <math>\epsilon > 0</math>. In other words, the stationary distribution is reached quickly starting from an arbitrary position, and the minimum such <math>t</math> is known as the [[Markov chain mixing time|mixing time]]. In practice, however, the total variation distance is generally intractable to compute, especially in high-dimensional problems or when the stationary distribution is only known up to a normalizing constant (as in most Bayesian applications).