A Markov process on depth’s classes

To search out p(d|N) we imagine the depth classes as sites of a Markov process. Let me explain:

A depth class d is the set of all of the cube’s states at a depth d (minimal variety of moves to the solved state). If we randomly selected a state in a depth class d, and we turn a random face with a random move, that can give us either a state in the category d + 1 , with a probability p_d, or a state in the category d -1, with a probability q_d. Within the quarter-turn metric there are not any self-class moves.

That defines a Markov process, where a selected site is an entire depth class. In our case, only contiguous d classes are one-jump connected. To be precise, it is a discrete-time birth-death Markov chain. Because the quantity of web sites is finite, the chain can also be irreducible and ergodic, and a novel stationary distribution exist.

We assume equally distributed probabilities for the choice of the random moves at every time. That induces some transition probabilities p_d, q_d (to be computed) between the depth classes. The quantity of random moves N is the discrete time of the Markov process. This can also be a one-dimensional random walker: at every site (depth class number d), the probability of going forward is p_d, and the probability of going backwards is q_d. This one dimensional chain is, roughly speaking, the “radial” direction within the Rubik’s graph (organized within the depth-radial layout).

The transition matrix

Any Markov processes is encoded in a transition matrix M. The (i,j) entry of M is the probability of jumping from site i to site j. In our case only the next entries are different from zero:

Here p_0 = 1: from the depth class 0 (containing just the solved state) we are able to only jump to the depth class 1 (there isn’t a class -1). Also, q_26 = 1: from the depth class 26 we are able to only jump to depth class 25 (there isn’t a class 27). For a similar reason, there are not any p_26 or q_0.

The stationary distribution

We mapped the motion of randomly moving the cube to a one-dimensional depth-class random walker jumping forwards and backwards with probabilities q_d and p_d. What happens after an extended walk? or, how repeatedly does the walker visit a selected site after an extended walk? In real life: how often is a depth class visited when the cube undergoes random turns?

In the long term, and regardless of what the start line was, the time the walker spends within the depth class d is proportional to the population D(d) of that depth class. That is the fundamental point here:

the (normalized) depth-population list D(d) must be interpreted because the vector representing the stationary distribution of our depth class Markov process.

Mathematically, D(d) is a left eigenvector of M

This matrix equation will give us 26 linear equations, from which we’ll get the p_i’s and q_i’s.

Considering that p_0 = q_26 = 1, we are able to rewrite these as

These are often known as detailed balance equations: the flux, defined to be the stationary site population times the jumping probability, is identical in each directions. The solutions are:

and p_i is obtained using p_i + q_i = 1.

Some conditions on the population of a depth class

There’s something interesting about these solutions. Because q_i is a probability we should always have that

and that translate into the next condition for the distribution D_k:

This can be a tower of inequalities that the depth-population D_k should fulfill. Explicitly, they could be organized as:

Specifically, the last two inequalities are

Because D_27 = 0, we get that the lower and upper sure are equal, so

Or:

The sum of the population of the even sites must be equal to the sum of the population of the odd sites!

We are able to see this as an in depth balance between even and odd sites: every move is all the time to a distinct and contiguous depth class. Any jump will take you from the odd depth class (the category of all of the odd depth classes) to the even depth class (the category of all of the even depth classes). So the odd to even class jump occur with probability 1 (and vise versa). Being the possibilities one in each direction, their population must be equal by detailed balance.

For a similar reason the Markov process will attain a period-two “stationary distribution” that switches between even and odd sites after every move (discrete time N).

An issue with the information

The depth-population D_d reported within the source of the information that we’re planning to make use of is approximate for d = 19,20,21,22,23,24. So there isn’t a guarantee it is going to satisfy all these conditions (inequalities). Don’t be surprised if we get some probabilities q_i out of the range [0,1] (as it’s the case!). Specifically, if we attempt to check the last condition (the even-odd population equality) it’s off by an enormous number! (update: see note at the top)

A way out

The odd class appear to be underpopulated (it is a consequence of the approximation the authors selected to report the information). To make things work (get probabilities within the range [0,1]), we resolve so as to add the previous big number to the population of the depth class 21 (the odd class with the best population, or, the one that can notice that addition the least). With this correction, all of the obtained probabilities appears to be correct (which implies the inequalities are also satisfied).

The jumping probabilities are:

p_i = 
{1., 0.916667, 0.903509, 0.903558, 0.903606, 0.903602, 0.90352, 0.903415, 
0.903342, 0.903292, 0.903254, 0.903221, 0.903189, 0.903153, 0.903108, 
0.903038, 0.902885, 0.902409, 0.900342, 0.889537, 0.818371, 0.367158, 
0.00342857, 6.24863*1e-12, 0.00022, 0.0833333}
# i from 0 to 25
q_i = 
{0.0833333, 0.0964912, 0.0964419, 0.096394, 0.0963981, 0.0964796, 
0.096585, 0.096658, 0.0967081, 0.0967456, 0.0967786, 0.0968113, 
0.0968467, 0.0968917, 0.0969625, 0.0971149, 0.0975908, 0.0996581, 
0.110463, 0.181629, 0.632842, 0.996571, 1., 0.99978, 0.916667, 1.}
# i from 1 to 26

Notice that nearly all the primary p_i (as much as i = 21) are near 1. These are the possibilities of going away from the solved state. The possibilities of going closer to the solved state (q_i) are almost 1 for i greater than 21. This puts in perspective why it’s difficult to unravel the cube: the random walker (or the cube’s random mover) might be “trapped eternally” in a neighborhood of the depth class 21.