Measuring Distance from Stationarity
A random walk is useful not only because it moves through a graph, but because its distribution can approach a stable distribution as time passes. To quantify that approach, we need a distance between probability distributions on the vertices. Total variation distance gives a precise measure: it is both a half-\(\ell^1\) difference and the largest possible difference in the probabilities assigned to an event.
Let \(\Omega\) be a finite set. A probability distribution \(\mu\) on \(\Omega\) assigns nonnegative numbers \(\mu(x)\) with \(\sum_{x\in\Omega}\mu(x)=1\). For a subset \(A\subseteq\Omega\), write \(\mu(A)=\sum_{x\in A}\mu(x)\).
The factor \(1/2\) ensures that total variation is the largest discrepancy on any event, rather than the sum of discrepancies over both the surplus and deficit points.
Proof. Set \(r(x)=\mu(x)-\nu(x)\). Since both distributions sum to \(1\), \(\sum_x r(x)=0\). Let \(A_+=\{x:r(x)>0\}\). The sum of the positive values of \(r\) equals the absolute sum of its negative values, so each is half of \(\sum_x|r(x)|\). In particular, \(\sum_{x\in A_+}r(x)=\frac12\sum_x|r(x)|\). For any set \(A\), the sum \(\sum_{x\in A}r(x)\) is at most the sum of all positive \(r(x)\), and at least the sum of all negative \(r(x)\). Its absolute value is therefore at most \(\frac12\sum_x|r(x)|\). Taking \(A=A_+\) attains this bound, proving the formula. \(\square\)
Walks, Stationarity, and Mixing Time
For a finite connected simple graph \(G=(V,E)\) with at least one edge, the simple random walk moves from its current vertex to a uniformly chosen neighbor. Its transition probabilities are \(P(u,v)=1/\deg(u)\) when \(uv\in E\), and \(P(u,v)=0\) otherwise. A distribution \(\pi\) is stationary if one step of the walk leaves it unchanged: \(\pi P=\pi\). For this walk, \(\pi(v)=\deg(v)/(2|E|)\) is stationary: for each vertex \(v\), \(\sum_u\pi(u)P(u,v)=\sum_{u:uv\in E}(1/(2|E|))=\deg(v)/(2|E|)=\pi(v)\). On a connected graph this is the stationary distribution. A lazy walk stays at its current vertex with probability \(1/2\) and otherwise takes a simple-random-walk step; it has the same stationary distribution.
More generally, a finite Markov chain has a transition matrix \(P\) with nonnegative entries and each row summing to \(1\). For an initial distribution \(\mu\), the distribution after \(t\) steps is \(\mu P^t\), where \(t\) is a nonnegative integer and \(P^0\) is the identity matrix. Let \(\pi\) be a specified stationary distribution for the chain.
The maximum over starting vertices matters: the walk may be close to stationarity from one start while still far from it from another. The threshold convention also matters when an exact distance equals \(\varepsilon\): that time does qualify.
Proof. Let \(\mu,\nu\) be distributions and write \(r(x)=\mu(x)-\nu(x)\). For each state \(y\), \((\mu P)(y)-(\nu P)(y)=\sum_x r(x)P(x,y)\). By the triangle inequality and the nonnegativity of transition probabilities, $$ \sum_y|(\mu P)(y)-(\nu P)(y)| \leq\sum_y\sum_x|r(x)|P(x,y) =\sum_x|r(x)|\sum_yP(x,y) =\sum_x|r(x)|. $$ Dividing by \(2\) proves \(\|\mu P-\nu P\|_{\mathrm{TV}}\leq\|\mu-\nu\|_{\mathrm{TV}}\). Now take \(\mu=P^t(x,\cdot)\), \(\nu=\pi\). Since \(\pi P=\pi\), this gives \(\|P^{t+1}(x,\cdot)-\pi\|_{\mathrm{TV}}\leq\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\). Maximizing the left side over \(x\) and bounding each right side by \(d(t)\) proves \(d(t+1)\leq d(t)\). \(\square\)
Worked Calculations
Worked Example: Comparing Two Distributions
Let \(\Omega=\{1,2,3\}\), with \(\mu=(1/2,1/3,1/6)\) and \(\nu=(1/3,1/3,1/3)\). Compute their total variation distance and exhibit an event attaining the maximum discrepancy.
The coordinate differences are \(1/2-1/3=1/6\), \(1/3-1/3=0\), and \(1/6-1/3=-1/6\). Therefore $$ \|\mu-\nu\|_{\mathrm{TV}} =\frac12\left(\left|\frac16\right|+|0|+\left|-\frac16\right|\right) =\frac12\left(\frac16+\frac16\right)=\frac16. $$ For \(A=\{1\}\), \(\mu(A)=1/2\) and \(\nu(A)=1/3\), so \(|\mu(A)-\nu(A)|=1/6\). This matches the total variation distance, as the event characterization requires.
Check: The differences sum to \(1/6+0-1/6=0\), as they must for two probability distributions. The positive discrepancy is \(1/6\), and the absolute negative discrepancy is also \(1/6\).
Worked Example: Exact Mixing Time on \(K_3\)
Let \(G=K_3\), with \(V=\{1,2,3\}\) and \(E=\{12,13,23\}\). Each step moves to either of the other two vertices with probability \(1/2\). The stationary distribution is \(\pi=(1/3,1/3,1/3)\). Find \(d(t)\) and \(t_{\mathrm{mix}}(1/12)\).
Starting at vertex \(1\), symmetry keeps the distribution in the form \((a_t,b_t,b_t)\). At time \(0\), \(a_0=1\). At the next step, the probability at vertex \(1\) is half the previous probability at vertices \(2\) and \(3\), so \(a_{t+1}=(1-a_t)/2\). Subtracting \(1/3\) gives $$ a_{t+1}-\frac13=-\frac12\left(a_t-\frac13\right). $$ Since \(a_0-1/3=2/3\), repeated application gives \(|a_t-1/3|=(2/3)(1/2)^t\). The other two coordinate differences each have magnitude \(|a_t-1/3|/2\), since the coordinates sum to \(1\) and are equal. Thus the distance from stationarity for this start is \(|a_t-1/3|=(2/3)(1/2)^t\). By symmetry, all three starting vertices give the same distance, so this is \(d(t)\).
At \(t=2\), \(d(2)=(2/3)(1/2)^2=1/6\). At \(t=3\), \(d(3)=(2/3)(1/2)^3=1/12\). At \(t=2\) the distance exceeds \(1/12\), and at \(t=3\) it equals the threshold, so \(t_{\mathrm{mix}}(1/12)=3\).
Check: Starting at \(1\), the distributions at times \(1,2,3\) are \((0,1/2,1/2)\), \((1/2,1/4,1/4)\), and \((1/4,3/8,3/8)\). Their distances from the uniform distribution are respectively \(1/3\), \(1/6\), and \(1/12\), agreeing with the formula.
Worked Example: A Lazy Walk on \(P_3\)
Let \(G=P_3\) have \(V=\{1,2,3\}\) and \(E=\{12,23\}\), and use the lazy walk that stays put with probability \(1/2\). Its transition matrix, with rows and columns ordered \(1,2,3\), is $$ P=\begin{pmatrix} 1/2&1/2&0\\ 1/4&1/2&1/4\\ 0&1/2&1/2 \end{pmatrix}. $$ The stationary distribution is \(\pi=(1/4,1/2,1/4)\), from the degrees \(1,2,1\). Find \(d(t)\) and \(t_{\mathrm{mix}}(1/8)\).
Starting at the middle vertex gives \(\pi\) after one step: the transition probabilities in row \(2\) are exactly \((1/4,1/2,1/4)\), so this start remains stationary thereafter. Starting at endpoint \(1\), the distribution at time \(1\) is \((1/2,1/2,0)\). Its difference from \(\pi\) is \((1/4,0,-1/4)\), with total variation distance \(\frac12(1/4+0+1/4)=1/4\).
For any number \(a\), direct multiplication gives \((a,0,-a)P=(a/2,0,-a/2)\). Therefore, at each subsequent step the endpoint-start difference from \(\pi\) is halved. At time \(t\geq1\), it is \((2^{-(t+1)},0,-2^{-(t+1)})\), and its total variation distance is \(2^{-(t+1)}\). The other endpoint gives the same distance by symmetry. At time \(0\), a point mass at an endpoint has distance \(\frac12(|1-1/4|+|0-1/2|+|0-1/4|)=3/4\). Hence \(d(0)=3/4\), and \(d(t)=2^{-(t+1)}\) for \(t\geq1\). Since \(d(1)=1/4>1/8\) and \(d(2)=1/8\), \(t_{\mathrm{mix}}(1/8)=2\).
Check: Multiplying the time-\(1\) distribution by \(P\) gives \((3/8,1/2,1/8)\). Its difference from \(\pi\) is \((1/8,0,-1/8)\), whose total variation distance is \(\frac12(1/8+1/8)=1/8\), as the time-\(2\) formula predicts.
Periodicity and a Common Pitfall
A stationary distribution does not by itself guarantee that the walk approaches stationarity from every starting point. For example, on the graph with \(V=\{1,2\}\) and \(E=\{12\}\), the simple random walk alternates deterministically between the two vertices. Its stationary distribution is \((1/2,1/2)\), but from vertex \(1\) the distribution at every even time is \((1,0)\), and at every odd time it is \((0,1)\). In either case its total variation distance from stationarity is \(\frac12(|1/2|+|{-1/2}|)=1/2\). Thus for any \(0<\varepsilon<1/2\), its mixing time is infinite. This example explains why periodicity matters; laziness is one way to remove this obstruction for connected graph walks.
Common mistake: omitting the factor \(1/2\). For the distributions in the first worked example, summing the absolute differences gives \(1/6+0+1/6=1/3\). That is the full \(\ell^1\) difference, not the total variation distance. The required division by \(2\) gives \(1/6\), which also equals the largest event-probability discrepancy.
Total variation distance makes “close to stationarity” precise in two equivalent ways: the half-\(\ell^1\) formula is convenient for calculation, while the event interpretation tells what the distance means probabilistically. Mixing time then asks for the earliest step at which every starting vertex is within a chosen tolerance. Exact small-graph calculations also show why the tolerance, the worst-case starting state, and the behavior of the walk over time must all be stated.
Check Your Understanding
Use the definitions and calculations above to answer the following questions.
- For \(\mu=(1/2,1/4,1/4)\) and \(\nu=(1/4,1/2,1/4)\), compute total variation distance and give a set attaining the maximum event discrepancy.
- For the \(K_3\) walk, find the smallest \(t\) such that \(d(t)\leq1/24\).
- Explain why the stationary distribution on \(P_3\) is \((1/4,1/2,1/4)\), rather than uniform.
- For the lazy \(P_3\) walk, what is \(d(3)\), and which starting vertices attain it?
- For the two-vertex simple random walk, what is its distance from stationarity at odd times, and why does this prevent mixing at thresholds below that value?