Local return moments and certified random-solving times for Rubik's Cube

Abstract

Consider the random walk on the standard $3\times3\times3$ Rubik's Cube that independently chooses one of the eighteen face turns with equal probability. Let $N$ denote the number of legal configurations and let $T_e$ be the first hitting time of the solved configuration, including time zero. We give the certified bounds$$1.0728316 < \frac{\mathbb{E}_\pi T_e}{N} < 1.0729459,$$where $\pi$ is uniform on the legal configurations. The same outward-rounded interval holds for $\mathbb{E}_xT_e/N$ for every configuration whose face-turn distance from solved is at least thirteen. The proof combines the established Green-function hitting-time identity with a degree-six polynomial resolvent certificate, exact return-word counts through length twelve, and a symmetry-averaged diameter estimate giving a spectral gap of at least $1/600$. The return counts were previously published in OEIS A061713 and are reproduced here by two independently implemented enumerations; all final inequalities use rational arithmetic. The certificate uses the classical matrix-moment framework to obtain an explicit finite-cube bound without computing the full spectrum or simulating rare solutions.