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

Center the board at the origin and map each white square $(i,j)$ toThe white squares become the integer points of the diamondand a bishop move changes exactly one coordinate. From $(u,v)$ the chain can move first to $(u,0)$ and then to $(0,0)$, since both points lie in $D_n$. Reversing such paths connects any two states, so the bishop random walk is an irreducible Markov chain.

Solved by gpt-5.6-sol high.

In the diamond coordinates, the horizontal line through $(u,v)$ has $2(n-|u|)+1$ points and the vertical line has $2(n-|v|)+1$ points. There is a numerical constant $a>0$, independent of $n$ and of the starting point, such that the walk enters the middle diamond $D_{n/2}$ within two steps with probability at least $a$. To see this, suppose $|u|\le |v|$, so $|u|\le n/2$. With probability at least $1/2$ the first move uses the longer horizontal line, and a fixed positive fraction of its choices have $|v^{\prime }|\le n/4$. From $(u,v^{\prime })$, the vertical line has length at least $3n/2$, is chosen with probability bounded below, and a fixed positive fraction of its points satisfy $|u^{\prime }|+|v^{\prime }|\le n/2$. The case $|v|\le |u|$ is symmetric.

Now couple two copies. Independently use the preceding construction until both lie in $D_{n/2}$, an event having probability at least $a^2$ in two steps. From $(u,v)$ and $(u^{\prime },v^{\prime })$ in that diamond, their horizontal line ranges overlap in at least $n+1$ values. A maximal coupling of the next moves can therefore, with probability bounded below, send them to $(u,w)$ and $(u^{\prime },w)$ for the same $|w|\le n/2$. Their vertical lines are then identical, and another maximal coupling makes the two states equal with probability bounded below. Thus there are constants $k$ and $b>0$, independent of $n$, for which the two copies coalesce during every block of $k$ steps with conditional probability at least $b$.

The coupling time consequently has a geometric tail. By the coupling inequality for total variation, for each fixed $0<\epsilon <1$,Since a nontrivial chain has mixing time bounded below by a positive constant, the mixing time has constant order.

Solved by gpt-5.6-sol high.