Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 215 (Mixing Times of Markov Chains)

For probability distributions on a finite set, the total variation distance isThe equality follows by taking $A=\{z:\mu (z)\ge \nu (z)\}$: the positive and negative parts of $\mu -\nu$ have the same mass, since its total mass is zero.

Use the stationary distribution identity $\pi P^t=\pi$. For each initial state $x$,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over $x$ proves $\boxed{d(t)\le \bar{d}(t)}$. This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.

A coupling of probability distributions is a joint probability distribution of random variables $(X,Y)$ with the specified marginal distributions: $\mathbb{P}(X\in A)=\mu (A)$ and $\mathbb{P}(Y\in A)=\nu (A)$. No independence is required.

For every set $A$, the difference of the two indicator functions vanishes when $X=Y$. ConsequentlyMaximizing over $A$ gives the coupling inequality for total variation:

Let $R$ interchange the two complete graphs, sending $v_i$ to $v_i^{\prime }$ and fixing $w$. This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts $X$ at $v_i$, keeps $Y_t=R(X_t)$ until the hitting time $\tau$ of $w$, and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at $\tau$. The coupling inequality for total variation gives

There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For $n\ge 2$, write $a={\mathbb{E}}_{v_1}\tau$ and $b={\mathbb{E}}_{v_i}\tau$ for $i\ne 1$. From every clique vertex there is a positive chance of reaching $w$ within two steps, uniformly over the finite state space for each fixed $n$, so $\tau$ has finite expected value. First-step analysis, using the degree of a vertex $n$ at $v_1$ and $n-1$ at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is ${\max }_x{\mathbb{E}}_x\tau \le n^2$, the hitting time of the bridge vertex between two cliques formula.

We must also handle arbitrary starting states, including $w$, before applying the mirror argument. Identify related vertices and consider the lumped Markov chain $Z$ on $\{1,\dots ,n,w\}$. Its transition matrix $Q$ has $Q(1,j)=1/n$ for $j\ne 1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne 1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne 1$ only ranges over $j\in \{1,\dots ,n\}$.

For $n\ge 3$ and $j\in \{2,\dots ,n\}$, direct two-step calculation givesAll these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot )\ge \alpha \nu (\cdot )$ for every $z$, where $\nu$ is the uniform distribution on a finite set $\{2,\dots ,n\}$ and $\alpha =(n-1)/(2n)\ge 1/3$. This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from $\nu$ with probability $\alpha$, using the residual probability distributions otherwise. The first successful block has expected value at most $1/\alpha$, so the alignment time $A$ has $\mathbb{E}A\le 6$. Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.

At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time $T$ satisfying $\mathbb{E}T\le 6+n^2$ for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least $1-2/n$: for two ordinary indices it is $(n-2)/(n-1)$; for one attachment index it is $(n-2)/n$. A maximal coupling therefore aligns those indices with probability $1-O(1/n)$, as suggested. The two-step argument above additionally covers $w$.

The nonlazy walk is an aperiodic Markov chain for $n\ge 3$, because the connected graph contains a triangle. For $n=1,2$ it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass $1/2$, and the walk stays on a single class at each time. Hence $d(t)\ge 1/2$ and the $1/4$ mixing time is infinite. The asymptotic conclusion is valid for $n\ge 3$.

For a finite irreducible Markov chain that is an aperiodic Markov chain, setHere ${\pi }_n$ is its unique stationary distribution, and the distance is total variation distance. Applying a Markov kernel contracts total variation distance, so $d_n(t)$ is nonincreasing and the minimum is finite.

Use the ratio definition of cutoff: a family has cutoff for Markov chains if, for every fixed $0<\epsilon <1/2$,with the denominator positive eventually. Thus the transition between any two fixed distance levels takes negligible time compared with the mixing time scale. By monotonicity and squeezing, this also gives $t_{\mathrm{mix}}^{(n)}(\alpha )/t_{\mathrm{mix}}^{(n)}(\beta )\to 1$ for any fixed $\alpha ,\beta \in (0,1)$.

Some definitions of cutoff for Markov chains additionally require the mixing time to diverge. That extra requirement cannot be built into the definition here: the final request in part (d) explicitly asks for a bounded-time counterexample. The ratio convention is the one consistent with that request.

Take the real inner productThe stationary distribution is strictly positive for an irreducible Markov chain. Detailed balance gives $⟨Pf,g{⟩}_{\pi }=⟨f,Pg{⟩}_{\pi }$, so $P$ is a self-adjoint operator. Choose a real orthonormal eigenbasis $f_1,\dots ,f_m$, where $m=|S|$, $P{f}_j={\lambda }_j{f}_j$, $f_1\equiv 1$, ${\lambda }_1=1$, and $\pi (f_j)=0$ for $j\ge 2$.

For fixed $y$, apply the spectral decomposition to $g_y(z)=1_{\{y\}}(z)/\pi (y)$. Its coefficient against $f_j$ is $f_j(y)$, whereas $(P^t{g}_y)(x)=P^t(x,y)/\pi (y)$. Thus the spectral kernel expansion of a reversible chain isThis holds for all integers $t\ge 0$; at $t=0$ each multiplier is one, including when ${\lambda }_j=0$. Negative eigenvalues are allowed, and retain their signs for odd $t$.

Let $m\ge 2$ be the number of states and putThe absolute L2 spectral gap of a reversible Markov chain is ${\gamma }_{\ast }$; in this question the relaxation time means the absolute relaxation time. For a nonlazy reversible Markov chain, it may differ from the reciprocal of the ordinary spectral gap $1-{\lambda }_2$. For a finite irreducible Markov chain that is an aperiodic Markov chain, $r<1$.

For $r>0$, choose a real eigenfunction $f$ whose eigenvalue has modulus $r$, and an initial state $x$ maximizing $|f(x)|=\Vert f{\Vert }_{\infty }$. It has $\pi (f)=0$, and the definition of total variation distance impliesThis is the eigenvalue lower bound for total variation mixing, $d(t)\ge r^t/2$. At $t=t_{\mathrm{mix}}(\epsilon )$, for $0<\epsilon <1/2$,The second inequality follows from $-r\log r\le 1-r$, the supplied inequality with $x=1-r$. Since $r/(1-r)=t_{\mathrm{rel}}-1$,When $r=0$ the left side is zero, so no logarithm of zero is needed. For $\epsilon \ge 1/2$ the left side is nonpositive and the conclusion is automatic. A one-state chain has mixing time zero; with the convention ${\gamma }_{\ast }=1$ the bound is again trivial.

Use the ratio definition of cutoff from part (a), and write $T_n=t_{\mathrm{mix}}^{(n)}(1/4)$. In the reversible Markov chain setting of the preceding parts let ${\gamma }_n=1-{\lambda }_{2,n}$ and ${\gamma }_{\ast ,n}=1-{\max }_{j\ge 2}|{\lambda }_{j,n}|$. In particular ${\gamma }_{\ast ,n}\le {\gamma }_n$.

If ${\gamma }_n{T}_n$ did not tend to infinity, there would be a subsequence and $B>0$ for which ${\gamma }_n{T}_n\le B$. Along it part (c) implies, for every fixed $0<\epsilon <1/2$,Since $T_n\to \infty$, choose fixed $\epsilon$ so small that $\log (1/(2\epsilon ))>B$. The lower limit of this ratio is then greater than one, contradicting cutoff for Markov chains. Thus the Peres product condition holds:In fact the argument with ${\gamma }_{\ast ,n}$ proves the stronger absolute-gap product condition. Part (d) does not repeat the reversible Markov chain hypothesis; the ordinary real ordering of eigenvalues above uses that hypothesis. If arbitrary chains are intended, define the spectral gap explicitly: the eigenvalue lower bound for total variation mixing works for complex eigenfunctions too, and proves the same assertion for ${\gamma }_{\ast }$ or for $1-{\max }_{j\ge 2}\mathrm{Re}{\lambda }_j$, which is at least ${\gamma }_{\ast }$. No real ordering of complex eigenvalues is implicit.

For the requested counterexample take nonlazy simple random walk on the complete graph $K_n$, $n\ge 3$. Let $\Pi$ have every row equal to the uniform distribution on a finite set, and let $a=-1/(n-1)$. ThenThus $d_n(0)\to 1$ and $d_n(1)=1/n\to 0$: every fixed-level mixing time is eventually one. This is a bounded-time jump satisfying the ratio definition of cutoff. The ordinary spectral gap is $n/(n-1)$ and the absolute one is $(n-2)/(n-1)$, so both products with $T_n=1$ tend to one, not infinity. The divergence assumption on $T_n$ is therefore essential under this convention.

On a finite state space with at least two states, as in the surrounding questions, for a real function write $\pi (f)={\sum }_x\pi (x)f(x)$ and ${\mathrm{Var}}_{\pi }(f)={\sum }_x\pi (x)(f(x)-\pi (f){)}^2$. The Poincare inequality for a reversible Markov chain with constant $C$ iswhere the Dirichlet form of a Markov chain isThe associated spectral gap is the ordinary gap $\gamma =1-{\lambda }_2$, with variational formulaEquivalently minimize $\mathcal{E}(f,f)$ subject to $\pi (f)=0$ and $⟨f,f{⟩}_{\pi }=1$. Thus the Poincare inequality for a reversible Markov chain holds precisely for $C\ge 1/\gamma$, and the optimal constant is $1/\gamma$. It controls the ordinary rather than absolute spectral gap, so negative eigenvalues do not invalidate it. If the unspecified state space in this part is infinite, the Poincare inequality for a reversible Markov chain and the variational infimum still make sense on nonconstant functions in $L^2(\pi )$, using the self-adjoint operator on that Hilbert space; the resulting spectral gap need not be represented by an actual second eigenvalue. The finite-state formula above is the intended specialization.

For a finite irreducible Markov chain satisfying detailed balance, define the directed-edge capacity $Q(u,v)=\pi (u)P(u,v)$. For every ordered pair $(x,y)$ choose a path ${\eta }_{xy}$ from $x$ to $y$ using only positive-capacity edges; take the empty path for $x=y$. Let $N_e(\eta )$ count occurrences of the directed edge $e$. The canonical paths Poincare bound says thatis a valid Poincare inequality for a reversible Markov chain constant. Simple paths give $N_e\in \{0,1\}$; allowing repetitions requires the multiplicities shown.

To prove the theorem, expand the variance using two independent samples from $\pi$:Telescoping along ${\eta }_{xy}$ and applying the Cauchy-Schwarz inequality givesInterchange the finite sums, then use the definition of $\rho$:Consequently $\boxed{{\mathrm{Var}}_{\pi }(f)\le \rho \mathcal{E}(f,f),\gamma \ge 1/\rho }$. All edges here are directed, so the $1/2$ in the Dirichlet form of a Markov chain is retained consistently.

The lazy Markov chain has holding probability $1/2$ and transition probability $1/(2n)$ to each neighbour in the hypercube graph. Its stationary distribution is $\pi (x)=2^{-n}$ by symmetry.

For $(x,y)$ choose the path changing the differing coordinates in increasing order. Its length is at most $n$. Fix a directed edge $(u,u^{(k)})$ that flips coordinate $k$. A path uses this edge exactly when $x_k=u_k$, $y_k=-u_k$, $y_j=u_j$ for $j<k$, and $x_j=u_j$ for $j>k$. The coordinates $x_j$ for $j<k$ and $y_j$ for $j>k$ are free. Thus exactly $2^{n-1}$ ordered pairs use it, whileThe unweighted load divided by capacity equals $n$; multiplying by the maximum length yields $\rho \le n^2$. The canonical paths Poincare bound therefore proves the slightly stronger ${\mathrm{Var}}_{\pi }(f)\le n^2\mathcal{E}(f,f)$, and in particular the requestedOne can keep the actual lengths: among these $2^{n-1}$ pairs, coordinate $k$ always differs, and each of the other $n-1$ coordinates differs for half the pairs. Their mean path length is $(n+1)/2$, giving exact congestion $\rho =n(n+1)/2$. This refinement still has order $n^2$.

For each subset $J\subseteq \{1,\dots ,n\}$, take the Walsh character $f_J(x)={\prod }_{j\in J}{x}_j$, including $f_{\varnothing }\equiv 1$. Under the uniform distribution on a finite set these functions are an orthonormal basis: $f_J{f}_K=f_{J△K}$ has mean zero unless $J=K$, since the coordinates are independent fair signs. There are $2^n$ such functions, the full dimension of the function space.

Flipping a coordinate in $J$ changes the sign, while flipping one outside $J$ leaves the value unchanged. The total probability of a sign change is $|J|/(2n)$, soThe spectrum of lazy random walk on the hypercube is thereforeAll eigenvalues are nonnegative and the second largest is $1-1/n$. Hence both the ordinary spectral gap and the absolute spectral gap equal $\boxed{\gamma =1/n}$. The requested bound in part (c) is smaller than the exact gap by a factor $2n$; even the refined increasing-coordinate canonical paths Poincare bound loses a factor $(n+1)/2$. The true optimal Poincare inequality for a reversible Markov chain constant is $n$.

Use $⟨f,g{⟩}_{\pi }={\sum }_x\pi (x)f(x)g(x)$. The Dirichlet form of a Markov chain isThe equality follows by expanding the square and using row sums one and the stationary distribution identity. For the reversible Markov chain, detailed balance makes $P$ a self-adjoint operator, with real orthonormal eigenbasis $f_1\equiv 1,f_2,\dots ,f_m$ and ordered eigenvalues $1={\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_m$.

Adding a constant changes neither the variance nor the Dirichlet form of a Markov chain. Expand the centered function as $f-\pi (f)={\sum }_{j\ge 2}{a}_j{f}_j$. ThenFor every nonconstant $f$ the quotient is at least $1-{\lambda }_2$, and equality is attained at $f=f_2$. This provesEquivalently minimize the Dirichlet form of a Markov chain over centered unit-norm functions. This is the variational characterization underlying the Poincare inequality for a reversible Markov chain, and does not require the transition matrix to have nonnegative eigenvalues. For a one-state chain there is no nonconstant test function; the displayed minimization concerns $m\ge 2$.

The symmetric group has $n!$ elements, not the printed order $n$. For $n\ge 2$ the identity and the $n-1$ adjacent transpositions have probabilities $1/n$, so the specified transition matrix is normalized. Its stationary distribution is uniform and it satisfies detailed balance, since each transposition is its own inverse. Adjacent transpositions generate the symmetric group, making this an irreducible Markov chain; the positive holding probability makes it an aperiodic Markov chain.

For a fixed label $i$, right multiplication swaps positions, so $f(\sigma )={\sigma }^{-1}(i)$ is the label's position. Under the uniform distribution on a finite set it is uniform on $\{1,\dots ,n\}$. ThereforeFor each generator $s_j=(j,j+1)$, the squared change $[f(\sigma s_j)-f(\sigma ){]}^2$ is one if the label occupies either of the two positions, and zero otherwise. Its stationary expected value is $2/n$, givingThus the tagged-label Rayleigh quotient for adjacent transpositions gives the corrected bound

The printed factor six cannot be obtained: the hint's variance of a uniform distribution is wrong. Directly, $\mathrm{Var}(U)={\int }_0^1{u}^{2}du-({\int }_0^{1}udu{)}^2=1/12$. Bounded convergence in distribution of $U_n$ does imply convergence of its first two moments, hence convergence of its variance, but the limit is $1/12$.

More strongly, the claimed asymptotic bound itself is false for this kernel. The Aldous spectral gap theorem states that the interchange process on a finite connected weighted graph has the same spectral gap as the single-label random walk with identical edge rates; see Theorem 1.1 and its proof. Here $P-I$ is that interchange process generator on a path graph with edge rates $1/n$. For the tagged-label generator, direct substitution of $g_{\ell }(k)=\cos (\ell \pi (k-1/2)/n)$ gives eigenvalues $-2(1-\cos (\ell \pi /n))/n$, $0\le \ell <n$, including the reflecting endpoint equations. These $n$ distinct eigenvalues exhaust the tagged-label function space. Consequently the theorem yieldswhich exceeds $6/n^3$ asymptotically. This use of a substantial external theorem is only to certify the printed claim's failure; the corrected factor-twelve upper bound above follows directly from the requested test function and the variational formula.

The reference kernel printed in the hint has total mass $1/n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)=1+1/n$, so it is not a Markov kernel. We explicitly replace it by the normalized random transposition shuffle: choose two positions independently and uniformly and swap them. Its probabilities areThese sum to one, and its ordinary spectral gap is $\tilde{\gamma }=2/n$, the value intended in the hint. This value can also be certified by the Aldous spectral gap theorem: the single-label generator has rate $2/n^2$ between distinct positions, so on centered functions it acts as multiplication by $-2/n$. Both shuffles have the same uniform distribution on a finite set as stationary distribution.

We use the Canonical paths comparison theorem in the following precise form. For two finite reversible Markov chains with the same positive stationary distribution $\pi$, route each directed transition $(x,y)$ of $\tilde{P}$ along a positive-capacity path ${\eta }_{xy}$ of $P$. Ifthen $\tilde{\mathcal{E}}(f,f)\le A\mathcal{E}(f,f)$ and $\gamma \ge \tilde{\gamma }/A$. Indeed, telescope each difference along its path, apply the Cauchy-Schwarz inequality, and sum with weights $\pi (x)\tilde{P}(x,y)/2$. The load definition gives the Dirichlet form of a Markov chain inequality; the common variance denominator then gives the spectral gap inequality. Identity transitions use empty paths.

Put $s_k=(k,k+1)$. A transposition $(i,j)$ is routed using the wordof length $L_{ij}=2(j-i)-1\le 2n$. Each generator occurs at most twice; write its occurrence count as $N_k(i,j)\le 2$. For a fixed directed adjacent edge $(\sigma ,\sigma s_k)$ and each occurrence of $s_k$ in a word, there is exactly one starting permutation whose translated word crosses this edge at that occurrence. This follows because right multiplication by the prefix is a bijection of the symmetric group. Hence the uniform stationary factors cancel in the comparison load, leavingThe crude bounds $L_{ij}\le 2n$, $N_k(i,j)\le 2$, and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\le n^2/2$ imply $A\le 4n^2$. ThereforeOnly pairs with $i\le k<j$ contribute, and there are $k(n-k)\le n^2/4$ of these. Keeping this restriction gives the stronger $A\le 2n^2$ and $\gamma \ge 1/n^3$. Neither comparison bound needs the exact adjacent-shuffle spectral gap; the normalization repair of the reference kernel is essential.