Number of moves necessary to solve Rubik's cube by pure chance

Suppose, random moves are made to solve Rubik's cube. A move consists of a $90$-degree-rotation of some side. The starting position is also random.

• What is $E(X)$, where $X$ is the number of moves until the cube is solved ?
• How many moves must be made, that the probability that the cube is solved, exceeds $99$% ?

Solution 1:

Each edge has 2 faces, providing for $12!\times 2^{12}$ possibilities.

Each vertex has 3 faces, providing for $8!\times 3^8$ possibilities.

Therefore if you dismantle the cube it can be reassembled in 519,024,039,293,878,272,000 possible states.

Thanks to Gerry Myerson for this: According to Singmaster's Notes on Rubik's Magic Cube, the total permutation of the edge and vertex cubes must be even. Then, if you orient all but one of the edges, the remaining one is forced, and similarly for the vertices, so only 1 in 12 possible assemblies of the cube is actually a "solvable" or "arrivable at by rotation" state.

Dividing the above number by 12 therefore confirms Turner and Gold's result (which i haven't seen first hand) that the number of states "arrivable at by rotation" is $43,252,003,274,489,856,000$.

Therefore any given random move has probability $1/43,252,003,274,489,856,000$ of completing the cube.

For such high $n$ the binomial will approximate the normal distribution, so the expected number of moves will be the mean.

I think Wolfram Alpha struggled with the number-crunching in my last answer so I've solved by substitution:

$0.5=\binom{n}{0}p^0q^n$ where $q=(1-1/43,252,003,274,489,856,000)$

$0.5=(1-1/43,252,003,274,489,856,000)^n$

$n\approx 3×10^{19}$ moves is the expected number of moves to solve it.

Repeating the substitution for 0.01:

$n\approx 1.992*10^{20}$ moves is the expected number of moves to reach 99% confidence.

Use of the binomial in this answer makes the technically incorrect assumption that the probability of solving on any particular move is not related to the probability of solving on a move n steps earlier. (i.e. there is no serial correlation). However as an experienced cube user I know that the cube very quickly diverges from its current position given random movements and therefore the effect of serial correlation will be very low.

This divergence is clearly illustrated by the fact that it follows from Rokicki, Kociemba, Davidson, and Dethridge's 2010 result that it takes at most 20 Singmaster moves to take the cube to any obtainable state you wish. Contrast that 20 moves with the expected number of random moves to solve the cube and you get an idea how minimal serial correlation will be.