Come a dimostrare la correttezza di un algoritmo di riordino?

Question

Ho due modi di produrre un elenco di elementi in ordine casuale e vorrei determinare se sono altrettanto fiera (distorta).

Il primo uso metodo che è quello di costruire l'intero elenco di elementi e poi fare uno shuffle su di esso (ad esempio uno shuffle Fisher-Yates). Il secondo metodo è più di un metodo iterativo che mantiene la lista mescolate ad ogni inserimento. In pseudo-codice la funzione di inserimento è:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

Mi interessa come uno va di mostrare l'equità di questa particolare rimescolamento. I vantaggi di questo algoritmo, dove viene utilizzato, sono sufficienti che, anche se un po 'ingiusto sarebbe a posto. Per decidere Ho bisogno di un modo per valutare la sua correttezza.

La mia prima idea è che ho bisogno di calcolare le permutazioni totale possibile in questo modo contro il totale permutazioni possibili per una serie di lunghezza finale. Sono un po 'in perdita però su come calcolare le permutazioni derivanti da questo algoritmo. Anche io non posso essere certo questo è il migliore, o più facile approccio.

Answer 1

In primo luogo, cerchiamo di fare due ipotesi forse ovvie, ma importanti:

1. _.random_item può scegliere l'ultima posizione.
2. _.random_item sceglie ogni posizione con probabilità $ \ frac {1} {n + 1} $.

Al fine di dimostrare la correttezza del vostro algoritmo, è necessario un argomento induttivo simile a quella usata qui :

• Per l'elenco Singleton c'è solo una possibilità, quindi viene scelto in modo uniforme.
• Supponendo che la lista con $ n $ elementi è stata uniformemente scelto (da tutte le permutazioni), dimostrano che quello con $ n + 1 $ elementi ottenuti con la vostra tecnica è scelto in modo uniforme.

---

^{Da qui in poi, la prova è sbagliato. Vedi sotto per una dimostrazione corretta; Lascio questo qui perché sia ??l'errore e le seguenti operazioni (che sono il suono) potrebbe essere educativo.}

È utile derivare una (ossia elemento-wise) immobili locale che deve tenere, perché discutendo tutta la permutazione è dolorosa. Si osservi che una permutazione viene uniformemente scelto se ogni elemento ha la stessa probabilità di essere in ogni posizione, cioè.

$ \ qquad \ displaystyle \ mathop {\ Forall} \ limiti _ {\ pi \ in \ mathrm {Perm} _n} \ operatorname {Pr} (L = \ pi) = \ frac {1} {n!} \ quad \ Longleftrightarrow \ quad \ mathop {\ forall} \ limits_ {i = 1} ^ n \ \ mathop {\ forall} \ limits_ {j = 1} ^ n \ operatorname {Pr} (L_i = j) = \ frac { 1} {n} \ qquad (1) $

dove $ n = | L |. $ E supponiamo per semplicità di notazione che inseriamo $ \ {1, \ dots, n \} $ nella lista

Ora, vediamo che cosa la vostra tecnica fa quando si inserisce il $ n + 1 $ st elemento. Dobbiamo considerare tre casi (dopo lo scambio):

1. Uno degli elementi della lista, non scambiati, vale a dire $ i \ in \ {1, \ dots, n \} $ e $ j \ in \ {1, \ dots, n \} $
2. Uno degli elementi della lista, scambiati, vale a dire $ i = n + 1 $ e $ j \ in \ {1, \ dots, n \} $
3. Il nuovo elemento, vale a dire $ i \ in \ {1, \ dots, n + 1 \} $ e $ j = n + 1 $

Per ogni caso, calcoliamo la probabilità di elemento $ j $ essere in posizione di $ i $; tutti devono rivelarsi $ \ frac {1} {n + 1} $ (il che è sufficiente a causa di $ (1) $). Sia $ p_n = \ frac {1} {n} $ è la probabilità che uno dei primi $ n $ elementi essendo in qualsiasi posizione nella vecchia lista (ipotesi di induzione), e $ P_S = \ frac {1} {n + 1} $ la probabilità di qualsiasi posizione di essere scelto da random_item (ipotesi 1, 2). Si noti che la scelta delle autorità doganali della lista con $ n $ elementi e raccogliendo la posizione di swap sono eventi indipendenti , così le probabilità di eventi fattore comune, ad esempio

$ \ qquad \ displaystyle \ operatorname {Pr} (L_i = j, i \ text {scambiati}) = \ operatorname {Pr} (L_i = j) \ cdot \ operatorname {Pr} (i \ text {scambiati} ) = p_np_s $

for $ i, j \ in \ {1, \ dots, n \} $. Ora per i calcoli.

1. Consideriamo solo il vecchio $ n elementi $. Tale elemento $ j $ è in posizione di $ i $ se e solo se c'era prima dell'ultimo inserimento e $ i $ non è selezionato come posizione di swap, che è

   $ \ quad \ displaystyle \ operatorname {Pr} (L_i = j) = p_n (1-P_S) = \ frac {1} {n} \ cdot \ frac {n} {n + 1} = \ frac { 1} {n + 1} $.

2. Qui consideriamo che uno dei vecchi elementi viene scambiato per l'ultima posizione. Elemento $ j $ avrebbe potuto essere in una qualsiasi delle vecchie posizioni, in modo che somma su tutte le probabilità che $ j $ è stato nella posizione $ i $ e $ i $ viene scelta come posizione di swap, che è

   $ \ quad \ displaystyle \ operatorname {Pr} (L_ {n + 1} = j) = \ sum_ {i = 1} ^ n p_np_s = \ sum_ {i = 1} ^ n \ frac {1} { n} \ cdot \ frac {1} {n + 1} = \ frac {1} {n + 1} $.

3. Il nuovo elemento finisce in posizione di $ i $ se e solo se $ i $ viene scelto come posizione di swap, che è

   $ \ quad \ displaystyle \ operatorname {} Pr (L_i = j) = P_S = \ frac {1} {n + 1} $.

Tutto si è rivelato bene, la vostra strategia di inserimento effettivamente pRiserva uniformità. Per il potere di induzione, che dimostra che il vostro algoritmo crea permutazioni uniformemente distribuiti.

^{Una parola di avvertimento: tale prova si rompe se gli elementi inseriti non sono a coppie resp diverso. distinguibili, perché poi la prima equazione non è più valida. Ma il vostro algoritmo è ancora valido; tutti permutazione con i duplicati è generata dallo stesso numero di esecuzioni casuali. È possibile a prova di questo contrassegnando i duplicati (vale a dire che li rende distinguibili), eseguire la prova di cui sopra e rimuovere le marcature (virtualmente); gli ultimi crolli passo uguali insiemi dimensioni di permutazioni alla stessa.}

---

Steven ha osservato correttamente nei commenti, sopra la prova è fondamentalmente errata da $ (1) $ non regge; è possibile costruire le distribuzioni sul set di permutazioni che soddisfano il destro, ma non il side¹ sinistra.

Pertanto, si dovrà lavorare con probabilità di permutazioni, che si rivela essere non così male, dopo tutto. Le ipotesi sulla random_item e la struttura induttiva delineata in fin dall'inizio del post rimangono sul posto, continuiamo da lì. Sia $ L ^ {(k)} $ indicare la lista dopo $ \ {1, \ dots, k \} $ sono stati inseriti.

Sia $ \ pi' \ in \ mathrm {} Perm _ {n + 1} $ una permutazione arbitraria di $ \ {1, \ dots, n + 1 \} $. Può essere scritto in modo univoco come

$ \ qquad \ displaystyle \ pi'= (\ pi (1), \ pi (2), \ dots, \ pi (i-1), n ??+ 1, \ pi (i + 1), \ dots , \ pi (n), \ pi (i)) $

per un po '$ \ pi \ in \ mathrm {} Perm _n $ e $ i \ in \ {1, \ dots, n + 1 \} $. Con l'ipotesi di induzione, $ \ operatorname {} Pr (L ^ {(n)} = \ pi) = \ frac {1} {n!} $. Inoltre, la posizione picconi random_item $ i $ con probabilità $ \ frac {1} {n + 1} $ per ipotesi. Come le scelte casuali di $ \ pi $ e $ i $ sono (stocasticamente) indipendenti, otteniamo

$ \ qquad \ displaystyle \ operatorname {Pr} (L ^ {(n + 1)} = \ pi ') = \ operatorname {Pr} (L ^ {(n)} = \ pi) \ cdot \ operatorname {} Pr (i \ text {} scambiati) = \ frac {1} {(n + 1)!} $

che abbiamo dovuto mostrare. Per il potere di induzione, che dimostra che il vostro algoritmo crea permutazioni uniformemente distribuiti.

---

1. Ad esempio, assegnare ogni permutazione in $ \ {(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3) \} $ probabilità $ \ frac {1} {4} $ e tutti gli altri $ 0 €. Ci sono anche esempi che assegnano ogni permutazione una probabilità diversa da zero.