Minimum number of random moves needed to uniformly scramble a Rubik's cube?

Question

Follow up from my last question: $3 \times 3$ Rubik's cube scrambling question

I am talking about $3 \times 3$ Rubik's cubes. Start with a solved cube. Then make some amount of random moves (where moves are defined using the half-turn metric: any twist of the face, i.e. 90 degrees counterclockwise, 90 degrees clockwise, 180 degrees are each one move). After how many moves will each of the 43 quintillion states be equally likely? If the answer is "infinitely many," can someone give some idea of how many moves will be "close enough?"

Answer 1

The term "devil's algorithm" describes a move sequence which, during execution, will go through all possible 43,252,003,274,489,856,000 states of the 3x3x3 Rubik's cube without visiting any state more than once. That is, every possible state will be equally likely when executing the sequence.

Bruce Norskog actually found such a Hamiltonian circuit for the 3x3x3 Rubik's cube in early 2012 (he and Mikhail Rostovikov found such sequences for the 2x2x2 a few months earlier independently). His sequence is defined in single quarter turns. Since a new state is reached with every move of his sequence (in theory), and since every state is only visited once, then the number in quarter turns it contains is 43,252,003,274,489,856,000 (the number of possible states).

http://www.speedsolving.com/forum/showthread.php?35505-A-Hamiltonian-circuit-for-Rubik-s-Cube

Therefore, it is still unknown what the maximum number of half turns such a sequence needs to contain, but clearly it is at most 43,252,003,274,489,856,000 half turns.

Answer 2

I was able to find several resources on the Rubik's cube group - much more than the last time I checked :-)

• Group Theory and the Rubik's Cube
• The Mathematics of the Rubik's Cube: Introduction to Group Theory and Permutation Puzzles

One can study the group of symmetries of the Rubik's cube and the Cayley Graph generated by the rotations U,D,L,R,F,B which correspond to the twist of the up down left right front back faces.

• The diameter of the Rubik's cube group is twenty -- this paper explains you can move from any position to another in 20 moves or less. This sequence of moves can be very hard to find but it exists...

Your question is about how long it takes to scramble a Rubik's cube... in math jargon it is the mixing time of a random walk on a Cayley graph of the Rubik's cube group. I don't know the specific case of the Rubik's cube group, but Diaconis and Bayer showed it takes about 7 shuffles to get a uniform distribution on a deck of cards, that is about $52! = 8 \times 10^{67}$ possibilties.

• Trailing the Dovetail Shuffle to its Layer

In the case of random walk generated by twists of the Rubik's Cube is a special case of the theory of mixing times of random walks on groups:

• Lectures on Mixing Times: A Crossroad between Probability, Analysis and Geometry
• Markov Chains and Mixing Times

Answer 3

You only converges towards the uniform distribution, so you a priori need an infinite number of shuffles...The good concept, however, is the one of "Markov chain mixing time", i.e., the number of step so that any initial Dirac distribution is transformed into a distribution at distance at most 1/4 (this is an arbitrary value) from the uniform distribution. A very good book on the subject : Markov chain mixing time, by Yuval Peres, Elizabeth Wilmer and David Levin. There are also interesting results in "Random Walks on Graphs: A Survey" by Laslo Lovasz.

You can easily show that the mixing time of the Rubik cube is at least 18, simply using the total number of configurations and the fact that you can reach at most 12 new cubes after each move. It is rather close to the diameter of the Rubik graph (20) or the average distance between two cubes (around 17).

General theorems yield poor upper bound (I remember having computed some time ago the upper bound 1600 moves). My personnal guess is that something like 45 moves should be sufficient, but I have no proof. Actually, it is mainly based on my experiments on the 2x2x2 cube (pocket cube) : in this case I was able to compute exhaustively how the distance to the uniform distribution varies: I found that the mixing time is of 24 or 25 moves (24 or 25 because the graph is bipartite). Recall that the diameter is 13 in this case.

I would be very interested in further results. Can we for example approximate the expander ratio of the Rubik cube graph? The second largest eigenvalue of the adjacency matrix?