Mixing Estimates for a Lazy Walk on a Cycle

The Lazy Walk on a Cycle

A walk on a cycle is spatially symmetric, so its transition matrix has a structure that can be exploited rather than handled by direct matrix powers. The discrete Fourier modes are eigenvectors of this matrix. Their eigenvalues describe how quickly each spatial frequency decays, and together they give an explicit upper bound on the distance to equilibrium.

Fix an integer $m\ge3$ and let $S=\mathbb{Z}/m\mathbb{Z}=\{0,1,\ldots,m-1\}$, with addition interpreted modulo $m$. On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $(X_n)_{n\ge0}$ be the discrete-time Markov chain with this state space and transition matrix $P=(p_{xy})$. Its natural filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. At each step, the chain stays where it is with probability $1/2$, and moves to each of its two neighbors with probability $1/4$.

Definition: For $x,y\in S$, $p_{xy}=1/2$ if $y=x$, $p_{xy}=1/4$ if $y=x+1$ or $y=x-1$ modulo $m$, and $p_{xy}=0$ otherwise. For $m\ge3$, the two neighbors are distinct. Each row sums to $1/2+1/4+1/4=1$, so $P$ is row-stochastic.

The uniform distribution $\pi$, with $\pi_y=1/m$ for every $y$, is stationary: each column also contains one entry $1/2$ and two entries $1/4$, so $\sum_x\pi_xp_{xy}=1/m$. The walk is irreducible because successive neighbor moves can reach any state, and it is aperiodic because $p_{xx}>0$. We will estimate how many steps are sufficient for its distribution to be close to $\pi$.

For probability distributions $\nu$ and $\eta$ on $S$, their total variation distance is $\|\nu-\eta\|_{\mathrm{TV}}=\tfrac12\sum_{y\in S}|\nu_y-\eta_y|$. Write $P^{(n)}=P^n$, and define the worst-case mixing time at accuracy $0<\varepsilon<1$ by $t_{\mathrm{mix}}(\varepsilon)=\min\{n\ge0:\max_{x\in S}\|P^{(n)}(x,\cdot)-\pi\|_{\mathrm{TV}}\le\varepsilon\}$.

Fourier Modes and Eigenvalues

For $k\in\{0,\ldots,m-1\}$, define the complex-valued function $\phi_k(x)=\exp(2\pi \mathrm{i}kx/m)$. These functions form the discrete Fourier basis. The transition rule acts on a function $f$ by $(Pf)(x)=\sum_y p_{xy}f(y)$. Applying it to one Fourier mode gives

(P\phi_k)(x) =\tfrac12\phi_k(x)+\tfrac14\phi_k(x+1)+\tfrac14\phi_k(x-1) =\lambda_k\phi_k(x), \qquad \lambda_k=\tfrac12+\tfrac12\cos(2\pi k/m) =\cos^2(\pi k/m).

Here the last equality follows from $1+\cos(2u)=2\cos^2(u)$. Thus every eigenvalue is real and belongs to $[0,1]$; $\lambda_0=1$, while the other modes have eigenvalues less than $1$.

Theorem (Fourier expansion and total variation bound): For the lazy walk on $S=\mathbb{Z}/m\mathbb{Z}$, started at any $x\in S$, and every integer $n\ge0$, $$ P^{(n)}(x,y)-\frac1m =\frac1m\sum_{k=1}^{m-1}\lambda_k^n \exp\!\left(\frac{2\pi\mathrm{i}k(y-x)}m\right), \qquad \|P^{(n)}(x,\cdot)-\pi\|_{\mathrm{TV}} \le\frac12\sqrt{\sum_{k=1}^{m-1}\lambda_k^{2n}}. $$ The bound is uniform in the starting state $x$.

Proof. The finite geometric sum gives $\sum_{x=0}^{m-1}\exp(2\pi\mathrm{i}(k-\ell)x/m)=m$ if $k=\ell$ modulo $m$, and $0$ otherwise: in the latter case it is a geometric series with ratio different from $1$ whose $m$th power is $1$. Therefore the Fourier modes are orthogonal and form a basis of the $m$-dimensional space of functions on $S$. Applying $P$ repeatedly multiplies $\phi_k$ by $\lambda_k^n$. Fourier inversion for the transition probabilities then gives $P^{(n)}(x,y)=m^{-1}\sum_{k=0}^{m-1}\lambda_k^n\exp(2\pi\mathrm{i}k(y-x)/m)$. The $k=0$ term is $1/m$, which proves the expansion. To obtain the inequality, square the absolute value of the expansion, sum over $y$, and use the same orthogonality identity. It gives $\sum_y|P^{(n)}(x,y)-1/m|^2=m^{-1}\sum_{k=1}^{m-1}\lambda_k^{2n}$. By Cauchy–Schwarz, $\sum_y|a_y|\le\sqrt{m\sum_y|a_y|^2}$; multiplying by $1/2$ yields the claimed total variation bound. $\square$

The factor $\lambda_k^{2n}$ in the bound records the decay of each nonconstant frequency. The next step bounds these eigenvalues in terms of how far $k$ is from $0$ modulo $m$.

Theorem (Explicit mixing-time upper bound): For every integer $m\ge3$ and $0<\varepsilon<1$, the lazy walk on the $m$-cycle satisfies $$ t_{\mathrm{mix}}(\varepsilon) \le \left\lceil\frac{m^2}{8}\log\!\left(1+\frac{1}{2\varepsilon^2}\right)\right\rceil. $$

Proof. For $k=1,\ldots,m-1$, set $r=\min(k,m-k)$. Then $1\le r\le m/2$ and $\lambda_k=1-\sin^2(\pi r/m)$. The sine function is concave on $[0,\pi/2]$, since its second derivative is $-\sin x\le0$; consequently its graph lies above the chord joining the endpoints, so $\sin x\ge2x/\pi$ on that interval. Hence $\sin(\pi r/m)\ge2r/m$. Using $1-u\le e^{-u}$ for $u\ge0$, we obtain $\lambda_k\le\exp(-4r^2/m^2)$. Set $a=8n/m^2$. Raising this inequality to the power $2n$ gives $\lambda_k^{2n}\le e^{-ar^2}$. For each positive integer $r$, at most two indices $k$ have $\min(k,m-k)=r$. Since $r^2\ge r$, it follows that $$ \sum_{k=1}^{m-1}\lambda_k^{2n} \le 2\sum_{r=1}^{\infty}e^{-ar^2} \le 2\sum_{r=1}^{\infty}e^{-ar} =\frac{2}{e^a-1} $$ when $n>0$. The geometric series equality follows from its ratio $e^{-a}<1$. The Fourier bound now gives $\|P^{(n)}(x,\cdot)-\pi\|_{\mathrm{TV}}\le\tfrac12\sqrt{2/(e^a-1)}$, uniformly in $x$. This is at most $\varepsilon$ whenever $e^a\ge1+1/(2\varepsilon^2)$, or equivalently $n\ge(m^2/8)\log(1+1/(2\varepsilon^2))$. Taking the least integer at least this large proves the result. The bound is stated for positive $n$; its right-hand side is positive, so the displayed mixing-time upper bound uses a positive integer. $\square$

Worked Calculations

Worked Example: Diagonalizing the Four-Cycle

Label the states $0,1,2,3$ modulo $4$. In this order the transition matrix is $$ P=\begin{bmatrix} \tfrac12&\tfrac14&0&\tfrac14\\ \tfrac14&\tfrac12&\tfrac14&0\\ 0&\tfrac14&\tfrac12&\tfrac14\\ \tfrac14&0&\tfrac14&\tfrac12 \end{bmatrix}. $$ Each row sums to $1/2+1/4+0+1/4=1$ or $1/4+1/2+1/4+0=1$, as appropriate.

For $m=4$, the eigenvalue formula gives $\lambda_0=\cos^2(0)=1$, $\lambda_1=\cos^2(\pi/4)=1/2$, $\lambda_2=\cos^2(\pi/2)=0$, and $\lambda_3=\cos^2(3\pi/4)=1/2$. At time $n=2$, the Fourier bound is $$ \frac12\sqrt{\lambda_1^4+\lambda_2^4+\lambda_3^4} =\frac12\sqrt{\frac1{16}+0+\frac1{16}} =\frac{1}{4\sqrt2}. $$

We can check against the exact distribution from $0$. In two steps, the probability of returning to $0$ is $(1/2)^2+2(1/4)^2=1/4+1/8=3/8$. The probability of reaching $1$ is $(1/2)(1/4)+(1/4)(1/2)=1/4$; by symmetry the probability of reaching $3$ is also $1/4$. The probability of reaching $2$ is $(1/4)(1/4)+(1/4)(1/4)=1/8$. These probabilities sum to $3/8+1/4+1/8+1/4=1$. The exact total variation distance is $\tfrac12(1/8+0+1/8+0)=1/8$, which is below the spectral bound $1/(4\sqrt2)$.

Worked Example: One-Step Distance on the Six-Cycle

Take $m=6$. Each row has probability $1/2$ of staying, $1/4$ of moving to each neighbor, and $0$ elsewhere; its entries sum to $1/2+1/4+1/4+0+0+0=1$. From state $0$, the one-step distribution in state order $0,\ldots,5$ is $(1/2,1/4,0,0,0,1/4)$, whose entries sum to $1$.

The stationary distribution assigns $1/6$ to every state. The absolute differences, in order, are $1/3,1/12,1/6,1/6,1/6,1/12$. Their sum is $1/3+1/6+1/2=1$, so the exact distance is $1/2$. For comparison, the eigenvalues for $k=0,\ldots,5$ are $1,3/4,1/4,0,1/4,3/4$, obtained by substituting each $k$ into $\cos^2(\pi k/6)$. Thus the Fourier bound at $n=1$ is $$ \frac12\sqrt{2\left(\frac34\right)^2+2\left(\frac14\right)^2+0^2} =\frac12\sqrt{\frac{20}{16}} =\frac{\sqrt5}{4}. $$

Since $\sqrt5>2$, this upper bound exceeds $1/2$, as it must to be consistent with the exact calculation. The example also shows why the Fourier estimate is an upper bound, not generally an exact distance.

Worked Example: Applying the Mixing-Time Formula

For the six-cycle, find a time certified by the upper bound to give total variation distance at most $\varepsilon=1/2$ from every starting state. The explicit formula requires $$ n\ge \frac{6^2}{8}\log\!\left(1+\frac{1}{2(1/2)^2}\right) =\frac92\log 3. $$

We verify that $n=5$ satisfies this requirement. The exponential series has positive terms, and $$ e^{10/9}> 1+\frac{10}{9}+\frac{(10/9)^2}{2}+\frac{(10/9)^3}{6}+\frac{(10/9)^4}{24} =\frac{59453}{19683}>3, $$ where $59453>3(19683)=59049$. Therefore $\log 3<10/9$, so $(9/2)\log3<5$. The theorem certifies that at $n=5$ the worst-case distance is at most $1/2$. This is a sufficient bound; it does not assert that five steps are the exact mixing time.

Directly checking the theorem’s tail estimate gives the same guarantee: $a=8n/m^2=8\cdot5/36=10/9$, and $e^a>3$, so $\tfrac12\sqrt{2/(e^a-1)}<\tfrac12\sqrt{2/2}=1/2$.

Interpretation and a Common Pitfall

The slowest nonconstant Fourier modes determine the long-time scale. For $k=1$, the eigenvalue is $\cos^2(\pi/m)$, which is close to $1$ when $m$ is large. The eigenvalue estimate in the proof shows that suppressing these modes requires a number of steps proportional to $m^2$, with additional dependence on the requested accuracy. The explicit bound is useful when a guarantee for all starting states is needed and an exact distribution is impractical to compute.

Common pitfall: forgetting that total variation includes a factor of $1/2$. After finding the absolute coordinate differences, their sum is the $L^1$ distance, not the total variation distance. For the six-cycle one-step example, the absolute differences sum to $1$, so the total variation distance is $1/2$, not $1$. A separate spectral pitfall is to use eigenvalues of the non-lazy walk without accounting for negative eigenvalues: the lazy walk’s eigenvalues are nonnegative, which is why the mode decay can be bounded directly by powers of $\lambda_k$.

Check Your Understanding

Use the Fourier eigenvalue formula and the definition of total variation to answer these questions.

For the lazy walk on a cycle of size $m$, calculate $\lambda_0$ and explain why this mode corresponds to the uniform stationary distribution.
On the four-cycle, calculate the Fourier upper bound at time $n=1$.
Why does the proof group at most two indices $k$ with the same value of $r=\min(k,m-k)$?
For $m=6$ and $\varepsilon=1/2$, verify the inequality used to certify that $n=5$ satisfies the mixing-time bound.
In the six-cycle one-step calculation, what is the $L^1$ distance from uniform, and what is the total variation distance?

Mixing Estimates for a Lazy Walk on a Cycle

What You'll Learn