User floatingforest - MathOverflow

Counting the number of Rubik's cube states in which k = 0 to 4 of the faces are "solved"

2012-12-20T06:28:19Z

Imagine an $n \times n \times n$ Rubik's cube, where we can transition the state of the cube using Singmaster moves under either the face- or quarter-turn metrics. We call a face of this cube "solved" if all of the symbols on the face are of the same color (there are six total colors).

How many total cube states are there when $k = {0, 1, 2, 3, 4}$ of the cube faces are solved, and what "distribution" are these states drawn from? Namely, what is the probability that they contain the fully solved state of the cube? Is this probability what one would expect for a uniform random sampling from the set of all possible cube states?

Note: This is (hopefully) a simplification of an earlier question asking for the probability that a greedy algorithm solves a Rubik's cube, where once a face is solved, the algorithm cannot backtrack and perturb the face (though rotations of the face are allowed).

Note 2: I know there are only going to be a small number of possible cube states when we freeze a face. Exact counts would be fantastic, but my goal here is to understand what distribution they are being drawn from.

Manhattan distance vs. absorption time on an unbounded integer lattice

2012-12-03T11:59:15Z

Imagine I have unbounded $d$-dimensional integer lattice where I take two vertices, $v_a$ and $v_b$, separated by a fixed Manhattan distance $L$, and I release a random walker at $v_a$ and allow for absorption (with a probability of unity) at $v_b$. How does the probability of absorption and the mean first passage time (MFPT) for absorption at $v_b$ scale with $L$?

Polya demonstrated the the origin recurrence probability, $p(d)$, of a random walker on a $d$-dimensional integer lattice is unity for $d = {1,2}$ and that:

$p(3) = \frac{6^{\frac{1}{2}}}{32*\pi^3} * \Gamma(\frac{1}{24}) * \Gamma(\frac{5}{24}) * \Gamma(\frac{7}{24}) * \Gamma(\frac{11}{24})$

( http://mathworld.wolfram.com/PolyasRandomWalkConstants.html )

From Polya's result I would guess that if $L \approx 1$, the probability of absorption at $v_b$ would be $\approx p(3)$. However, that's simply a guess, and offers little information on the MFPT for absorption.

What might change if we instead consider a Brownian motion?

Update :: I am most interested in a good estimate for how the absorption probability and MFPT scales as $L$ goes from $1$ to $\infty$, rather than an asymptotic.

Update 2 :: I have written a post on mathematics stackexchange asking for further explanation of Omer's answer. My concern was that such a discussion might be too low level for this forum. I hope this is an appropriate thing to do.

http://math.stackexchange.com/questions/250735/the-integer-lattice-green-function-and-its-relation-to-hitting-probabilities-t

Update 3 :: I'm simulated random walks on an infinite $Z^3$ integer lattice, where $10^5$ steps without absorbence at a target vertex (near the origin) counts as the walker diverging to infinity. Walks are initialized at the origin, (0,0,0), and values for means-square-displacement (MSD) and the number of steps prior to absorption are averages over $10^3$ iterations.

Absorbing target = {0,0,0}

Fraction of absorbed walks prior to 10^5 steps = 353/1000 = 35.3%

Mean displacement of walker = 279.824

Mean[# steps until absorbance or 10^5 steps] = 64731.3

Mean[# steps conditioned on absorbance] = 88.7

Absorbing target = {0,0,1}

Fraction of absorbed walks prior to 10^5 steps = 335/1000 = 33.5%

Mean displacement of walker = 288.447

Mean[# steps until absorbance or 10^5 steps] = 66628.2

Mean[# steps conditioned on absorbance] = 382.7

Absorbing target = {0,0,2}

Fraction of absorbed walks prior to 10^5 steps = 155/1000 = 15.5%

Mean displacement of walker = 367.702

Mean[# steps until absorbance or 10^5 steps] = 84556.8

Mean[# steps conditioned on absorbance] = 366.5

Absorbing target = {0,0,3}

Fraction of absorbed walks prior to 10^5 steps = 114 / 1000 = 11.4%

Mean displacement of walker = 385.576

Mean[# steps until absorbance or 10^5 steps] = 88642.4

Mean[# steps conditioned on absorbance] = 371.9

Absorbing target = {0,0,15}

Fraction of absorbed walks prior to 10^5 steps = 16 / 1000 = 1.6%

Mean displacement of walker = 430.08

Mean[# steps until absorbance or 10^5 steps] = 98427.1

Mean[# steps conditioned on absorbance] = 1693.8

Absorbing target = {0,0,30}

Fraction of absorbed walks prior to 10^5 steps = 9 / 1000 = 0.9%

Mean displacement of walker = 440.352

Mean[# steps until absorbance or 10^5 steps] = 99161.4

Mean[# steps conditioned on absorbance] = 6822.2

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

2012-12-02T14:12:04Z

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 http://mathoverflow.net/questions/35765/expected-number-of-steps-for-a-discrete-random-walk-to-visit-every-point-on-an-n).

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.

Comment by FloatingForest

2012-12-20T18:34:39Z

@Gerhard Paseman Do you think those cube states are random samples of all possible cube states, or somehow biased?

Comment by FloatingForest

2012-12-20T14:42:28Z

@Francois Brunault Well, I'm allowing rotations of the face, so 4^3 = 64 states are possible once we fix one face, but you're absolutely right. What I'm trying to understand is, what is the probability that the solved cube is one of those states? Or are those states more or less a random sample of all possible cube states?

Comment by FloatingForest

2012-12-20T13:12:33Z

@Brendan McKay Version (1) is what I had in mind. I don't want to condition on the cells being in the correct positions for a solved cube.

Comment by FloatingForest

2012-12-20T12:39:34Z

@Francois Brunault I'm looking to make a statement of just how frequently you can solve the cube when you fix one or more faces. The answer, no doubt, will be "very infrequently".

Comment by FloatingForest

2012-12-20T10:06:21Z

@Greg Martin :)

Comment by FloatingForest

2012-12-20T04:41:13Z

@Gerhard Paseman Admittedly though, if you have k=2 and the two faces are not on opposite sides of the cube, no further moves will permitted.

Comment by FloatingForest

2012-12-20T04:36:38Z

@Gerhard Paseman You can rotate the face or the $n - 1$ "stacks" of cells below this face.

Comment by FloatingForest

2012-12-05T13:36:23Z

@Alexandre Eremenko Right, I'm having some trouble understanding how this problem works in the continuum limit, so I keep talking about Manhattan distances instead of Euclidean distances (where I'm not sure why it makes sense to talk about them on a lattice). Small $L$ means $L \leq 100$ or so.

Comment by FloatingForest

2012-12-04T03:50:39Z

@Timothy Chow Egged myself :), good point.

Comment by FloatingForest

2012-12-03T20:17:44Z

@Alexandre Eremenko I'm most interested in the regime where $L$ is small. I'd like to understand how the MFPT increases with $L$ in this regime.

Comment by FloatingForest

2012-12-03T12:56:06Z

@Squark, thanks, it makes sense to me that that's true if $L$ is finite.

Comment by FloatingForest

2012-12-03T10:25:48Z

@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?

Comment by FloatingForest

2012-12-03T00:04:11Z

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