4
$\begingroup$

Consider the permutation group of the Rubik's cube $G$: http://en.wikipedia.org/wiki/Rubik%27s_Cube_group

We have that $$\lVert G\rVert = 2^{27}\times 3^{14}\times 5^3\times 7^2\times 11=43,252,003,274,489,856,000\approx 4.325\times 10^{19}$$

Say we randomly sample cube states. More specifically, we take a cube, tie a blindfold on ourselves, and make some arbitrarily large number of random moves, then untie the blindfold and look at the cube state (ignoring everything during mixing). The idea is that we want to uniformly sample cube states, and not simply take a random walk on the cube's Cayley graph where all sorts of correlations will crop up based on previous states.

Is the probability of solving the cube during any given random sampling $\frac{1}{||G||}$? Or is the space larger because $||G||$ does not include automorhisms, reflections, or other symmetries that might decrease the probability of observing the solution state? What is the true probability of seeing a cube solution during any given sampling event? Can every cube solution be realized (in terms of the nearest-neighbor graph for colored faces)? Is it, for example, true that every state is unique up to the automorphisms of the cube, or do some states have higher probabilities than others because they are more or less symmetric?

$\endgroup$
1
$\begingroup$

Mathologer has a nice video that talks about all of these.

As long as the "arbitrary large number of random moves" is greater than the "mixing time," then randomly walking along the Cayley graph is the same as uniformly sampling cube states. The answer to the question in the title is $\Vert G\Vert$.

The mixing time of the Rubik's cube group under the half-turn metric is, I believe, unknown at this time, but is at least $20$, because the diameter of the Cayley graph under the half-turn metric is $20$. I suspect that the mixing time is not much larger than $30$ or so, for similar reasons as to why only $7$ dovetail shuffles are required to mix a random deck of $52$ cards.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.