Comment est asymptotiquement mauvais naïf brassage?

Question

Il est bien connu que cet algorithme « naïf » pour brouiller un tableau en échangeant chaque élément avec un autre hasard choisi ne fonctionne pas correctement:

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

Plus précisément, puisque, il y a $ n ^ n $ possibles « chemins » par le calcul à chacun des $ n itérations $, l'un des choix $ n $ est faite (avec une probabilité uniforme); parce que le nombre de permutations possibles $ n! $ ne divise pas uniformément dans le nombre de chemins $ n ^ n $, il est impossible pour cet algorithme pour produire chacun des $ n! $ permutations avec une probabilité égale. (Au lieu de cela, il faut utiliser la soi-disant Fischer-Yates Lecture aléatoire qui change essentiellement l'appel à choisir un nombre aléatoire de [0..n) avec un appel à choisir un nombre aléatoire de [ dans); que de moot à ma question, cependant.)

Ce que je me demande, comment le shuffle naïf peut « mauvais » être? Plus précisément, laissant $ P (n) $ l'ensemble de toutes les permutations et $ C (\ rho) $ le nombre de chemins à travers l'algorithme naïf qui produit la permutation résultante $ \ rho \ P (n) $, ce est le comportement asymptotique des fonctions

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

et

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

Le facteur principal est de « normaliser » ces valeurs: si le shuffle est naïf « asymptotiquement bon » alors

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

Je soupçonne (basé sur des simulations informatiques que j'ai vu) que les valeurs réelles sont enfuyaient de 1, mais est encore connu si $ \ lim M (n) $ est fini, ou si $ \ lim m ( n) $ est limitée loin de 0? Ce qui est connu sur le comportement de ces quantités?

Answer 1

Nous montrerons par induction que la permutation $ \ rho_n = (2,3,4, \ ldots, n, 1) $ est un exemple avec $ C (\ rho_n) = 2 ^ {n-1} $. Si tel est le pire des cas, comme pour les quelques premiers $ n $ (voir les notes pour séquence OEIS A192053 ), puis $ m (n) \ environ (2 / e) ^ {n} $. Ainsi, le min normalisé, comme le max normalisé, est « exponentielle mauvais ».

Le cas de base est facile. Pour l'étape d'induction, nous avons besoin d'un lemme:

Lemme: En tout chemin allant de $ (2,3,4, \ ldots, n, 1) $ à $ (1,2,3, \ ldots, n) $, soit la d'abord déplacer les positions swaps $ 1 $ et $ n $, ou le dernier mouvement des swaps positions $ 1 $ et $ n $.

Preuve Sketch: Supposons pas. Considérons le premier mouvement qui implique la n $ $ 'ième position. On suppose qu'il est le i $ $ 'e mouvement, $ i \ NEQ $ 1 et $ i \ n NEQ $. Ce mouvement doit placer l'élément 1 $ en $ i $ 'e place. Considérons maintenant le prochain mouvement qui touche l'élément 1 $. Supposons que ce mouvement est la j $ $ 'e mouvement. Ce swap déplacer doit i $ $ et $ j $, déplaçant l'élément 1 $ dans le $ j $ 'e place, avec $ i

Maintenant, si le premier mouvement swaps les positions 1 et $ $ $ n $, les mouvements restants doivent prendre l'$ de permutation (1, 3,4,5, \ ldots, n, 2) $ à $ (1,2 , 3,4, \ ldots, n) $. Si les mouvements restants ne touchent pas la première position, alors c'est la permutation $ \ rho_ {n-1} $ en positions 2 $ \ ldots n $, et nous savons par induction qu'il ya $ C (\ rho_ {n 1}) = 2 ^ {n-2} $ chemins qui font. Un argument similaire à la preuve du lemme dit qu'il n'y a pas de chemin qui touche la première position, comme l'élément 1 $ doit alors se retrouver dans la position incorrecte.

Si le dernier mouvement des swaps les positions $ 1 $ et $ n $, la première $ n-1 se déplace $ doit prendre les $ de permutation (2,3,4, \ ldots, n, 1) $ à la $ de permutation ( n, 2, 3,4, \ ldots, n-1, 1) $. Encore une fois, si ces mouvements ne touchent pas la dernière position, alors c'est la permutation $ \ {rho_ n-1} $, et par induction il y a $ C (\ rho_ {n-1}) = 2 ^ {n 2} $ chemins qui le font. Et encore, si l'un des premiers $ n-1 $ se déplace ici touche la dernière position, l'élément 1 $ ne peut jamais se retrouver dans le bon endroit.

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

Answer 2

Après quelques recherches autour grâce au pointeur de mhum à OEIS, je l'ai enfin trouvé une excellente analyse et une belle (relativement) l'argument élémentaire (du fait, pour autant que je peux dire, Goldstein et Moews [1]) que $ M (n) $ croît superexponentially rapidement en $ n $:

Tous involution $ \ iota $ de $ \ {1 \ ldots n \} $ correspond à une exécution de l'algorithme brassage « naïf » qui produit la permutation d'identité comme résultat, puisque l'algorithme échangera k $ $ avec $ \ iota (k) $, puis $ permutez \ iota (k) $ avec $ k $, laissant les deux inchangés. Cela signifie que le nombre de pistes de l'algorithme qui donnent la permutation d'identité est au moins le nombre de involutions $ Q (n) $ (en fait, un peu montre de penser que la correspondance est 1-1 et il est donc exactement $ Q ( n) $), et ainsi le maximum de $ M (n) $ est délimitée par le bas par $ Q (n) $.

Q $ (n) $ va apparemment par un certain nombre de noms, y compris les numéros de téléphone : voir http: // oeis.org/A000085 et http://en.wikipedia.org/wiki/Telephone_number_%28mathematics% 29 . Les asymptotiques sont bien connus, et il se avère que $ Q (n) \ C environ \ left (\ frac {n} {e} \ right) ^ {n / 2} e ^ \ sqrt {n} $; à partir de la relation de récurrence $ Q (n) = Q (n-1) + (n-1) Q (n-2) $ il peut être démontré par induction que le rapport $ R (n) = \ frac {Q (n) } {Q (n-1)} $ satisfait $ \ sqrt {n} \ lt R (n) \ ll \ sqrt {n + 1} $ et de là, l'analyse de base reçoit le premier n $ ^ {n / 2} $ terme dans les asymptote, bien que les autres termes exigent un effort plus prudent. Étant donné que le 'facteur d'échelle' $ \ frac {! N} {n ^ n} $ dans la définition de M $ (n) $ est seulement $ C \ sqrt {n} e ^ {- n} $, le premier terme de $ Q (n) $ domine et les rendements (asymptotiquement) M $ (n) \ geq Cn ^ {(n + 1) / 2} e ^. {- 3n / 2 + \ sqrt {n}} $

Goldstein et Moews à aller de fait à afficher dans [1] que la permutation d'identité est la plus probable pour grande $ n $, de sorte que le est en fait $ $ \ geq un $ \ environ $ et le comportement de M $ (n) $ est entièrement réglé. Cela laisse encore la question du comportement de $ m (n) $ ouverte; Je ne serais pas trop surpris si cela aussi cédé à l'analyse dans leur papier, mais je ne l'ai pas eu l'occasion de le lire de près encore assez pour vraiment avoir une emprise sur leurs méthodes, juste assez pour assimilez le résultat de base.

[1] Goldstein, D. et Moews, D .: "L'identité est le plus aléatoire d'échange probable pour un grand n", http://arxiv.org/abs/math/0010066