Un processo markoviano sulle classi di profondità
Trovare p(d|N) immaginiamo le classi di profondità come siti di un processo markoviano. Lasciatemi spiegare:
Una lezione approfondita D è l’insieme di tutti gli stati del cubo in profondità D (numero minimo di mosse allo stato risolto). Se scegliessimo casualmente uno stato in una classe di profondità De giriamo una faccia a caso con una mossa casuale, che ci darà uno stato nella classe d+1, con una probabilità p_do uno stato nella classe d-1, con una probabilità q_d. Nella metrica del quarto di giro non ci sono mosse di autoclasse.
Ciò definisce un processo Markov, in cui un particolare sito costituisce un’intera classe di profondità. Nel nostro caso, solo contigui D le classi sono collegate con un salto. Per essere più precisi, questo è a catena di Markov nascita-morte a tempo discreto. Poiché la quantità di siti è finita, anche la catena è irriducibile (ergodica) ed esiste un’unica distribuzione stazionaria.
Assumiamo probabilità equamente distribuite per la selezione delle mosse casuali in ogni momento. Ciò induce alcune probabilità di transizione p_d, q_d (da calcolare) tra le classi di profondità. La quantità di mosse casuali N è il tempo discreto del processo di Markov. Anche questo è un camminatore casuale unidimensionale: in ogni sito (classe di profondità numero D)la probabilità di andare avanti è p_d, e la probabilità di tornare indietro è q_d. Questa catena unidimensionale è, grosso modo, la direzione “radiale” nel grafico di Rubik (organizzato nel layout profondità-radiale).
La matrice di transizione
Qualsiasi processo Markov è codificato in una matrice di transizione M. IL (io, j) ingresso di M è la probabilità di saltare dal sito io al sito J. Nel nostro caso solo le seguenti voci sono diverse da zero:
Qui P_0 = 1: dalla classe di profondità 0 (contenente solo lo stato risolto) possiamo solo passare alla classe di profondità 1 (non c’è lezione -1). Anche, Q_26 = 1: dalla classe di profondità 26 possiamo solo passare alla lezione approfondita 25 (non c’è lezione 27). Per lo stesso motivo non ce ne sono P_26 O Q_0.
La distribuzione stazionaria
Abbiamo mappato l’azione di spostare casualmente il cubo su un camminatore casuale unidimensionale di classe profondità che salta avanti e indietro con probabilità q_d E p_d. Cosa succede dopo una lunga camminata? oppure quante volte il camminatore visita un particolare sito dopo una lunga camminata? Nella vita reale: quanto spesso viene visitata una classe di profondità quando il cubo subisce giri casuali?
A lungo termine, e indipendentemente dal punto di partenza, il tempo che il camminatore trascorre nella classe di approfondimento D è proporzionale alla popolazione D(d) di quella classe di profondità. Questo è il punto principale qui:
l’elenco (normalizzato) della popolazione in profondità D(d) dovrebbe essere interpretato come il vettore che rappresenta la distribuzione stazionaria del nostro processo di Markov della classe di profondità.
Matematicamente, D(d) è un autovettore sinistro di M
Questa equazione di matrice ci darà 26 equazioni lineari, da cui otterremo le pi’sabbia q_i‘S.
Tenendo conto di ciò P_0 = q_26 = 1, possiamo riscriverli come
Questi sono conosciuti come equazioni di bilancio dettagliate: il flusso, definito come la popolazione del sito stazionario moltiplicata per la probabilità di salto, è lo stesso in entrambe le direzioni. Le soluzioni sono:
E pi si ottiene utilizzando p_i + q_i = 1.
Alcune condizioni sulla popolazione di una classe di profondità
C’è qualcosa di interessante in queste soluzioni. Perché q_i è una probabilità che dovremmo averlo
e che si traducono nella seguente condizione per la distribuzione D_k:
Questa è una torre di disuguaglianze che la popolazione in profondità D_k dovrebbe soddisfare. Esplicitamente possono essere organizzati come:
In particolare, le ultime due disuguaglianze sono
Perché D_27 = 0, otteniamo che il limite inferiore e superiore sono uguali, quindi
O:
La somma della popolazione dei siti pari dovrebbe essere uguale alla somma della popolazione dei siti dispari!
Possiamo vedere questo come un equilibrio dettagliato tra i siti pari e quelli dispari: ogni spostamento avviene sempre verso una classe di profondità diversa e contigua. Qualsiasi salto ti porterà dalla classe di profondità dispari (la classe di tutte le classi di profondità dispari) alla classe di profondità pari (la classe di tutte le classi di profondità pari). Quindi il salto di classe da dispari a pari avviene con probabilità 1 (e viceversa). Essendo le probabilità una in entrambe le direzioni, la loro popolazione dovrebbe essere uguale secondo il bilancio dettagliato.
Per lo stesso motivo il processo di Markov raggiungerà una “distribuzione stazionaria” del periodo due che passa dai siti pari a quelli dispari dopo ogni spostamento (tempo discreto N).
Un problema con i dati
La popolazione profonda D_d riportato nel fonte dei dati che prevediamo di utilizzare è approssimativo D = 19,20,21,22,23,24. Quindi non vi è alcuna garanzia che soddisfi tutte queste condizioni (disuguaglianze). Non sorprenderti se otteniamo alcune probabilità q_i fuori dall’intervallo (0,1) (come è il caso!). In particolare, se proviamo a verificare l’ultima condizione (l’uguaglianza della popolazione pari-dispari) il risultato è errato di un gran numero! (aggiornamento: vedi nota alla fine)
Una via d’uscita
Le classi dispari sembrano essere sottopopolate (questa è una conseguenza dell’approssimazione scelta per riportare i dati). Per far funzionare le cose (ottenere probabilità nell’intervallo (0,1)), decidiamo di aggiungere il grande numero precedente alla popolazione della classe di profondità 21 (la classe dispari con la popolazione più grande, ovvero quella che noterà che inoltre il minimo). Con questa correzione tutte le probabilità ottenute sembrano essere corrette (il che significa che anche le disuguaglianze sono soddisfatte).
Le probabilità di salto sono:
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
Si noti che quasi tutti i primi pi (fino a io = 21) sono vicini a 1. Queste sono le probabilità di allontanarsi dallo stato risolto. Le probabilità di avvicinarsi allo stato risolto (q_i) sono quasi 1 per io più grande di 21. Ciò mette in prospettiva il motivo per cui è difficile risolvere il cubo: il camminatore casuale (o il motore casuale del cubo) sarà “intrappolato per sempre” in un quartiere della classe di profondità 21.
Fonte: towardsdatascience.com
