Come asintoticamente è grave rimescolamento ingenuo?

Question

E 'ben noto che questo algoritmo 'naive' per mischiare una matrice scambiando ogni elemento con un altro scelto casualmente non funziona correttamente:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

In particolare, dato che a ciascuna di $ n $ iterazioni, di $ n $ scelte è fatto (con probabilità uniforme), ci sono $ n ^ n $ possibili 'percorsi' attraverso il calcolo; perché il numero di possibili permutazioni $ n! $ non divide in modo uniforme il numero di percorsi $ n ^ n $, è impossibile per questo algoritmo per produrre ciascuna delle permutazioni $ n! $ con uguale probabilità. (Al contrario, si dovrebbe usare la cosiddetta Fischer-Yates Shuffle, che cambia in sostanza la chiamata a scegliere un numero casuale da [0..n) con una chiamata a scegliere un numero casuale da [ nel); che di discutibile alla mia domanda, però.)

Quello che mi chiedo è: come 'cattivo' possibile il riordino ingenuo essere? Più in particolare, lasciando $ P (n) $ l'insieme di tutte le permutazioni e $ C (\ rho) $ il numero di percorsi attraverso l'algoritmo ingenuo che producono il risultante permutazione $ \ rho \ in P (n) $, cosa è il comportamento asintotico delle funzioni

$ \ qquad \ displaystyle M (n) = \ frac {n!} {N ^ n} \ max _ {\ rho \ in P (n)} C (\ rho) $

e

$ \ qquad \ displaystyle m (n) = \ frac {n!} {N ^ n} \ min _ {\ rho \ in P (n)} C (\ rho) $?

Il fattore principale è quello di 'normalizzare' questi valori: se il riordino ingenuo è 'asintoticamente buono' poi

$ \ qquad \ displaystyle \ lim_ {n \ to \ infty} M (n) = \ lim_ {n \ to \ infty} m (n) = 1 $.

Ho il sospetto (sulla base di alcune simulazioni al computer che ho visto) che i valori attuali sono delimitate da 1, ma è anche noto se $ \ lim M (n) $ è finita, o se $ \ lim m ( n) $ è delimitato da 0? Ciò che è noto circa il comportamento di queste quantità?

Answer 1

Si mostrerà per induzione che la permutazione $ \ rho_n = (2,3,4, \ ldots, n, 1) $ è un esempio con $ C (\ rho_n) = 2 ^ {n-1} $. Se questo è il caso peggiore, in quanto è per i primi $ n $ (vedi le note per OEIS sequenza A192053 ), poi $ m (n) \ circa (2 / e) ^ {n} $. Così il min normalizzato, come la massima normalizzata, è 'in modo esponenziale cattivo'.

Il caso base è semplice. Per il passo di induzione, abbiamo bisogno di un lemma:

Lemma: in qualsiasi percorso da $ (2,3,4, \ ldots, n, 1) $ a $ (1,2,3, \ ldots, n) $, sia la primi swap mossa posizioni $ 1 $ e $ n $, o le posizioni ultima mossa swap $ 1 $ e $ n $.

Prova Sketch: non supporre. Consideriamo la prima mossa che coinvolge il $ n $ '° posizione. Si supponga che è il $ i $ 'th spostare, $ i \ neq 1 $ e $ i \ neq n $. Questa mossa deve posizionare l'elemento $ 1 $ in $ i $ '° posto. Consideriamo ora la prossima mossa che tocca l'articolo $ 1 $. Assumere questa mossa è il $ j $ 'th spostare. Questo scambio mossa must $ I $ e $ j $, spostando l'articolo $ 1 $ in $ j $ '° posto, con $ i

Ora, se i primi swap spostare le posizioni $ 1 $ e $ n $, le restanti mosse devono prendere la permutazione $ (1, 3,4,5, \ ldots, n, 2) $ a $ (1,2 , 3,4, \ ldots, n) $. Se le restanti mosse non toccare la prima posizione, allora questo è il permutazione $ \ rho_ {n-1} $ in posizioni $ 2 \ ldots n $, e sappiamo per induzione che ci sono $ C (\ rho_ {n- 1}) = 2 ^ {n-2} $ percorsi che fanno questo. Un argomento simile alla prova del Lemma dice che non v'è alcun percorso che tocca la prima posizione, in quanto l'articolo $ 1 $ deve poi finire nella posizione corretta.

Se gli swap ultima mossa posizioni $ 1 $ e $ n $, il primo $ n-1 $ si muove devono prendere la permutazione $ (2,3,4, \ ldots, n, 1) $ per la permutazione $ ( n, 2, 3,4, \ ldots, n-1, 1) $. Anche in questo caso, se queste mosse non toccano l'ultima posizione, allora questo è il permutazione $ \ rho_ {n-1} $, e per induzione ci sono $ C (\ rho_ {n-1}) = 2 ^ {n- 2} $ sentieri che lo fanno. E ancora, se uno dei primi $ n-1 $ si muove qui tocca l'ultima posizione, l'articolo $ 1 $ non può mai finire nel posto giusto.

Quindi, $ C (\ rho_n) = 2C (\ rho_ {n-1}) = 2 ^ {n-1} $.

Answer 2

Dopo un po 'di scavo intorno grazie al puntatore del mhum a OEIS, ho finalmente trovato un'eccellente analisi e bellissimo (relativamente) argomento elementare (a causa, per quanto posso dire, a Goldstein e Moews [1]) che $ M (n) $ cresce superexponentially veloce in $ n $:

Qualsiasi involuzione $ \ briciolo $ di $ \ {1 \ ldots n \} $ corrisponde ad un'esecuzione dell'algoritmo 'ingenuo' mischiare che produce la permutazione identità come il suo risultato, dal momento che l'algoritmo scambiare $ k $ con $ \ iota (k) $ e successivamente swap $ \ iota (k) $ con $ k $, lasciando entrambi invariati. Ciò significa che il numero di corse della algoritmo che cedere la permutazione identità è almeno il numero di involuzioni $ Q (n) $ (in realtà, un po 'di spettacoli di pensiero che la corrispondenza è 1-1 e quindi è esattamente $ Q ( n) $), e quindi il massimo in $ M (n) $ è delimitata da sotto di $ Q (n) $.

$ Q (n) $ va a quanto pare da una serie di nomi, tra cui numeri di telefono : vedi http: // oeis.org/A000085 e http://en.wikipedia.org/wiki/Telephone_number_%28mathematics% 29 . I asintotica sono ben noti, e si scopre che $ Q (n) \ circa C \ left (\ frac {n} {e} \ right) ^ {n / 2} e ^ \ sqrt {n} $; dalla relazione di ricorrenza $ Q (n) = Q (n-1) + (n-1) Q (n-2) $ si può induttivamente dimostrato che il rapporto $ R (n) = \ frac {Q (n) } {Q (n-1)} $ soddisfa $ \ sqrt {n} \ lt R (n) \ lt \ sqrt {n + 1} $ e da lì analisi di base ha l'importante $ n ^ {n / 2} $ termine nelle asintotica, anche se le altre condizioni richiede uno sforzo più attenta. Dal momento che il 'fattore di scala' $ \ frac {! N} {n ^ n} $ nella definizione di $ M (n) $ è solo circa $ C \ sqrt {n} e ^ {- n} $, il termine leader di $ Q (n) $ domina e dei rendimenti (asintoticamente) $ M (n) \ geq Cn ^ {(n + 1) / 2} e ^. {- 3n / 2 + \ sqrt {n}} $

Goldstein e Moews infatti andare a mostrare in [1] che la permutazione identità è il più probabile per grandi $ n $, in modo che il $ \ geq $ è infatti un $ \ circa $ e il comportamento di $ M (n) $ è completamente risolta. Questo lascia ancora la questione del comportamento di $ m (n) $ aperta; Non vorrei essere troppo sorpresi se che anche ceduto l'analisi nel loro articolo, ma non ho avuto modo di leggere da vicino ancora abbastanza per davvero ottenere una presa sui loro metodi, solo quanto basta per Grok il risultato di base.

[1] Goldstein, D. e Moews, D .: "L'identità è la più casuale scambio probabile per n grande", http://arxiv.org/abs/math/0010066