Random solving of a Rubik cube .

Question

After playing a little with a Rubik cube I thought of the following problem :

Suppose we start with a solved Rubik cube (a general one , with $n^3$ cubes) . Then we choose one of the moves , each having a probability of $\frac{1}{6n}$ of being chosen , and apply it on our cube . We continue doing so ( choosing a new move randomly and then applying it and so on...) , until we reach the solved position again . What is the expected number of moves needed to solve the cube in this way ?

I thought about it and I think the answer should be $\infty$ (at least for $n \geq 3$) because there are a lot of random sequences of moves that will take a long time to solve the cube but I don't have a rigorous way to prove it.

For $n=2$ I'm not that sure if the answer should be finite or infinite (but I still tend to think it's infinite).

Thank you for your time to help me!

Answer 1

Consider a simpler scenario: suppose you have a biased coin, which shows Heads with probability $p > 0$. What is the expected number of attempts required to throw a Head? The probability that exactly $n$ throws are required is $q^{n-1}p$, where $q = 1-p$. So the expected number of throws is $\sum_{n=1}^\infty nq^{n-1}p = \dfrac{p}{(1-q)^2} = \dfrac{1}{p}$. Note in particular that this is finite!

Now, let $N$ be the maximum number of moves required to solve an $n \times n \times n$ Rubik's cube. Thanks to the efforts of countless dedicated investigators, we know that for $n=3$, we have $N=20$ according to the half-turn metric, and $N=26$ according to the quarter-turn metric (see for instance this link). But the exact value of $N$ doesn't matter; the number of positions is finite, and therefore the maximum number of moves required to solve a solvable position is also finite.

Suppose the number of moves available at each turn is $m$. You say that $m=6n$, and I won't argue with that; again, the important thing is that $m$ is finite. Then all you have to do to solve a position in $N$ moves or less is to pick the optimal move each time. The probability of doing this by chance is at least $p=m^{-N}$.

So if you consider a "coin flip" to be $N$ random moves in your Rubik's cube, then the expected number of coin flips is at most $\dfrac{1}{p} = m^N$. So the expected number of moves is at most $\dfrac{N}{p} = Nm^N$.

Answer 2

As you can see by reading the answers to this question involving a knight tour on a chessboard, we can determine the expected return time for any irreducible Markov chain by finding the unique stationary distribution; if the mass of the distribution at a given state is $p$, then the expected return time to that state is $\frac{1}{p}$. (Intuitively, if we process the Markov chain for a long time, we expect to be at the given state with probability $p$, so the average distance between returns to the state is $\frac{1}{p}$.)

In the case of a random walk on a graph $G$, the unique stationary distribution is given by making the mass at each vertex proportional to its degree. When the graph is regular (as is the case here), each vertex will have the same mass, namely $\frac{1}{|G|}$. So the expected return time for each vertex will be exactly $|G|$.

Thus the expected number of turns required to get back to the starting state of any type of Rubik's cube is equal to the number of positions of the cube.

Answer 3

The 2x2x2 Rubik's cube consists of 8 corner pieces. All permutations of these are possible, so that's 8! = 40320 possible permutations. Each piece also has three possible orientations, spaced 120 degrees apart (any one of the 3 colours on tha piece can be showing on the top or bottom face.) Detailed analysis will show that if the orientations of 7 pieces are specified, there is only one possible orientation for the last piece's (Rubik cubers call this "twist parity) so there are 3^7=2187 possible orientation states. Multiplying these together, there are 88179840 possible states for the 2x2x2 Rubik's cube. If we consider different rotations of the entire cube as equivalent, we must divide this by 24, giving 3674160 possible states.

The 3x3x3 Rubik's cube has in addition to the above, a centre piece and 6 face centres which do not move. It also has 12 edge pieces, which can be arranged in any of 12!=479001600 permutations. Each edge also has 2 possible orientations, and in a similar manner to the corners, if the orientation of 11 edges are specified only one orientation of the 12th edge is possible (Rubik cubers call this "flip parity.") there are thus 2^11=2048 possible orientation states. Multiplying these together, total number of states for the edges is 980995276800.

There is a third type of parity on the rubik's cube called swap parity, which means that the overall permutation of pieces must be even (ie corners even and edges even, or corners odd and edges odd.) So the overall number of states is 88179840 x 980995276800/2=43252003274489856000 (Because the centres of the faces offer a fixed reference, the division by 24 for rotations of the entire set of corners does not apply.)

This is a large number, but certainly not infinite. For analysis of how to work out the probability, see the other answers to this question.