$\newcommand{\Cat}{{\rm Cat}}$ $\newcommand{\A}{\mathcal A}$ $\newcommand{\freestar}{ \framebox[7pt]{\star} }$

## Markov chain mixing times

### Edited by org.aimpl.user:benhamou@math.univ-paris-diderot.fr and org.aimpl.user:reza@cims.nyu.edu

In general, we will use the following notation in the problem list. We consider aperiodic irreducible Markov chains on a state space, $\Omega$ with unique invariant (stationary) distribution $\pi$. In the discrete time setting we allow the matrix $(P)_{x,y\in\Omega}$ with $P_{xy}=P(x,y)$ to denote the transition matrix of the Markov chain.

A chain is reversible if $\pi(x)P(x,y)=\pi(y)P(y,x)$ for all $x,y\in\Omega$. $Q(x,y)=\pi(x)P(x,y)$ is the edge measure on $(x,y)$. We denote by $t_{\mbox{mix}}$ the total variation mixing time defined as $t_{\mbox{mix}}(\epsilon)=\inf\{t:\sup_{\omega_0\in\Omega}\|P^t(\omega_0,\cdot)-\pi(\cdot)\|_{TV}\leq \epsilon\}\,,$ and set $t_{\mbox{mix}}=t_{\mbox{mix}}(\epsilon)$, where the total variation distance $\|\mu-\nu\|_{TV}=\tfrac 12 \|\mu-\nu\|_{\ell^1}\,.$

### Sections

1. 6. Various

Cite this as: AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.