Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 215 / 4

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$.