5
$\begingroup$

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?"

|cite|improve this question
$\endgroup$
  • $\begingroup$ It must be $\geq 17$ $\endgroup$ – Dan May 31 '14 at 14:22
  • 2
    $\begingroup$ @Dan Well, $\geq 20$ (it was proven by computation that $20$ is indeed "God's number) $\endgroup$ – MCT May 31 '14 at 14:38
  • $\begingroup$ I think you'll have to settle for "close enough". Compare the problem of shuffling a deck of cards, which has been extensively (but I think not exhaustively) studied. $\endgroup$ – David K Jun 3 '14 at 19:35
  • 1
    $\begingroup$ Are your moves uniformly random? $\endgroup$ – PyRulez Jan 25 '18 at 18:29
4
$\begingroup$

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

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.

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.

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:

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thomas your claim sounds cool! Under what metric are you claiming that the pocket cube has a mixing time of $24$/$25$? For example, the Cayley graph is not bipartite under the half-turn metric. Also, how were you able to exhaustively establish the above? Did you write all $6^{23}$ (resp. $6^{24}$) words of length $=24$ (resp. $=25$) with generating set $s=\langle F, F', U, U', L, L'\rangle$, and determine which element of $G$ each word corresponded to? $\endgroup$ – Mark S Apr 14 at 13:38
1
$\begingroup$

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.

|cite|improve this answer
$\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.