**A Markov process on depth’s classes**

To find ** 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 the cube’s states at a depth

**(minimal number of moves to the solved state). If we randomly chose a state in a depth class**

*d***, and we turn a random face with a random move, that will give us either a state in the class**

*d***with a probability**

*d + 1 ,***, or a state in the class**

*p_d***with a probability**

*d -1,***In the quarter-turn metric there are no self-class moves.**

*q_d.*That defines a Markov process, where a particular site is a whole depth class. In our case, only contiguous ** d **classes are one-jump connected. To be precise, this is a discrete-time birth-death Markov chain. Because the amount of sites is finite, the chain is also irreducible and ergodic, and a unique stationary distribution exist.

We assume equally distributed probabilities for the selection of the random moves at each time. That induces some transition probabilities ** p_d, q_d **(to be computed)

**between the depth classes. The amount of random moves**

**is the discrete time of the Markov process. This is also a one-dimensional random walker: at every site (depth class number**

*N***, the probability of going forward is**

*d)***and the probability of going backwards is**

*p_d,***This one dimensional chain is, roughly speaking, the “radial” direction in the Rubik’s graph (organized in the depth-radial layout).**

*q_d.*## The transition matrix

Any Markov processes is encoded in a transition matrix ** M**. The

**(**entry of

*i,j*)**is the probability of jumping from site**

*M***to site**

*i***. In our case only the following entries are different from zero:**

*j*Here ** p_0 = 1: **from the depth class

**0**(containing just the solved state) we can only jump to the depth class

**(there is no class**

*1***). Also,**

*-1***: from the depth class**

*q_*26*= 1***26**we can only jump to depth class

**25**(there is no class

**27**). For the same reason, there are no

**or**

*p_*26

*q_*0.## The stationary distribution

We mapped the action of randomly moving the cube to a one-dimensional depth-class random walker jumping back and forth with probabilities ** q_d** and

**. What happens after a long walk? or, how many times does the walker visit a particular site after a long walk? In real life: how often is a depth class visited when the cube undergoes random turns?**

*p_d*In the long run, and no matter what the starting point was, the time the walker spends in the depth class ** d** is proportional to the population

**of that depth class. This is the main point here:**

*D(d)**the (normalized) depth-population list **D(d)** should be interpreted as 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 will get the ** p_i’**s and

*q_i**’*s.

Taking into account that ** p_0 = q_26 = 1, **we can rewrite these as

These are known as ** detailed balance equations**: the flux, defined to be the stationary site population times the jumping probability, is the same in both 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 is something interesting about these solutions. Because ** q_i **is a probability we should have that

and that translate into the following condition for the distribution ** D_k**:

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

In particular, the last two inequalities are

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

Or:

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

We can see this as a detailed balance between even and odd sites: every move is always to a different and contiguous depth class. Any jump will take you from the odd depth class (the class of all the odd depth classes) to the even depth class (the class of all the even depth classes). So the odd to even class jump occur with probability 1 (and vise versa). Being the probabilities one in both direction, their population should be equal by detailed balance.

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

## A problem with the data

The depth-population ** D_d **reported in the source of the data that we are planning to use is approximate for

*d**= 19,20,21,22,23,24.*So there is no guarantee it will satisfy all these conditions (inequalities). Don’t be surprised if we get some probabilities

**out of the range [0,1] (as it is the case!). In particular, if we try and check the last condition (the even-odd population equality) it is off by a big number! (update: see note at the end)**

*q_i*## A way out

The odd class seem to be underpopulated (this is a consequence of the approximation the authors chose to report the data). To make things work (get probabilities in the range [0,1]), we decide to add the previous big number to the population of the depth class 21 (the odd class with the greatest population, or, the one that will notice that addition the least). With this correction, all the obtained probabilities seems to be correct (which means 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 almost all the first ** p_i** (up to

**) are close to**

*i = 21***1.**These are the probabilities of going away from the solved state. The probabilities of going closer to the solved state (

**) are almost**

*q_i***for**

*1***greater than**

*i***This puts in perspective why it is difficult to solve the cube: the random walker (or the cube’s random mover) will be “trapped forever” in a neighborhood of the depth class**

*21.***.**

*21*This post originally appeared on TechToday.