What is the mixing time of a random walk?

We already know that a random walk is a Markov chain with the vertices as its states, and we know that an ergodic Markov chain converges to its invariant distribution. But we do not know how fast. The mixing time is a measure of how quickly it converges. We now formally define this concept.

Def 1: The variation distance between two distributions $D_1$ and $D_2$ on a countable state space $S$ is given by $$||D_1-D_2|| = \frac{1}{2}\sum_{x\in S}{|D_1(x) - D_2(x)|}$$

The factor of one half ensures that the variation distance remains between $0$ and $1$.

Def 2: Let $\pi$ be the invariant distribution of an ergodic Markov chain with state space $S$. Let $p_{x}^t$ represent the distribution of the state of the chain starting at state $x$ after $t$ steps. We define $$\Delta_x(t) = ||p^t_x-\pi||$$ and $$\Delta(t) = \max_{x\in S}{\Delta_x(t)}$$

So $\Delta_x(t)$ is the variation distance between the invariant distribution and $p^t_x$, and $\Delta(t)$ is the maximum of these. Now we can define the mixing time.

Def 3: Similarly we defined $$\tau_x(\epsilon) = \min\{t: \Delta_x(t)\leq \epsilon \}$$ and $$\tau(\epsilon)=\max_{x\in S}{\tau_x(\epsilon)}$$ where $\tau_x(\epsilon)$ is the first time when the variation distance between $p^t_x$ and the invariant distribution is $\leq \epsilon$ and $\tau(\epsilon)$ is the maximum of these. $\tau(\epsilon)$ is called the mixing time.

We say that a Markov chain is rapidly mixing if $\tau(\epsilon)$ is polynomial in $\log(1/\epsilon)$ and the size of the problem.