A Markov process on depth’s classes
To seek 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 specific 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 will only jump to the depth class 1 (there isn’t any class -1). Also, q_26 = 1: from the depth class 26 we will only jump to depth class 25 (there isn’t any 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 backwards and forwards with probabilities q_d and p_d. What happens after a protracted walk? or, how persistently does the walker visit a specific site after a protracted 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) needs to 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 are going to get the p_i’s and q_i’s.
Making an allowance for that p_0 = q_26 = 1, we will rewrite these as
These are generally 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 must 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:
Particularly, the last two inequalities are
Because D_27 = 0, we get that the lower and upper certain are equal, so
Or:
The sum of the population of the even sites needs to be equal to the sum of the population of the odd sites!
We will see this as an in depth balance between even and odd sites: every move is at all times to a special 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 chances one in each direction, their population needs to 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 info
The depth-population D_d reported within the source of the info that we’re planning to make use of is approximate for d = 19,20,21,22,23,24. So there isn’t any guarantee it’s 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!). Particularly, 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 tip)
A way out
The odd class appear to be underpopulated (it is a consequence of the approximation the authors selected to report the info). 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 25q_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 chances of going away from the solved state. The chances 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 resolve the cube: the random walker (or the cube’s random mover) can be “trapped endlessly” in a neighborhood of the depth class 21.