Quelle distribution tirez-vous de ce mélange aléatoire brisé?

Question

Le fameux shuffle de Fisher-Yates algorithme peut être utilisé pour permuter aléatoirement un tableau de longueur N:

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

Une erreur commune que j'ai été dit maintes et maintes fois de ne pas le faire est la suivante:

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

C'est, au lieu de reprendre un entier aléatoire de k à N, vous choisissez un nombre entier aléatoire de 1 à N.

Qu'advient-il si vous faites cette erreur? Je sais que la permutation n'est pas distribuée de manière uniforme, mais je ne sais pas quelles garanties il y a sur ce que la distribution sera. En particulier, quelqu'un aurait-il une expression pour les distributions de probabilité sur les positions finales des éléments?

Merci beaucoup!

Answer 1

Une Approche Empirique.

Nous allons mettre en œuvre l'erreur de l'algorithme dans 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];
]  

Maintenant obtenir le nombre de fois que chaque entier est dans chaque position:

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

Nous allons prendre trois positions dans les tableaux obtenus et le tracé de la distribution de fréquence pour chaque entier dans cette position:

Pour la position 1 à la fréquence de distribution:

Pour la position 5 (moyen)

Et pour la position 10 (le dernier):

et ici vous avez la distribution de tous les postes de tracés ensemble:

Ici vous avez plus de statistiques sur 8 positions:

Quelques observations:

• Pour tous les postes de la probabilité de "1" est le même (1/n).
• La probabilité de la matrice est symétrique à l'égard de la grande anti-diagonale
• Ainsi, la probabilité pour que tout nombre de la dernière la position est également uniforme (1/n)

Vous pouvez visualiser les propriétés de regarder le départ de toutes les lignes à partir du même point (première propriété) et la dernière ligne horizontale (troisième propriété).

La deuxième propriété peut être vu à partir de la matrice suivante représentation exemple, où les lignes sont les positions, les colonnes sont du nombre des occupants, et la couleur représente la probabilité expérimentale:

Pour un 100x100 matrice:

Modifier

Juste pour le fun, j'ai calculé la formule exacte pour la deuxième diagonale de l'élément (la première est de 1/n). Le reste peut être fait, mais c'est beaucoup de travail.

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

Les valeurs vérifiées à partir de n=3 à 6 ( {8/27, 57/256, 564/3125, 7105/46656} )

Modifier

Travailler un peu le grand calcul explicite dans @wnoise réponse, nous pouvons obtenir un peu plus d'infos.

Remplacement 1/n par p[n], donc les calculs sont maintenez non évaluée, on obtient par exemple pour la première partie de la matrice avec n=7 (cliquez pour voir une plus grande image):

Qui, après comparaison avec les résultats pour les autres valeurs de n, nous pouvons en identifier certains connus séquences d'entiers dans la matrice:

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

Vous pouvez trouver ces séquences (dans certains cas avec des signes différents) dans le merveilleux http://oeis.org/

Résoudre le problème général est plus difficile, mais j'espère que ce n'est qu'un début

Answer 2

Le "erreur" que vous mentionnez est traînant par hasard transpositions. Ce problème a été étudié en détail par Diaconis et Shahshahani dans la Génération d'une permutation aléatoire aléatoire transpositions (1981). Ils font une analyse complète des temps d'arrêt et de convergence à l'uniformité. Si vous ne pouvez pas obtenir un lien vers le papier, alors s'il vous plaît envoyez-moi un e-mail et je peux vous en envoyer une copie. C'est vraiment un plaisir de lire (comme le sont la plupart de Persi Diaconis papier).

Si le tableau a les entrées répétées, le problème est légèrement différent. Comme un plug sans vergogne, ce problème plus général est adressée par moi-même, Diaconis et Soundararajan à l'Annexe B de la Règle générale pour les Radiers de Brassage (2011).

Answer 3

Disons

• a = 1/N
• b = 1-a
• B_i(k) est la probabilité de la matrice après l' i pour les swaps kème élément. j'.e la réponse à la question "où est - k après i swaps?". Par exemple B₀(3) = (0 0 1 0 ... 0) et B₁(3) = (a 0 b 0 ... 0). Ce que vous voulez, c'est B_N(k) pour tout k.
• K_i est une matrice NxN avec 1s dans la i-ème colonne et de la i-ième ligne, des zéros partout ailleurs, l'e.g:

• I_i est la matrice identité, mais avec l'élément x=y=j'ai remis à zéro. E. g pour i=2:

• Un_je est

Ensuite,

Mais parce que B_N(k=1..N) est la matrice d'identité, la probabilité qu'un élément donné, je vais à la fin être en position j est donnée par la matrice de l'élément (i,j) de la matrice:

Par exemple, pour N=4:

Un diagramme pour N = 500 (niveaux de couleur sont 100*probabilité):

Le motif est le même pour tout N>2:

• Le plus probable fin de la position pour le k-ième élément est k-1.
• Le moins probable fin de la position est k pour k < N*ln(2), la position 1 sinon

Answer 4

Je savais que j'avais vu cette question avant...

"pourquoi est-ce simple algorithme de shuffle de produire des résultats biaisés? ce qui est une simple raison? "a beaucoup de bonnes choses dans les réponses, en particulier un lien vers un blog de Jeff Atwood sur le code de l'Horreur.

Comme vous l'avez déjà deviné, basé sur la réponse de @bélisaire, la répartition exacte est très dépendant du nombre d'éléments à être mélangées. Voici Atwood du complot pour 6 de l'élément de pont:

Answer 5

Quelle belle question! Je voudrais avoir une réponse complète.

De Fisher-Yates est agréable à analyser parce que une fois qu'il décide sur le premier élément, il le laisse tranquille. La désinformation, on peut à plusieurs reprises swap un élément dans et hors de n'importe quel endroit.

On peut analyser de la même façon nous ne serions qu'une chaîne de Markov, en décrivant les mesures stochastiques, matrices de transition agissant de façon linéaire sur des distributions de probabilité. La plupart des éléments sont laissés seuls, la diagonale est généralement de (n-1)/n. Sur pass k, quand ils n'obtiennent pas laissés seuls, ils obtenir échangé avec l'élément k, (ou d'un élément aléatoire si elles sont l'élément k). C'est 1/(n-1) dans la ligne ou la colonne k. L'élément de ligne et de colonne k est également en 1/(n-1). Il est assez facile de multiplier ces matrices ensemble pour k allant de 1 à n.

Nous savons que l'élément à la dernière place sera tout aussi susceptibles d'avoir été à l'origine de n'importe où parce que le dernier passage de swaps de la dernière place à égalité de chances avec les autres. De même, le premier élément sera tout aussi susceptibles d'être placés n'importe où. Cette symétrie est parce que la transposition inverse l'ordre de multiplication de matrice. En fait, la matrice est symétrique dans le sens de la ligne i est le même que la colonne (n+1 - i). Au-delà, les chiffres ne montrent pas beaucoup de motif apparent. Ces solutions exactes de ne montrer d'accord avec les simulations exécutées par bélisaire: Dans le logement i, La probabilité d'obtenir j diminue à mesure que j soulève à i, pour atteindre sa valeur la plus basse à i-1, et ensuite sauter jusqu'à sa valeur la plus élevée au i, et en diminuant jusqu'à ce que j atteigne n.

Dans Mathematica, j'ai généré à chaque pas

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

(Je n'ai pas trouvé documenté n'importe où, mais la première règle de correspondance est utilisée.) La finale de la matrice de transition peut être calculé avec:

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

ListDensityPlot est un utile outil de visualisation.

Edit (par bélisaire)

Juste une confirmation. Le code suivant donne la matrice de même que dans @Eelvex de réponse:

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}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm