Quelle est la gravité asymptotique du brassage naïf?

33

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

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

Plus précisément, puisque à chacune des nn itérations, l’une desnn choix est fait (avec une probabilité uniforme), il y a n nnn chemins possibles dans le calcul; parce que le nombre de permutations possibles n ! n!ne divise pas uniformément le nombre de chemins n nnn , il est impossible pour cet algorithme de produire chacun des n ! n!permutations avec probabilité égale. (Au lieu de cela, on devrait utiliser le soi-disant shuffle de Fischer-Yates , qui change essentiellement l'appel pour choisir un nombre aléatoire de [0..n) avec un appel pour choisir un numéro aléatoire de [i..n); c'est sans objet pour ma question, cependant.)

Ce que je me demande, c'est à quel point le remaniement naïf peut être «mauvais»? Plus précisément, si P ( n )P(n) est l'ensemble de toutes les permutations et C ( ρ )C(ρ) le nombre de chemins de l'algorithme naïf qui produisent la permutation résultante ρ P ( n )ρP(n) , quel est le comportement asymptotique des fonctions

M(n)=n!nnmaxρP(n)C(ρ)M(n)=n!nnmaxρP(n)C(ρ)

et

m(n)=n!nnminρP(n)C(ρ)m(n)=n!nnminρP(n)C(ρ) ?

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

limnM(n)=limnm(n)=1limnM(n)=limnm(n)=1 .

Je soupçonne (d'après certaines simulations informatiques que j'ai vues) que les valeurs réelles sont délimitées par 1, mais sait-on même si est fini ou si est délimité 0? Que sait-on du comportement de ces quantités?limM(n)limM(n)limm(n)limm(n)

Steven Stadnicki
la source
8
Bonne question. Je ne sais pas où est le meilleur endroit pour cette question. Sauf s’il est clair qu’un autre forum est meilleur pour cela, je pense que vous devriez le laisser ici pendant une semaine environ, et si vous n’obtenez pas de réponse satisfaisante, posez-la sur l’un des autres forums (et mettez des liens dans les deux questions). )
Peter Shor
4
@vzn "Pourquoi effectuer une analyse complète sur un algorithme défectueux connu?" Parce que les mathématiques sont intéressantes et que vous ne savez jamais où d'autres applications pourraient surgir - voir l'analyse de Knuth sur Bubble Sort, par exemple. Les graphiques d'Atwood donnent une analyse qualitative approximative de l'inhomogénéité, mais c'est loin d'une analyse mathématiquement quantitative. (Et il y a différentes formulations équivalentes du shuffle Fischer-Yates - celle que je mentionne fonctionne très bien.)
Steven Stadnicki
4
Pour mémoire, la séquence OEIS A192053 correspond à C max ( ρ ) et ne répertorie pas un formulaire fermé. De plus, les notes de cette entrée suggèrent que min C ( ρ ) peut être 2 n - 1 , ce qui implique que m ( n ) 0 . C(ρ)C(ρ)2n1m(n)0
Mhum
2
@vzn Quel est le problème avec les questions ouvertes?
Yuval Filmus
1
@vzn Pas d'accord sur votre dernière phrase, il y a beaucoup d'analyses sur les remaniements "imparfaits". Pour des exemples, si nous faisons transpositions au hasard, on sait que le seuil est à peu près aléatoire ( 1 / 2 ) n log n . La question actuelle peut être difficile, mais il est a priori difficile de dire si c'est "très difficile". Une réponse comme celle de mhum est déjà très satisfaisante, montrant que la question était appropriée pour le forum et ne présentait pas une barrière insurmontable (preuves formelles mises de côté). (1/2)nlogn
Yuval Filmus

Réponses:

13

Nous montrerons par induction que la permutation ρ n = ( 2 , 3 , 4 , , n , 1 ) est un exemple avec C ( ρ n ) = 2 n - 1 . Si tel est le pire des cas, comme pour les quelques premiers n (voir les notes de séquence OEIS A192053 ), puis m ( n ) ( 2 / e ) nρn=(2,3,4,,n,1)C(ρn)=2n1nm(n)(2/e)n. Ainsi, le minimum normalisé, comme le maximum normalisé, est «exponentiellement mauvais».

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

Lemme: quelle que soit la trajectoire de ( 2 , 3 , 4 , , n , 1 ) à ( 1 , 2 , 3 , , n ) , le premier mouvement remplace les positions 1 et n , ou le dernier mouvement les positions 1 et n .(2,3,4,,n,1)(1,2,3,,n)1n1n

Croquis de preuve: Supposons que non. Considérez le premier mouvement qui implique la n ième position. Supposons que c’est le i ème mouvement, i 1 et i n . Ce mouvement doit placer l'élément 1 à la i ème place. Considérons maintenant le prochain mouvement qui touche l’article 1 . Supposons que ce mouvement est le j « e mouvement. Ce mouvement doit permuter i et j , déplaçant l'élément 1 à la j 'ème place, avec i < j . Un argument similaire dit que le point 1nii1in1i1jij1ji<j1ne peut ensuite être déplacé vers la droite. Mais le point 1 doit finir en premier lieu, une contradiction. 1

À présent, si le premier coup échange les positions 1 et n , les coups restants doivent prendre la permutation ( 1 , 3 , 4 , 5 , , n , 2 ) à ( 1 , 2 , 3 , 4 , , n ) . Si les mouvements restants ne touchent pas la première position, il s'agit de la permutation ρ n - 1 en positions 2 n , et nous savons par induction qu'il y a1n(1,3,4,5,,n,2)(1,2,3,4,,n)ρn12nC ( ρ n - 1 ) = 2 n - 2 chemins qui le font. Un argument similaire à la preuve du lemme dit qu'il n'y a pas de chemin qui touche la première position, car l'élément 1 doit alors se retrouver dans une position incorrecte.C(ρn1)=2n21

Si le dernier coup intervertit les positions 1 et n , les n - 1 premiers coups doivent porter la permutation ( 2 , 3 , 4 , , n , 1 ) à la permutation ( n , 2 , 3 , 4 , , n - 1 , 1 ) . Encore une fois, si ces mouvements ne touchent pas la dernière position, il s’agit de la permutation ρ n - 1 et, par induction,1nn1(2,3,4,,n,1)(n,2,3,4,,n1,1)ρn1C ( ρ n - 1 ) = 2 n - 2 chemins qui le font. Et encore une fois, si l’un des n - 1 premiersmouvements touche ici la dernière position, l’article 1 ne peut jamais se retrouver au bon endroit.C(ρn1)=2n2n11

Ainsi, C ( ρ n ) = 2 C ( ρ n - 1 ) = 2 n - 1 .C(ρn)=2C(ρn1)=2n1

Peter Shor
la source
Perfect - the argument behind the lemma looks a lot like the one I had for involutions being the only way of getting the identity permutation, but I'd missed the recursive structure in the explicit swap. Thank you!
Steven Stadnicki
10

After some digging around thanks to mhum's pointer to OEIS, I've finally found an excellent analysis and a nice (relatively) elementary argument (due, as far as I can tell, to Goldstein and Moews [1]) that M(n)M(n) grows superexponentially fast in nn:

Toute involution ι de { 1 n } correspond à une exécution de l'algorithme de réarrangement «naïf» qui produit la permutation d'identité comme résultat, car l'algorithme échangera k avec ι ( k ) , puis échangera ι ( k ) avec k , laissant les deux inchangés. Cela signifie que le nombre d'exécutions de l'algorithme donnant la permutation d'identité est au moins égal au nombre d'involutions Q ( n ) (en fait, un peu de réflexion montre que la correspondance est égale à 1-1 et qu'il s'agit donc exactement de Q ( nι{1n}kι(k)ι(k)kQ(n)) ), et donc le maximum dans M ( n ) est borné par le bas par Q ( n ) .Q(n)M(n)Q(n)

Q ( n ) porte apparemment plusieurs noms, dont lesnuméros de téléphone: voirhttp://oeis.org/A000085ethttp://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29. Les asymptotiques sont bien connus, et il se révèle que Q ( n ) C ( nQ(n)e )n/2enQ(n)C(ne)n/2en; from the recurrence relation Q(n)=Q(n1)+(n1)Q(n2)Q(n)=Q(n1)+(n1)Q(n2) it can be inductively shown that the ratio R(n)=Q(n)Q(n1)R(n)=Q(n)Q(n1) satisfies n<R(n)<n+1n<R(n)<n+1 and from there basic analysis gets the leading nn/2nn/2 term in the asymptotics, though the other terms require a more careful effort. Since the 'scale factor' n!nnn!nn in the definition of M(n)M(n) is only about CnenCnen, the leading term of Q(n)Q(n) dominates and yields (asymptotically) M(n)Cn(n+1)/2e3n/2+nM(n)Cn(n+1)/2e3n/2+n.

Goldstein and Moews in fact go on to show in [1] that the identity permutation is the most likely for large nn, so the is in fact a and the behavior of M(n)M(n) is fully settled. This still leaves the question of the behavior of m(n)m(n) open; I wouldn't be too surprised if that also yielded to the analysis in their paper, but I haven't had opportunity to read it closely enough yet to really get a grip on their methods, only enough to grok the basic result.

[1] Goldstein, D. and Moews, D.: "The identity is the most likely exchange shuffle for large n", http://arxiv.org/abs/math/0010066

Steven Stadnicki
la source
1
It's not too hard to show that the permutation (2,3,4,,n,1) is an example with C(ρ)=2n1. If this is the worst case, as it is for the first few n, then m(n)(2/e)n.
Peter Shor
@PeterShor Can you give the basic argument? I feel like I'm missing some simple version of the involutions argument that would work, but I'm not quite getting it. I think even if that's not quite minimal that would be good enough; the minimum count seems unlikely to be subexponential in n and just knowing that the normalized max and min are both 'exponentially bad' is a pretty satisfactory answer.
Steven Stadnicki
I added an answer with the argument ... it's too long for a comment.
Peter Shor