Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 204 / 4

Project $X$ to its label in ${\mathbb{Z}}^2$. At each step the label makes a nearest-neighbor move with probability $4/5$ and holds with probability $1/5$ when $X$ crosses between layers. This lazy planar random walk is recurrent because ordinary random walk on ${\mathbb{Z}}^2$ is recurrent.

Whenever the label returns to that of $x_0$, the layer coordinate belongs to a two-state irreducible chain, and there is a uniformly positive chance to equal the original layer. Infinitely many label returns therefore give infinitely many returns to $x_0$. Thus simple random walk on $G$ is recurrent.

The Aldous-Broder algorithm starts the recurrent random walk at $x_0$ and, whenever it first visits a vertex $v\ne x_0$, adds the edge by which it entered $v$. Recurrence ensures that every vertex is eventually visited. The collection of first-entrance edges is a spanning tree and has the infinite-volume uniform spanning-tree law.

Fix a simple path of 2022 vertices in the first layer. The event that all its edges belong to the uniform spanning tree has positive probability: a finite acyclic edge set can be extended to a spanning tree in every sufficiently large finite exhaustion, and the transfer-current determinant for that forest has a positive infinite-volume limit.

The event that $T_1$ has a component of size at least 2022 is invariant under translations of ${\mathbb{Z}}^2$. The uniform spanning-tree law on this transitive recurrent graph is translation ergodic, so an invariant event of positive probability has probability one. Therefore $T_1$ almost surely has such a component.

The event that $T_1$ is connected is translation invariant and hence has probability zero or one. Layer-exchange symmetry gives the same probability for connectivity of $T_2$. If $T_1$ were connected almost surely, both induced forests would therefore be connected almost surely.

On that event the spanning tree must contain exactly one vertical edge: it needs at least one to join the two layers, while two vertical edges together with the unique paths inside the connected $T_1$ and $T_2$ would form a cycle. But a translation-invariant random set cannot contain exactly one vertical edge almost surely. Every specified vertical edge would have probability zero of being the unique one, and their countable union would still have probability zero. This contradiction proves that $T_1$ is almost surely not connected.