Random walks on G

"Random scrambling" is actually a Markov chain on G: each step uniformly picks one of 18 HTM generators. The natural question: after how many steps is the distribution "close enough" to uniform on G? The answer is the mixing time, deeply linked to the cutoff phenomenon in random-walk theory (Diaconis–Shahshahani 1981 style).

24.1 Interactive: random-walk simulator

The random walk below ticks at 80 ms per step. Bars show a "proxy distance" (mismatched positions + orientations); watch it climb from 0 to ~40 and plateau. The three invariants stay pinned along the trajectory — visual proof that the walk lives inside the reachable coset.

24.2 Asymptotic estimate of mixing time

For a simple random walk on a general finite group with k generators, Diaconis–Shahshahani give an exact bound via representation theory:$$d_{TV}^2\le \frac{1}{4}\sum _{\rho \ne \text{triv}}{d}_{\rho }^2\Vert \hat{\mu }(\rho ){\Vert }^{2t}$$where $\hat{\mu }(\rho )$ is the Fourier coefficient of measure μ at irreducible representation ρ. For the cube, a back-of-envelope evaluation gives$$t_{\mathrm{mix}}(0.25)\sim \Theta ({\log }_2|G|)\sim 20\text{–}30.$$

WCA's 25-move scramble length is no accident: 25 sits near the mixing-time bound while staying away from the 20-move God's-number ceiling (meaningful scrambles shouldn't be known extremal states). In practice scramblers impose "no consecutive same-face" (aperiodic restrictions) to push the distribution closer to uniform — this is the heart of TNoodle, WCA's scramble generator.

24.3 The cutoff phenomenon

Diaconis's cutoff phenomenon (1980s): for many natural random walks on groups, $d_{TV}(t)$ stays near 1 for a long time, then drops sharply to near 0 within a narrow window:

Canonical example (Bayer–Diaconis 1992): 52 cards need $\frac{3}{2}{\log }_{2}52\approx 8.5$ riffles to mix. 7 still leaves traces; 9 is humanly indistinguishable from uniform. The cube's cutoff is not yet rigorously established; estimates put it at 22 ± 3 HTM moves.

24.4 Spectral gap & mixing rate

View the walk's transition matrix $P_t$ as a $|G|\times |G|$ giant matrix. Its eigenvalues $1={\lambda }_0>{\lambda }_1\ge {\lambda }_2\ge \dots$ govern mixing speed. The "spectral gap" $\mathrm{gap}=1-{\lambda }_1$ dominates:

Large gap = fast mixing = close to an expander. Whether the 18-generator Cayley graphs form an expander family (over n × n × n) is an active question. Numerical experiments put the 3×3's ${\lambda }_1\approx 0.65$, gap ≈ 0.35 — moderately fast.

24.5 Why does WCA pick 25 moves?

WCA's 25-move scramble is deliberate:

• Not too short (e.g. 10): distribution far from uniform, allowing competitors to exploit common openings.
• Not exactly 20: hits the God's-number ceiling, possibly producing superflip-class extremal states and skewing averages.
• Must filter same-face repeats: U U U U = identity. Without filtering, the random walk wastes 3/18 of steps. TNoodle restricts each step to 15 generators (excluding the previous face).
• 25 is above the estimated cutoff and above God's number: close to uniform but away from known extremal positions. Empirically guarantees fairness + diversity.

2×2 / 4×4 / 5×5 use longer scrambles (40+ steps), reflecting larger mixing times. Megaminx uses 70 steps because its generating set is smaller (slower mixing per step).

24.4 Transition matrix P on the Cayley graph

The random walk is a Markov chain on G with transition kernel$$P_{ij}=\mathrm{Pr}[X_{t+1}=g_j\mid X_t=g_i]=\{\begin{array}{ll}1/18& g_j=g_i\cdot s\text{for some}s\in S,\\ 0& \text{otherwise}\end{array}$$where $S$ is the 18-move HTM generator set. This is exactly "uniform-random-neighbour jump" on the cube's Cayley graph.

P is doubly stochastic (each row and column sums to 1, since S = S⁻¹): immediately giving ${\pi }_g=1/|G|$ as the stationary distribution. Moreover P is reversible w.r.t. π: ${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$, so as an operator on ${\ell }^2(G,\pi )$ P is self-adjoint, hence has real spectrum.

24.5 Spectrum and the mixing-time bound

By the spectral theorem, P has real eigenvalues $1={\lambda }_1>{\lambda }_2\ge \cdots \ge {\lambda }_{|G|}\ge -1$, with ${\lambda }_1=1$ for the uniform eigenvector. The spectral gap $\delta =1-|{\lambda }_2|$ controls mixing:

The matching lower bound: $t_{\mathrm{mix}}\ge \frac{1}{2}\cdot \frac{|{\lambda }_2|}{1-|{\lambda }_2|}\cdot \log (1/(2\epsilon ))$. With $\log |G|\approx 65.2$ and the empirically observed $|{\lambda }_2|\approx 1-1/20$, the bound yields $t_{\mathrm{mix}}(0.25)\sim 20\text{–}25$ — matching the simulation in 24.7.

24.6 Diaconis–Shahshahani on Sₙ

The classical Diaconis–Shahshahani result (1981): on the random transposition walk on $S_n$, $t_{\mathrm{mix}}(\epsilon )=\frac{1}{2}n\log n+c(\epsilon )\cdot n$, with a sharp cutoff near $\frac{1}{2}n\log n$. For $n=52$ cards (transposition model): $\frac{1}{2}\cdot 52\cdot \log 52\approx 103$ transpositions. (Different model from the 7-riffle-shuffle result, but the spectral argument is the same flavour.)

For the cube, $S_8\times S_{12}$ contributes $\frac{1}{2}\cdot 12\cdot \log 12\approx 14.9$ as the "permutation" mixing scale — but the orientation part $(\mathbb{Z}/3{)}^7\times (\mathbb{Z}/2{)}^{11}$ separately mixes in ~7 and ~11 steps. Together this predicts 15–20, matching the empirical value below.

24.7 Empirical: cube t_mix ≈ 18–22 steps

Data from Monte Carlo: estimating $d_{TV}$ across ~10⁵ random-walk trajectories on G. The cutoff midpoint ≈ 18 is no coincidence with §23's "random scramble average distance ~18" — both come from the same saturation of the Cayley graph at depth 18.