Solving a Rubik's cube via a series of randomly selected (quarter-turn) Singmaster moves

Question

In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a $3\times3\times3$ Rubik's cube, starting in an arbitrary configuration, can strictly be solved in at most 20 Singmaster moves (under the face-turn metric) from Rubik's Cube move group $(G, *)$, where $*$ is the concatenation operation (summarized here: https://en.wikipedia.org/wiki/Rubik%27s_Cube_group ). In 2011, Erik Demaine et. al. (Algorithms for Solving Rubik's Cubes, arXiv:1106.5736v1 ) showed that any ($n \times n \times n$) Rubik's cube can optimally be solved in $\Theta (\frac{n^2}{\log(n)})$ steps, also under the face-turn metric.

Say we restrict ourselves to the simpler quarter-turn metric (only allowing for 90 degree rotations), and set up the following scenario:

We hand a ($n \times n \times n$) Rubik's cube to a robot, and program the robot to execute an random set of 90 degree Singmaster moves in $G$, then stop when the cube is solved. We know that the number of total cube states for a $3\times3\times3$ cube is: $||G|| = (2^{27}.3^{14}.5^3.7^2.11) = 43,252,003,274,489,856,000$ (Turner and Gold 1985, Schonert), and we can therefore use the negative binomial distribution calculate the mean number of random system states we need to sample to find a "finished" cube (call this value $S_3$ for the $3\times3\times3$ cube and $S_n$ for the $n \times n \times n$ cube). However, the robot is performing random quarter-turn moves, not necessarily randomly sampling cube configurations.

What distribution can we expect for the number of random 90 degree Singmaster moves necessary for the robot to complete the cube? I suppose we can calculate an upperbound for the expected mean number of required moves by taking a product of $S_n$ and the mean number of random moves necessary to "mix" the cube (I'm unaware of an estimate for this time), but can we do better? Also, I would guess that the "mixing time" for the cube is much faster than the solution time, making it the case that the initial state of the cube shouldn't matter.

(I'm not entirely opposed to allowing for arbitrary 90 or 180 degree Singmaster moves by the robot, but it just seems simpler to only consider the set of quarter-turn moves.)

Update :: Based on Brendan McKay's answer, which I mostly agree with, I intuitively feel that that the number of steps to find a solution for a ($n \times n \times n$) cube via a random walk on the cube's Cayley graph, should be something like $\Theta (||G|| \log (||G||))$. This intuition is coming from the scaling for the expected coverage time for a random walk on an integer lattice.

From: Jonasson, J., Schramm, O. On the cover time of planar graphs. Electronic Communications in Probability 5, pp. 85 - 90 (2000), we have that the cover time for a $d$-dimensional integer lattice $G$ with $n$ vertices scales as: $\Theta(n^2)$ for $d = 1$, $\Theta(n (\log n)^2)$ for $d = 2$, and $\Theta(n \log n)$ for $d \geq 3$. (hat tip to Andreas Rüdinger for his answer to Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice).

For the Cayley graph of a generalized Rubik's cube, it seems like we're in the limit of the sort of connectivity on an integer lattice that yields $\Theta(n \log n)$ covering times. So I suppose, on average, it should take about half this many steps to find the solved cube configuration?

Obviously this is very very sketchy reasoning, and I hesitate to actually write it down.

Answer 1

I think the expected time for stumbling across the solution is roughly proportional to the number of configurations. The process you describe is walking randomly on a Cayley graph. The limiting distribution is uniform, so after a large number of steps you will be in approximately a random place and the chance of that being the solution is the reciprocal of the number of vertices (i.e. the number of configurations). If someone expert in rapid mixing of Markov chains comes along, they will tell us if this argument can be made rigorous.

ADDED: This much is certain: Say $N$ is the number of configurations. If you start at a random configuration, then the probability of being at the solution configuration after $i$ steps is exactly $1/N$ for every $i$. However these are not independent events. The expected number of solutions seen in the first $N$ steps is exactly 1, but it does not follow that the expected wait for the first solution is $N$.

Answer 2

I don't see how this can be answered without crunching through lots of the data generated in Rokicki et al (RKDD)'s calculation. Also I'd guess (off the top of my head) that the expectation value is infinite.

For a given cube state S, let L(S) be the minimal number of turns needed to solve S. RKDD showed L(S)<=20 for all S. Let S+r denote the cube state reached by performing move r on S. There are three possibilities: 1) L(S+r)=1+L(S), i.e. r has made the cube more disordered than it was; 2) L(S+r)=L(S), i.e. r hasn't "improved" S but hasn't made it worse; 3) L(S+r)=L(S)-1, i.e. the move actually makes progress toward a solution.

It seems pretty likely to me that in the more ordered states, most of the available moves won't make progress, and probably most lose progress (add disorder). Even for L=20 (no more disorder is possible) it wouldn't surprise me if most moves don't make progress. Also, the set of (say) L=19 states that can be reached from an L=20 state might be a small fraction of all the L=19 states, and might have different likelihood (higher or lower) of reaching L=18 on the next move than a random L=19 state would have.

It might be feasible to solve this problem exhaustively for the 2x2x2 cube without too much computer resources. For 3x3x3, if you've got a database that lets you quickly determine L(S) for arbitrary S, then you can do some statistical sampling, but we know that the effort it takes to make such a database (it's a possibly proper superset of what RKDD did) is enormous.

Answer 3

If we fix the axes and the centre-faces, which only rotate on the spot, we're left with 12 "edges cubes" and 8 "vertex cubes". Hold a Rubik's cube in your hand, then disassemble it, and you will see what I mean.

Each "edge cube" can occupy 12 places and has 2 faces, providing for $12!\times 2^{12}$ possibilities.

Each "vertex cube" can occupy 8 places and has 3 faces, providing for $8!\times 3^8$ possibilities.

Therefore ignoring the for all intents and purposes identical, centre squares and orientations of the cube, the cube has 519,024,039,293,878,272,000 possible states. Turner and Gold's result excludes the $\frac{11}{12}$ states of the cube which cannot be reached by rotation - only attainable if the pieces are removed and reassembled!

Using Turner and Gold's result the probability of solving it on any given random move is therefore 1 in 43 billion billion.

Knowing from experience that one rarely returns to the same position by random, it can be deduced that serial correlation will have a minor effect upon the cube's path so its behaviour will closely approximate a simple binomial probability.

$n$ being large, this will approximate a normal distribution so the expected number of moves is given by the probability of solving it zero times in $n$ moves equalling $0.5$.

$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=3×10^{19}$ moves should be a pretty accurate estimate of the expected number of moves to solve it.