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

The laziness of $P=(Q+I)/2$ makes all its eigenvalues nonnegative. WriteThe relaxation time isIf $(f_i)$ is an orthonormal eigenbasis of $L^2(\pi )$ with $f_1=1$, the spectral decomposition is

On the diagonal,so every summand is nonnegative. Let $m=\lceil t_{\mathrm{rel}}\rceil$. For every $i\ge 2$,HenceMultiply by $\pi (x)f_i(x{)}^2$ and sum over $i\ge 2$ to obtain the required inequality.

The squared $L^2(\pi )$ distance has the diagonal identityThe diagonal excess is nonnegative and decreases with time. ThereforeUsing the identity supplied in the question givesAt $t=8{\mathbb{E}}_{\pi }{\tau }_x$ the right side is at most $1/16$, up to the immaterial integer rounding. Thus

Put $T=t_{\mathrm{mix}}^{(2)}(a,1/4)$ and $m=\lceil t_{\mathrm{rel}}\rceil$. The expected local time isPart c and the supplied return identity giveThe second term is bounded by the same infinite sum. Part b now yieldsThus the hinted universal constant $C=9e/(e-1)$ works.

A family exhibits pre-cutoff for Markov chains if there are constants $0<A<B<\infty$ and times $t_n$ such that its worst-case total-variation distance tends to one at $A{t}_n$ and to zero at $B{t}_n$. For irreducible reversible chains, a standard necessary condition for pre-cutoff is the product conditionThe hypothesis that $t_{\mathrm{mix}}^{(n)}/t_{\mathrm{rel}}^{(n)}$ is bounded contradicts this condition, while $t_{\mathrm{mix}}^{(n)}\to \infty$ excludes a bounded-time degeneracy. Hence the family cannot exhibit pre-cutoff.

Let ${\Pi }_n(x,y)={\pi }_n(y)$. Since $P_n{\Pi }_n={\Pi }_n{P}_n={\Pi }_n$ and ${\Pi }_n^2={\Pi }_n$, the stationary-reset perturbation of a Markov chain satisfiesEvery row difference from stationarity is multiplied by the nonnegative scalar $(1-a_n{)}^t$, so

Write $r_n=t_{\mathrm{mix}}^{(n)}/t_{\mathrm{rel}}^{(n)}\to \infty$. ThenBy cutoff, at every fixed multiple $c/a_n$ the original chain is still asymptotically unmixed, while part i givesThus the new chain crosses between fixed distance levels gradually on the full scale $a_n^{-1}$: for example its $\epsilon$-mixing times are asymptotic to $a_n^{-1}\log (1/\epsilon )$. No two fixed multiples of one scale can make the limiting distance respectively one and zero, so the family has no pre-cutoff.

Every nonconstant eigenvalue $\lambda$ of $P_n$ becomes $(1-a_n)\lambda$. Hence, writing ${\gamma }_n=1/t_{\mathrm{rel}}^{(n)}$,Sincewe have ${\tilde{t}}_{\mathrm{rel}}^{(n)}\sim t_{\mathrm{rel}}^{(n)}$. Part ii gives ${\tilde{t}}_{\mathrm{mix}}^{(n)}\asymp a_n^{-1}$, and therefore

For a path $\Gamma$,by the Cauchy-Schwarz inequality. Average over ${\nu }_{xy}$, multiply by $\tilde{Q}(x,y)$, and sum. Reversing the order of summation in the definition of the two Dirichlet forms givesLet $M={\max }_x\pi (x)/\tilde{\pi }(x)$. The variational formula for variance givesTake a nonconstant eigenfunction attaining the Rayleigh quotient $\gamma$ for $P$. Then

Choose the uniform distribution on shortest paths equivariantly under graph automorphisms. Automorphisms preserve distances and send uniform shortest paths to uniform shortest paths, so vertex transitivity makesconstant in $x$. Summing this constant over vertices counts each path-edge incidence at most twice:Thus $\tilde{f}(x)\le 2n\Delta$, and each nonnegative summand satisfies

Compare simple random walk $P$ with the independent sampler $\tilde{P}(x,y)=\pi (y)=1/n$, whose spectral gap is one. Both stationary distributions are uniform. Route each transition $(x,y)$ of the sampler along a uniformly selected shortest path. For a directed graph edge $e$,Part i therefore bounds the congestion byPart a, equivalently the Canonical paths comparison theorem, gives

For each fixed output state $y$, the right-shift part has exactly two predecessors, each contributing $1/3$, and the left-shift part also has exactly two predecessors, each contributing $1/6$. Thus every column sum isThe transition matrix is doubly stochastic, so the uniform lawis invariant.

Track on the lifted integer line the coordinate refreshed at each step. It is a random walk $R_t$ with right-step probability $2/3$ and left-step probability $1/3$. Every visited residue modulo $n$ has had its bit replaced by an independent fair bit. Consequently the first time all residues have been visited is a strong stationary time for this shift-refresh chain on a hypercube.

For the upper bound, reaching level $n$ visits every residue, so the refresh time is at most ${\tau }_n$. The supplied moments giveFor any sequence $w_n$ with $w_n/\sqrt{n}\to \infty$, Chebyshev inequality and the strong-stationary-time bound imply

For the lower bound, choose integers $b_n$ such thatand consider ${\tau }_{n-2b_n}\wedge {\tau }_{-b_n}$. Its supplied mean is $3n-6b_n+o(1)$ and its variance is $O(n)$; after replacing $w_n$ by a sequence with $\sqrt{n}\ll w_n\ll n$, take for example $b_n=\lfloor \sqrt{w_n\sqrt{n}}\rfloor$. This satisfies the displayed scale separation, and the supplied moment bounds showBefore that exit, the visited interval has length less than $n-b_n$, so at least $b_n$ coordinates retain their initial values.

Start the chain from the all-zero vector. Conditional on the explored path, the number of one-bits is binomial with at most $n-b_n$ trials, whereas under stationarity it is $\mathrm{Bin}(n,1/2)$. Since $b_n/\sqrt{n}\to \infty$, standard binomial concentration separates these two laws; for instance the eventhas probability tending to one for the chain and to zero under $\pi$. ThereforeThe transition from one to zero occurs in an $o(n)$ window around $3n$, proving total-variation cutoff with cutoff time $3n$.