Un proceso de Markov sobre clases de profundidad.
Encontrar pag(d|norte) Imaginamos las clases de profundidad como sitios de un proceso de Markov. Dejame explicar:
Una clase de profundidad d es el conjunto de todos los estados del cubo en una profundidad d (número mínimo de movimientos al estado resuelto). Si elegimos aleatoriamente un estado en una clase de profundidad dy giramos una cara aleatoria con un movimiento aleatorio, que nos dará un estado en la clase d + 1 , con una probabilidad p_do un estado en la clase d-1, con una probabilidad q_d. En la métrica de un cuarto de turno no hay movimientos de autoclase.
Eso define un proceso de Markov, donde un sitio en particular es una clase de profundidad completa. En nuestro caso, sólo contiguos d Las clases están conectadas en un solo salto. Para ser más precisos, este es un cadena de Markov de nacimiento-muerte en tiempo discreto. Debido a que la cantidad de sitios es finita, la cadena también es irreducible (ergódica) y existe una distribución estacionaria única.
Asumimos probabilidades igualmente distribuidas para la selección de movimientos aleatorios en cada momento. Eso induce algunas probabilidades de transición. p_d, q_d (a calcular) entre las clases de profundidad. La cantidad de movimientos aleatorios. norte es el tiempo discreto del proceso de Markov. Este también es un caminante aleatorio unidimensional: en cada sitio (número de clase de profundidad d)la probabilidad de seguir adelante es p_d, y la probabilidad de retroceder es q_d. Esta cadena unidimensional es, en términos generales, la dirección “radial” en el gráfico de Rubik (organizada en el diseño radial de profundidad).
La matriz de transición
Cualquier proceso de Markov está codificado en una matriz de transición. METRO. El (yo, j) entrada de METRO es la probabilidad de saltar del sitio i al sitio j. En nuestro caso sólo las siguientes entradas son distintas de cero:
Aquí pag_0 = 1: de la clase de profundidad 0 (que contiene solo el estado resuelto) solo podemos saltar a la clase de profundidad 1 (no hay clase -1). También, q_26 = 1: de la clase de profundidad 26 solo podemos saltar a la clase de profundidad 25 (no hay clase 27). Por la misma razón, no existen pag_26 o q_0.
La distribución estacionaria
Mapeamos la acción de mover aleatoriamente el cubo a un caminante aleatorio unidimensional de clase de profundidad que salta hacia adelante y hacia atrás con probabilidades. q_d y p_d. ¿Qué pasa después de una larga caminata? o ¿cuántas veces visita el caminante un sitio en particular después de una larga caminata? En la vida real: ¿con qué frecuencia se visita una clase de profundidad cuando el cubo realiza giros aleatorios?
A la larga, y sin importar cuál haya sido el punto de partida, el tiempo que el caminante pasa en la clase de profundidad d es proporcional la poblacion D(d) de esa clase de profundidad. Este es el punto principal aquí:
la lista de población en profundidad (normalizada) D(d) debe interpretarse como el vector que representa la distribución estacionaria de nuestro proceso de Markov de clase de profundidad.
Matemáticamente, D(d) es un vector propio izquierdo de METRO
Esta ecuación matricial nos dará 26 ecuaciones lineales, de las cuales obtendremos la Pi’arena q_i‘s.
Teniendo en cuenta que pag_0 =q_26 = 1, podemos reescribirlos como
Estos se conocen como ecuaciones de equilibrio detalladas: el flujo, definido como la población del sitio estacionario multiplicada por la probabilidad de salto, es el mismo en ambas direcciones. Las soluciones son:
y Pi se obtiene usando p_i + q_i = 1.
Algunas condiciones sobre la población de una clase de profundidad.
Hay algo interesante en estas soluciones. Porque q_i es una probabilidad que deberíamos tener eso
y que se traducen en la siguiente condición para la distribución D_k:
Esta es una torre de desigualdades que la población profunda D_k debe cumplir. Explícitamente, se pueden organizar como:
En particular, las dos últimas desigualdades son
Porque D_27 = 0, Obtenemos que el límite superior e inferior son iguales, por lo que
O:
¡La suma de la población de los sitios pares debe ser igual a la suma de la población de los sitios impares!
Podemos ver esto como un equilibrio detallado entre sitios pares e impares: cada movimiento es siempre a una clase de profundidad diferente y contigua. Cualquier salto lo llevará de la clase de profundidad impar (la clase de todas las clases de profundidad impar) a la clase de profundidad par (la clase de todas las clases de profundidad pares). Entonces, el salto de clase impar a par ocurre con probabilidad 1 (y viceversa). Siendo las probabilidades una en ambas direcciones, su población debería ser igual según el equilibrio detallado.
Por la misma razón, el proceso de Markov alcanzará una “distribución estacionaria” del período dos que cambia entre sitios pares e impares después de cada movimiento (tiempo discreto). norte).
Un problema con los datos.
La población profunda D_d reportado en el fuente de los datos que planeamos utilizar son aproximados para d = 19,20,21,22,23,24. Por tanto, no hay garantía de que satisfaga todas estas condiciones (desigualdades). No se sorprenda si obtenemos algunas probabilidades. q_i fuera del rango [0,1] (¡como es el caso!). En particular, si intentamos verificar la última condición (la igualdad de la población par-impar), ¡está equivocada por un gran número! (actualización: ver nota al final)
Una salida
Las clases impares parecen estar subpobladas (esto es una consecuencia de la aproximación elegida para informar los datos). Para que las cosas funcionen (obtener probabilidades en el rango [0,1]), decidimos agregar el número grande anterior a la población de la clase de profundidad 21 (la clase impar con mayor población, o la que notará menos esa adición). Con esta corrección, todas las probabilidades obtenidas parecen ser correctas (lo que significa que las desigualdades también se satisfacen).
Las probabilidades de salto son:
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
Observe que casi todos los primeros Pi (hasta yo = 21) están cerca de 1. Estas son las probabilidades de salir del estado resuelto. Las probabilidades de acercarse al estado resuelto (q_i) están casi 1 para i mas grande que 21. Esto pone en perspectiva por qué es difícil resolver el cubo: el caminante aleatorio (o el motor aleatorio del cubo) quedará “atrapado para siempre” en una vecindad de la clase de profundidad. 21.