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

A stopping time $T$ is a strong stationary time iffor every $x,y,t$. Thus $X_T\sim \pi$ and is independent of $T$. The separation distance isFor any strong stationary time,Hence $1-P^t(x,y)/\pi (y)\le {\mathbb{P}}_x(T>t)$, and maximizing proves the claim.

Observe the lazy walk on ${\mathbb{Z}}_{2^k}$ only after every second genuine jump. Two independent nearest-neighbor signs have sum $-2,0,2$ with probabilities $1/4,1/2,1/4$. Division by two therefore produces one step of the lazy simple random walk on ${\mathbb{Z}}_{2^{k-1}}$. The Strong Markov property at successive jump times proves

At $T_{{\tau }_{k-1}}^{(k)}$, part b and the strong-stationarity assumption make $X^{(k)}/2$ uniform on ${\mathbb{Z}}_{2^{k-1}}$ and independent of the stopping index. One further lazy step either stays or moves by one, each parity occurring with probability one half; conditional on the even residue already selected, this chooses uniformly between its two lifts to ${\mathbb{Z}}_{2^k}$. Thushas a uniform terminal state independent of ${\tau }_k$, and is a strong stationary time.

Take ${\tau }_0=0$ and apply part c recursively. A lazy walk makes a genuine jump with probability $1/2$, so the expected time required for $2j$ jumps is $4j$. Using the stated independence,The initial value zero solves this recurrence as

One step of the Glauber dynamics chooses a vertex $v$ uniformly and resamples its spin from its conditional Ising model distribution given all other spins. If the proposed new spin is $x$ and $S_v(\sigma )={\sum }_{w\sim v}\sigma (w)$, its update probability is

The worst-case distance to stationarity isThe Path coupling theorem says that if a coupling contracts an integer-valued path metric by a factor $\alpha <1$ for every adjacent pair, then

Couple two configurations differing at one vertex $u$ by choosing the same update vertex and the same uniform random number for the heat-bath update. Updating $u$ removes the disagreement. Updating a nonneighbor of $u$ cannot create one. At a neighbor $v$, the two conditional plus-spin probabilities differ by at most $\tanh \beta$, using the supplied identity. Since $u$ has at most $\Delta$ neighbors, the expected Hamming distance after one step is at mostThe Hamming diameter is $n$, so the Path coupling theorem gives

For a reversible transition matrix $P$ on $L^2(\pi )$, the spectral gap isEquivalently for a lazy chain,

For reversible chains $P,\tilde{P}$ with stationary laws $\pi ,\tilde{\pi }$, assign to every directed $\tilde{P}$-edge $(x,y)$ a path ${\Gamma }_{xy}$ of $P$-edges. Ifand $\tilde{\pi }(x)\le a\pi (x)$, the Canonical paths comparison theorem gives $\gamma (P)\ge \gamma (\tilde{P})/(aA)$, with equivalent conventions absorbing $a$ into the congestion.

Let $B=2{\mathbb{Z}}_{2n}^d$. The chain induced on $B$ by the lazy walk on $A$ has uniform stationary distribution, and an excursion from one even vertex can return there or reach only one of its $2d$ even lattice neighbors at displacement $\pm 2e_i$. Its transition conductances are bounded above by constants depending only on $d$. Testing its Dirichlet quotient withtherefore givesIndeed neighboring values differ by $O(n^{-1})$, while the variance of $f$ is bounded below uniformly. The supplied trace-chain theorem gives ${\gamma }_B\ge {\gamma }^{(2n)}(A)$, and hence

For stationary edge flow $Q(x,y)={\pi }^G(x)P(x,y)$, the bottleneck ratio isUsing $f=1_S$ in the variational characterization,Taking the infimum gives ${\gamma }^G\le 2{\Phi }_{\ast }^G$.

Put $B_r=B(x,s+r)$. Every transition leaving $B_r$ enters $B_{r+1}$, and stationarity bounds its flow by the stationary mass newly reached:While ${\pi }^G(B_r)\le 1/2$, the definition of ${\Phi }_{\ast }^G$ therefore givesIteration for $r=0,\dots ,t-1$ proves the formula.

Choose vertices $x,y$ at distance $d_G$, put $r=\lfloor (d_G-1)/4\rfloor$ and $R=\lfloor (d_G-1)/2\rfloor$. The radius-$R$ balls about $x$ and $y$ are disjoint, so one has stationary mass at most $1/2$; call its center $z$. Apply part b from radius $r$ to radius $R$:Here the exponent should be $R-r$, and $R-r\ge (d_G-2)/4$. ThereforeSince the relaxation time is $t_{\mathrm{rel}}^G=1/{\gamma }^G$, part a yields