6
$\begingroup$

I'm interested in some questions about the computational complexity of bounding the mixing time of random walks on Cayley-graphs of finite groups like that of the Rubik's Cube Group $G$. Determining that $20$ is the diameter (God's number) of the Rubik's Cube Group under the half-turn metric with Singmaster generating set $s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$ was a wonderful result. I'm curious about follow-up questions, such as determining how many half-turn twists would it take to get the cube fully "mixed" to $\epsilon$-close to the uniform stationary distribution $\pi$.

For example, noting that there are $\vert s \vert=18$ moves in the half-turn metric, and calling $m$ the variational-distance mixing time, is there a promise to the effect of:

  • If $n\ge m$, for all but a very small number of elements $\epsilon$ of $g\in G$, there very close to $\frac{18^n}{\vert G \vert}$ ways of writing $g$ as words of length $\le n$, and

  • If $n \lt m$, there is a large subset $A\subseteq G$ with $g\in A$ such that there are only $\frac{18^n}{2\vert G \vert}$ ways of writing $g$ as words of length $\le n$?

My intuition is that, after the cube is fully mixed with $n\ge m$ moves, there should not be a large special subset $A\subseteq G$ of elements that need a lot more or a lot less than $18^n$ ways of writing them, starting from the solved position. On the other hand, if the cube has only been scrambled with $n\lt m$ twists, then there should be a large subset $A$ that has elements that are in some sense difficult to describe.

Here I think of $\epsilon$ as about $\frac{1}{10^9}\vert G\vert$ straggler positions such as the superflip that are "difficult" to describe. I think of the size of $A$ as much larger, e.g. about $\frac{1}{10}\vert G\vert$ or so, if the walk hasn't transitioned to fully mixed.

Is such a promise reasonable? Does it depend on whether the random walk exhibits a cutoff phenomenon?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.