10
$\begingroup$

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!

$\endgroup$
14
  • $\begingroup$ You choose a different move every time or you apply the same move over and over again? I think the former one, right? $\endgroup$
    – user301452
    Jan 11, 2016 at 15:28
  • $\begingroup$ @menag Each of the moves isn't influenced by each of the others . Each of the moves is chosen separately so I don't always use the same move . $\endgroup$
    – user252450
    Jan 11, 2016 at 15:30
  • 1
    $\begingroup$ quora.com/… $\endgroup$
    – vadim123
    Jan 11, 2016 at 15:32
  • 4
    $\begingroup$ Why would it be infinite? From every state of the cube, there is a nonzero chance that you will only apply the best move from that point on until the cube is solved. $\endgroup$
    – Tim Vermeulen
    Jan 11, 2016 at 15:32
  • 2
    $\begingroup$ @TimVermeulen: Your comment does not, by itself, imply that the expected solving time is finite (although it is). $\endgroup$
    – TonyK
    Jan 11, 2016 at 15:37

3 Answers 3

Reset to default
19
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Nice! My first reaction was that this couldn't possibly be right; surely the expected number of turns is smaller if a half-turn is counted as one move rather than two? Then I realised that if a half-turn is one move, you can actually skip over the solution without stopping. $\endgroup$
    – TonyK
    Jan 11, 2016 at 17:47
7
$\begingroup$

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$.

$\endgroup$
5
  • 2
    $\begingroup$ For the asker's benefit, note a crucial point here: The case of the coin flips is much cleaner than the case of the cube, because the coin flips are independent and all share the same probability. In the case of the cube being randomly scrambled, although the "trials" here, consisting of $N$ moves, are far from being independent, you can still place a uniform bound on the probability of success in each trial, predicated on the state of the cube at the beginning of that trial. This is what allows you to place an upper bound on the expected number of moves. $\endgroup$
    – Dustan Levenstein
    Jan 11, 2016 at 16:25
  • $\begingroup$ at each move, the distance of the current state $x_n$ from the solution $x_0$ is $d_n \pmod{20}$ where $20$ is the maximum number of moves needed to solve the cube. I'm wondering if the rubik's cube is symmetric enough to prove that the probability $p(d_{n+1} | x_n) =p(d_{n+1} | d_n)$ i.e. the probability to increase or decrease or keep the distance at the same value only depends on the current distance and not on the particular state ? $\endgroup$
    – reuns
    Jan 11, 2016 at 17:06
  • 1
    $\begingroup$ The solution is not related at all to the maximal length $N$ introduced here. See Deedlit's answer for the correct result. $\endgroup$
    – Hagen von Eitzen
    Jan 11, 2016 at 17:38
  • 1
    $\begingroup$ @Hagen: Yes, Deedlit's surprising answer shows that you are right. (But my answer is not wrong; and perhaps it is more accessible to the OP.) $\endgroup$
    – TonyK
    Jan 11, 2016 at 17:44
  • $\begingroup$ @user1952009 : Sadly, no. There are states with only one minimal path to solved and other states with more than one minimal path even at distance $2$. The "checkerboard" is another state with several distinct minimal paths to solved, although "most" states have a single path to solved. Now, we probably can bound this effect, but I expect the result would be rather "floppy". $\endgroup$
    – Eric Towers
    Jan 11, 2016 at 23:35
0
$\begingroup$

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.

$\endgroup$

Your Answer

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