Che distribuzione ottieni da questo casuale mescolamento casuale?

Il famoso algoritmo shuffle Fisher-Yates può essere usato per permutare casualmente un array A di lunghezza N:

For k = 1 to N Pick a random integer j from k to N Swap A[k] and A[j] 

Un errore comune che mi è stato ripetutamente detto di non fare è questo:

 For k = 1 to N Pick a random integer j from 1 to N Swap A[k] and A[j] 

Cioè, invece di scegliere un numero intero casuale da k a N, scegli un numero intero casuale da 1 a N.

Cosa succede se commetti questo errore? So che la permutazione risultante non è uniformsmente distribuita, ma non so quali garanzie ci sono su quale sarà la distribuzione risultante. In particolare, qualcuno ha un’espressione per le distribuzioni di probabilità sulle posizioni finali degli elementi?

Un approccio empirico.

Implementiamo l’algoritmo errato in Mathematica:

 p = 10; (* Range *) s = {} For[l = 1, l <= 30000, l++, (*Iterations*) a = Range[p]; For[k = 1, k <= p, k++, i = RandomInteger[{1, p}]; temp = a[[k]]; a[[k]] = a[[i]]; a[[i]] = temp ]; AppendTo[s, a]; ] 

Ora ottieni il numero di volte in cui ogni numero intero è in ogni posizione:

 r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s] 

Prendiamo tre posizioni negli array risultanti e tracciamo la distribuzione di frequenza per ogni intero in quella posizione:

Per la posizione 1 la distribuzione di freq è:

inserisci la descrizione dell'immagine qui

Per la posizione 5 (centro)

inserisci la descrizione dell'immagine qui

E per la posizione 10 (ultima):

inserisci la descrizione dell'immagine qui

e qui hai la distribuzione per tutte le posizioni tracciate insieme:

inserisci la descrizione dell'immagine qui

Qui hai una statistica migliore su 8 posizioni:

inserisci la descrizione dell'immagine qui

Alcune osservazioni:

  • Per tutte le posizioni la probabilità di "1" è la stessa (1 / n).
  • La matrice di probabilità è simmetrica rispetto al grande anti-diagonale
  • Quindi, anche la probabilità per qualsiasi numero nell'ultima posizione è uniforms (1 / n)

È ansible visualizzare tali proprietà guardando l'inizio di tutte le linee dallo stesso punto (prima proprietà) e l'ultima linea orizzontale (terza proprietà).

La seconda proprietà può essere vista dal seguente esempio di rappresentazione di matrice, dove le righe sono le posizioni, le colonne sono il numero di occupante e il colore rappresenta la probabilità sperimentale:

inserisci la descrizione dell'immagine qui

Per una matrice 100x100:

inserisci la descrizione dell'immagine qui

modificare

Solo per divertimento, ho calcolato la formula esatta per il secondo elemento diagonale (il primo è 1 / n). Il resto può essere fatto, ma è molto lavoro.

 h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n) 

Valori verificati da n = 3 a 6 ({8/27, 57/256, 564/3125, 7105/46656})

modificare

Elaborando un po 'il calcolo generale esplicito nella risposta @wnoise, possiamo ottenere maggiori informazioni.

Sostituendo 1 / n con p [n], quindi i calcoli sono mantenuti non valutati, otteniamo ad esempio per la prima parte della matrice con n = 7 (clicca per vedere un'immagine più grande):

inserisci la descrizione dell'immagine qui

Che, dopo aver confrontato i risultati con altri valori di n, identifichiamo alcune sequenze di interi noti nella matrice:

 {{ 1/n, 1/n , ...}, {... .., A007318, ....}, {... .., ... ..., ..}, ... ...., {A129687, ... ... ... ... ... ... ..}, {A131084, A028326 ... ... ... ... ..}, {A028326, A131084 , A129687 ... ....}} 

Puoi trovare quelle sequenze (in alcuni casi con segni diversi) nella meravigliosa http://oeis.org/

Risolvere il problema generale è più difficile, ma spero che questo sia un inizio

L ‘”errore comune” che menzioni è mescolare con trasposizioni casuali. Questo problema è stato studiato in dettaglio da Diaconis e Shahshahani nella generazione di una permutazione casuale con trasposizioni casuali (1981) . Eseguono un’analisi completa dei tempi di arresto e della convergenza all’uniformità. Se non riesci a ottenere un link alla carta, ti prego di inviarmi una e-mail e posso inviarti una copia. In realtà è una lettura divertente (come la maggior parte delle carte di Persi Diaconis).

Se la matrice ha voci ripetute, il problema è leggermente diverso. Come una spina spudorata, questo problema più generale è affrontato da me stesso, Diaconis e Soundararajan nell’Appendice B di A Regola del pollice per Riffle Shuffling (2011) .

Diciamo

  • a = 1/N
  • b = 1-a
  • B i (k) è la matrice di probabilità dopo aver scambiato per l’elemento k th. cioè la risposta alla domanda “dov’è k dopo i scambio?”. Ad esempio B 0 (3) = (0 0 1 0 ... 0) e B 1 (3) = (a 0 b 0 ... 0) . Quello che vuoi è B N (k) per ogni k.
  • K i è una matrice NxN con 1s nella i-esima colonna e i-esima riga, zeri ovunque, ad esempio:

kappa_2

  • I i è la matrice id quadro ma con l’elemento x = y = i azzerato. Ad esempio per i = 2:

I_2

  • A è

Ai = bIi + aKi

Poi,

b_n

Ma poiché B N (k = 1..N) forma la matrice di identity framework, la probabilità che ogni dato elemento i alla fine sia nella posizione j è data dall’elemento di matrice (i, j) della matrice:

matrice della soluzione

Ad esempio, per N = 4:

B_4

Come diagramma per N = 500 (i livelli di colore sono 100 * probabilità):

B_500

Il modello è lo stesso per tutti N> 2:

  • La posizione finale più probabile per l’elemento k-esimo è k-1 .
  • La posizione finale più probabile è k per k , altrimenti la posizione 1

Sapevo di aver visto questa domanda prima …

” perché questo semplice algoritmo di shuffle produce risultati distorti? qual è una semplice ragione? ” ha un sacco di cose buone nelle risposte, in particolare un link a un blog di Jeff Atwood su Coding Horror .

Come avrete già intuito, sulla base della risposta di @belisarius, la distribuzione esatta dipende in larga misura dal numero di elementi da mescolare. Ecco la trama di Atwood per un mazzo di 6 elementi:

inserisci la descrizione dell'immagine qui

Che bella domanda! Vorrei avere una risposta completa.

Fisher-Yates è bello da analizzare perché una volta che decide sul primo elemento, lo lascia da solo. Lo sbilenco può scambiare ripetutamente un elemento dentro e fuori da qualsiasi posto.

Possiamo analizzarlo allo stesso modo in cui avremmo una catena di Markov, descrivendo le azioni come matrici di transizione stocastiche che agiscono linearmente sulle distribuzioni di probabilità. La maggior parte degli elementi rimane solo, la diagonale è di solito (n-1) / n. Al passaggio k, quando non vengono lasciati da soli, vengono scambiati con l’elemento k, (o un elemento casuale se si tratta dell’elemento k). Questo è 1 / (n-1) in una riga o colonna k. L’elemento sia in riga che in colonna k è anche 1 / (n-1). È abbastanza facile moltiplicare queste matrici insieme per andare da 1 a n.

Sappiamo che l’elemento nell’ultimo posto sarà ugualmente probabile che sia stato originariamente ovunque perché l’ultimo passaggio scambia l’ultimo posto con altrettanta probabilità con qualsiasi altro. Allo stesso modo, il primo elemento sarà ugualmente probabilmente posizionato ovunque. Questa simmetria è dovuta al fatto che la trasposizione inverte l’ordine di moltiplicazione della matrice. In effetti, la matrice è simmetrica nel senso che la riga i è uguale alla colonna (n + 1 – i). Oltre a ciò, i numeri non mostrano uno schema molto apparente. Queste soluzioni esatte mostrano un accordo con le simulazioni eseguite da belisarius: nello slot i, la probabilità di ottenere j diminuisce all’aumentare di j, raggiungendo il suo valore più basso in i-1, e quindi salendo al suo valore più alto in i, e diminuendo fino a quando giunge al n.

In Mathematica ho generato ogni passo con

  step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]] 

(Non l’ho trovato documentato da nessuna parte, ma viene utilizzata la prima regola di corrispondenza.) La matrice di transizione finale può essere calcasting con:

 Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]] 

ListDensityPlot è uno strumento di visualizzazione utile.

Modifica (di belisarius)

Solo una conferma Il seguente codice fornisce la stessa matrice della risposta di @ Eelvex:

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]]; r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]; [email protected][r[4, i], {i, 1, 4}] // MatrixForm 

La pagina di Wikipedia sullo shuffle Fisher-Yates ha una descrizione e un esempio di cosa esattamente accadrà in quel caso.

È ansible calcolare la distribuzione utilizzando matrici stocastiche . Lascia che la matrice A (i, j) descriva la probabilità della carta originariamente in posizione I finendo in posizione j. Quindi il kth swap ha una matrice Ak data da Ak(i,j) = 1/N se i == k o j == k , (la carta in posizione k può finire ovunque e qualsiasi carta può finire in posizione k con uguale probabilità), Ak(i,i) = (N - 1)/N per tutti i != k (ogni altra carta rimarrà nello stesso posto con probabilità (N-1) / N) e tutti gli altri elementi zero .

Il risultato dello shuffle completo viene quindi dato dal prodotto delle matrici AN ... A1 .

Mi aspetto che tu stia cercando una descrizione algebrica delle probabilità; puoi ottenerne uno espandendo il prodotto matrix sopra, ma immagino che sarà abbastanza complesso!

AGGIORNAMENTO: ho appena visto la risposta equivalente di Wnoise sopra! oops …

Ho esaminato ulteriormente, e si scopre che questa distribuzione è stata studiata a lungo. Il motivo per cui è interessante è perché questo algoritmo “rotto” è (o era) utilizzato nel sistema di chip RSA.

In Shuffling con trasposizioni semi-casuali , Elchanan Mossel, Yuval Peres e Alistair Sinclair studiano questa e una class più generale di mescolanze. Il risultato di quel documento sembra essere che ci vuole log(n) shuffles rotti per ottenere una distribuzione quasi casuale.

In The bias of three pseudorandom shuffles ( Aequationes Mathematicae , 22, 1981, 268-292), Ethan Bolker e David Robbins analizzano questo shuffle e determinano che la variazione totale della distanza dall’uniformità dopo un singolo passaggio è 1, indicando che non è molto casuale a tutti. Danno anche analisi asimmetriche.

Alla fine, Laurent Saloff-Coste e Jessica Zuniga trovarono un bel limite superiore nel loro studio di catene di Markov disomogenee.

Questa domanda è l’accattonaggio per un’analisi intertriggers del diagramma a matrice visiva dello shuffle rotto menzionato. Tale strumento è nella pagina Will It Shuffle? – Perché i comparatori casuali sono cattivi da Mike Bostock.

Bostock ha messo insieme uno strumento eccellente che analizza i comparatori casuali. Nel menu a discesa in quella pagina, scegli naïve swap (casuale ↦ casuale) per vedere l’algoritmo rotto e il modello che produce.

La sua pagina è informativa in quanto consente di vedere gli effetti immediati che un cambiamento nella logica ha sui dati mescolati. Per esempio:

Questo diagramma a matrice che usa uno shuffle non uniforms e molto distorto viene prodotto usando uno swap naïve (selezioniamo da “1 a N”) con un codice come questo:

 function shuffle(array) { var n = array.length, i = -1, j; while (++i < n) { j = Math.floor(Math.random() * n); t = array[j]; array[j] = array[i]; array[i] = t; } } 

mescolanza parziale

Ma se implementiamo un shuffle non distorto, dove selezioniamo da "k a N" dovremmo vedere un diagramma come questo:

inserisci la descrizione dell'immagine qui

dove la distribuzione è uniforms e viene prodotta da codice come:

 function FisherYatesDurstenfeldKnuthshuffle( array ) { var pickIndex, arrayPosition = array.length; while( --arrayPosition ) { pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) ); array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ]; } } 

Le eccellenti risposte fornite finora si stanno concentrando sulla distribuzione, ma hai chiesto anche “Cosa succede se commetti questo errore?” – che è ciò che non ho ancora visto, quindi darò una spiegazione al riguardo:

L’algoritmo shuth di Knuth-Fisher-Yates seleziona 1 di n elementi, quindi 1 di n-1 elementi rimanenti e così via.

Puoi implementarlo con due matrici a1 e a2 in cui rimuovi un elemento da a1 e lo inserisci in a2, ma l’algoritmo lo fa in posizione (il che significa che ha bisogno di un solo array), come spiegato qui (Google: ” Shuffling Algorithms Fisher-Yates DataGenetics “) molto bene.

Se non rimuovi gli elementi, possono essere scelti a caso in modo casuale che produce la casualità distorta. Questo è esattamente ciò che fa il secondo esempio che stai descrivendo. Il primo esempio, l’algoritmo Knuth-Fisher-Yates, utilizza una variabile del cursore che va da k a N, che ricorda quali elementi sono già stati presi, evitando così di selezionare gli elementi più di una volta.