Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a 3x3x3 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: http://en.wikipedia.org/wiki/Rubik's_Cube_group ). In 2011, Erik Demaine et. al. ( http://arxiv.org/abs/1106.5736v1 ) showed that any (n x n x 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 x n x 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 3x3x3 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 3x3x3 cube and $S_n$ for the n x n x 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 x n x 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.

share|improve this question
1  
The cover time is largely irrelevant here. What you're looking for is the hitting time. I would not expect to see a logarithmic factor here. –  Ori Gurel-Gurevich Dec 4 '12 at 7:10
add comment

2 Answers

up vote 8 down vote accepted

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

share|improve this answer
    
@Brendan McKay Right I think what you're saying makes good sense. For fun, I certainly would be curious to see a more rigorous argument. –  FloatingForest Dec 3 '12 at 0:04
    
@Brendan McKay Why is the expected number of solutions after $N$ steps, $E[x] = 1$? If we're taking a random walk of a Cayley graph, won't there be a large probability, each step, to revisit a previous state? –  FloatingForest Dec 3 '12 at 10:25
    
@FloatingForest: In Brendan's argument, the expected number of solutions you see on the $i$th step is $1/N$ for all $i$. Then sum over $i$ from $1$ to $N$. Expectation is always linear regardless of whether the variables are correlated. –  Timothy Chow Dec 3 '12 at 18:29
    
@Timothy Chow Egged myself :), good point. –  FloatingForest Dec 4 '12 at 3:50
1  
While I haven't tried to prove it rigorously, it seems quite obvious that the RW on rubik's cube is locally transient in the sense that if you look at the expected number of visits to the starting configuration before getting mixed is small (bounded, if you consider $n$ by $n$ by $n$ cubes). This means that the expected number of steps to hit a particular configuration is indeed proportional to the number of configurations. –  Ori Gurel-Gurevich Dec 4 '12 at 7:06
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.