Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 215 / 3

The Dirichlet form of a Markov chain isWhen $P$ is reversible, this equals $⟨f,(I-P)g{⟩}_{\pi }$.

Solved by gpt-5.6-sol high.

For a finite reversible lazy chain, the relaxation time is $t_{\mathrm{rel}}=1/\gamma$, where $\gamma =1-{\lambda }_2$ is the spectral gap. Its spectral profile isThe variational characterization of the spectral gap isEvery class $c_0^{+}(A)$ is contained in the class over which this last infimum is taken, so $\lambda (A)\ge \gamma$ and $\Lambda (r)\ge \gamma$. Therefore

Solved by gpt-5.6-sol high.

Let $N=|V_n|$. Since the degrees lie between $1$ and $\Delta$,The Generalized Cheeger inequality and ${\Phi }_{\ast }(u)\ge {\Phi }_{\ast }(c)\ge \alpha$ for $u\le c$ giveFor all larger $u$, part (a) gives $\Lambda (u)\ge 1/t_{\mathrm{rel}}$. Split the supplied spectral-profile integral at $c$ to obtain

Solved by gpt-5.6-sol high.

Under the standard intended reading that the added edges form a perfect matching between $G_n$ and $H_n$, the claim follows as follows. Degrees in $M_n$ remain bounded in terms of $\Delta$. For $A\subseteq V(M_n)$, write $A_G=A\cap V(G_n)$ and $A_H=A\cap V(H_n)$. The matching contributes at least $||A_G|-|A_H||$ boundary edges, while expansion inside $G_n$ contributes a constant multiple of $\min \{|A_G|,n-|A_G|\}$. A case split according as $|A_G|\le n/2$ or $|A_G|>n/2$ showsThus $M_n$ has a uniform Cheeger constant. Cheeger inequality gives a uniformly bounded relaxation time, while ${\pi }_{\min }\asymp 1/n$. The usual spectral mixing estimate, or part (b), then gives $t_{\mathrm{mix}}\lesssim \log n$.

If “adding $n$ edges” permits all $G_n$ vertices to attach to the same vertex of $H_n$, the assertion is false as written. Take $H_n$ to be a path and attach every vertex of the expander to one endpoint. A walk started at the other endpoint needs order $n^2$ time to reach the attachment endpoint, so its mixing time is not $O(\log n)$. The perfect-matching interpretation is therefore necessary.

Solved by gpt-5.6-sol high.