Quelle dissortingbution obtenez-vous de ce mélange aléatoire cassé?

Le célèbre algorithme de shuffle de Fisher-Yates 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 fréquente qu’on m’a répété de ne pas 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-à-dire qu’au lieu de choisir un entier aléatoire de k à N, vous choisissez un entier aléatoire de 1 à N.

Que se passe-t-il si vous faites cette erreur? Je sais que la permutation qui en résulte n’est pas uniformément dissortingbuée, mais je ne sais pas quelles garanties il y a sur la dissortingbution qui en résultera. En particulier, est-ce que quelqu’un a une expression pour les dissortingbutions de probabilité sur les positions finales des éléments?

Une approche empirique

Implémentons l’algorithme erroné 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, obtenez le nombre de fois que chaque entier est dans chaque position:

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

Prenons trois positions dans les tableaux résultants et traçons la dissortingbution de fréquence pour chaque nombre entier dans cette position:

Pour la position 1, la dissortingbution de la fréquence est la suivante:

entrer la description de l'image ici

Pour la position 5 (au milieu)

entrer la description de l'image ici

Et pour la position 10 (dernier):

entrer la description de l'image ici

et ici vous avez la dissortingbution pour tous les postes tracés ensemble:

entrer la description de l'image ici

Ici, vous avez une meilleure statistique sur 8 positions:

entrer la description de l'image ici

Quelques observations:

  • Pour toutes les positions, la probabilité de "1" est la même (1 / n).
  • La masortingce de probabilité est symésortingque par rapport au grand anti-diagonal
  • Ainsi, la probabilité pour un nombre quelconque dans la dernière position est également uniforme (1 / n)

Vous pouvez visualiser ces propriétés en regardant le début de toutes les lignes 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 vue à partir de l'exemple de représentation masortingcielle suivant, où les lignes sont les positions, les colonnes sont le nombre d'occupants et la couleur représente la probabilité expérimentale:

entrer la description de l'image ici

Pour une masortingce 100x100:

entrer la description de l'image ici

modifier

Juste pour le plaisir, j'ai calculé la formule exacte pour le deuxième élément diagonal (le premier est 1 / n). Le rest peut être fait, mais c'est beaucoup de travail.

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

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

modifier

En travaillant un peu sur le calcul explicite général dans @wnoise answer, nous pouvons obtenir un peu plus d'informations.

En remplaçant 1 / n par p [n], donc les calculs sont maintenus non évalués, on obtient par exemple pour la première partie de la masortingce avec n = 7 (cliquez pour voir une image plus grande):

entrer la description de l'image ici

Après avoir comparé avec les résultats pour d'autres valeurs de n, identifions quelques séquences entières connues dans la masortingce:

 {{ 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 c'est un début

L’erreur commune que vous mentionnez est le mélange par transpositions aléatoires. Diaconis et Shahshahani ont étudié en détail ce problème dans Generating a random permutation with random transpositions (1981) . Ils effectuent une parsing complète des temps d’arrêt et de la convergence vers l’uniformité. Si vous ne pouvez pas obtenir de lien vers l’article, envoyez-moi un e-mail et je pourrai vous faire parvenir une copie. C’est en fait une lecture amusante (comme la plupart des articles de Persi Diaconis).

Si le tableau a des entrées répétées, le problème est légèrement différent. En tant que fiche sans vergogne, ce problème plus général est abordé par Diaconis et Soundararajan dans l’Annexe B de Règle de base pour Riffle Shuffling (2011) .

Disons

  • a = 1/N
  • b = 1-a
  • B i (k) est la masortingce de probabilité après avoir échangé pour le k e élément. c’est-à-dire la réponse à la question “où est k après avoir échangé?”. Par exemple B 0 (3) = (0 0 1 0 ... 0) et B 1 (3) = (a 0 b 0 ... 0) . Ce que vous voulez, c’est B N (k) pour chaque k.
  • K i est une masortingce NxN avec 1s dans la ieme colonne et la ieme ligne, zéros partout ailleurs, par exemple:

kappa_2

  • I i est la masortingce d’identité mais avec l’élément x = y = i mis à zéro. Par exemple pour i = 2:

I_2

  • Un je est

Ai = bii + aKi

Alors,

B_n

Mais parce que B N (k = 1.N) forme la masortingce d’identité, la probabilité qu’un élément donné soit à la position j est donnée par l’élément de masortingce (i, j) de la masortingce:

matrice de solution

Par exemple, pour N = 4:

B_4

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

B_500

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

  • La position finale la plus probable pour le k-ème élément est k-1 .
  • La position finale la moins probable est k pour k , position 1 sinon

Je savais que j’avais vu cette question avant …

” Pourquoi cet algorithme simple de mélange produit-il des résultats biaisés? Quelle est une raison simple? ” a beaucoup de bonnes choses dans les réponses, en particulier un lien vers un blog de Jeff Atwood sur Coding Horror .

Comme vous l’avez peut-être déjà deviné, sur la base de la réponse de @belisarius, la dissortingbution exacte dépend fortement du nombre d’éléments à mélanger. Voici l’insortinggue d’Atwood pour un jeu de 6 éléments:

entrer la description de l'image ici

Quelle belle question! J’aimerais avoir une réponse complète.

Fisher-Yates est agréable à parsingr, car une fois qu’il décide du premier élément, il rest seul. Le biais peut être remplacé à plusieurs resockets par un élément.

Nous pouvons parsingr cela de la même manière que nous le ferions avec une chaîne de Markov, en décrivant les actions comme des masortingces de transition stochastiques agissant linéairement sur les dissortingbutions de probabilité. La plupart des éléments restnt seuls, la diagonale est généralement (n-1) / n. Au passage k, quand ils ne sont pas laissés seuls, ils sont échangés avec l’élément k, (ou un élément aléatoire s’ils sont l’élément k). Ceci est 1 / (n-1) dans la ligne ou la colonne k. L’élément dans la ligne et la colonne k est également 1 / (n-1). Il est assez facile de multiplier ces masortingces ensemble pour k allant de 1 à n.

Nous soaps que l’élément de la dernière place sera tout aussi susceptible d’être à l’origine que la dernière passe échangera probablement la dernière place avec une autre. De même, le premier élément sera également susceptible d’être placé n’importe où. Cette symésortinge est due au fait que la transposition inverse l’ordre de la multiplication masortingcielle. En fait, la masortingce est symésortingque dans le sens où la ligne i est la même que la colonne (n + 1 – i). Au-delà, les chiffres ne montrent pas beaucoup de motif apparent. Ces solutions exactes concordent avec les simulations effectuées par Belisarius: Dans la case i, la probabilité d’obtenir j diminue à mesure que j augmente à i, atteignant sa valeur la plus faible à i-1, puis sautant à sa valeur maximale décroissant jusqu’à ce que j atteigne n.

Dans Mathematica, j’ai généré chaque étape avec

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

(Je ne l’ai trouvé nulle part documenté, mais la première règle de correspondance est utilisée.) La masortingce de transition finale peut être calculée avec:

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

ListDensityPlot est un outil de visualisation utile.

Edit (par Belisarius)

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

 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, IdentityMasortingx[n], Table[step[m, n], {m, s}]]; Last@Table[r[4, i], {i, 1, 4}] // MasortingxForm 

La page de Wikipedia sur le mélange Fisher-Yates contient une description et un exemple de ce qui se passera exactement dans ce cas.

Vous pouvez calculer la dissortingbution à l’aide de masortingces stochastiques . Soit la masortingce A (i, j) décrire la probabilité que la carte à l’origine à la position i se retrouve en position j. Alors la kth swap a une masortingce Ak donnée par Ak(i,j) = 1/N si i == k ou j == k , (la carte en position k peut finir n’importe où et n’importe quelle carte peut finir à la position k avec une probabilité égale), Ak(i,i) = (N - 1)/N pour tout i != k (toutes les autres cartes restront au même endroit avec la probabilité (N-1) / N) et tous les autres éléments zéro .

Le résultat du armsage complet est alors donné par le produit des masortingces AN ... A1 .

Je pense que vous recherchez une description algébrique des probabilités; vous pouvez en obtenir un en développant le produit masortingciel ci-dessus, mais j’imagine que ce sera assez complexe!

MISE À JOUR: J’ai juste repéré la réponse équivalente de wnoise ci-dessus! Oops…

J’ai approfondi cette question et il s’avère que cette dissortingbution a été longuement étudiée. La raison pour laquelle cela est intéressant est que cet algorithme “cassé” est (ou était) utilisé dans le système de puce RSA.

Dans Shuffling par transpositions semi-aléatoires , Elchanan Mossel, Yuval Peres et Alistair Sinclair étudient cette question et une classe plus générale de battements. Le résultat de cet article semble être que cela nécessite un mélange aléatoire de log(n) pour obtenir une dissortingbution presque aléatoire.

Dans Le biais de trois remaniements pseudo-aléatoires ( Aequationes Mathematicae , 22, 1981, 268-292), Ethan Bolker et David Robbins parsingnt ce mélange et déterminent que la distance totale de variation par rapport à l’uniformité après un seul passage est de 1, indiquant aléatoire du tout. Ils donnent également des parsings asympotiques.

Enfin, Laurent Saloff-Coste et Jessica Zuniga ont trouvé une belle limite supérieure dans leur étude des chaînes de Markov inhomogènes.

Cette question demande une parsing interactive du diagramme masortingciel visuel du mélange brisé mentionné. Un tel outil est sur la page Est-ce que ça brouille? – Pourquoi les comparateurs aléatoires sont mauvais par Mike Bostock.

Bostock a mis au point un excellent outil d’parsing des comparateurs aléatoires. Dans la liste déroulante de cette page, choisissez swap naïf (random ↦ random) pour voir l’algorithme cassé et le modèle qu’il produit.

Sa page est informative car elle permet de voir les effets immédiats d’un changement de logique sur les données mélangées. Par exemple:

Ce diagramme de masortingce utilisant un shuffle non uniforme et très biaisé est produit en utilisant un échange naïf (on choisit de “1 à N”) avec un code comme celui-ci:

 function shuffle(array) { var n = array.length, i = -1, j; while (++i < n) { j = Math.floor(Math.random() * n); t = array[j]; array[j] = array[i]; array[i] = t; } } 

mélange aléatoire

Mais si nous implémentons un mélange non biaisé, où nous sélectionnons de "k à N", nous devrions voir un diagramme comme celui-ci:

entrer la description de l'image ici

où la dissortingbution est uniforme et est produite à partir de code tel que:

 function FisherYatesDurstenfeldKnuthshuffle( array ) { var pickIndex, arrayPosition = array.length; while( --arrayPosition ) { pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) ); array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ]; } } 

Les excellentes réponses données jusqu’à présent se concentrent sur la dissortingbution, mais vous avez également demandé “Que se passe-t-il si vous faites cette erreur?” – qui est ce que je n’ai pas encore vu de réponse, alors je vais donner une explication à ce sujet:

L’algorithme de lecture aléatoire Knuth-Fisher-Yates sélectionne 1 des n éléments, puis 1 des 1 éléments restants, etc.

Vous pouvez l’implémenter avec deux tableaux a1 et a2 où vous supprimez un élément de a1 et l’insérez dans a2, mais l’algorithme le fait (ce qui signifie qu’il ne nécessite qu’un seul tableau), comme expliqué ici (Google: ” Mélanger les algorithmes Fisher-Yates DataGenetics “) très bien.

Si vous ne supprimez pas les éléments, ils peuvent être choisis de manière aléatoire, ce qui produit le caractère aléatoire biaisé. C’est exactement ce que fait le deuxième exemple que vous décrivez. Le premier exemple, l’algorithme Knuth-Fisher-Yates, utilise une variable de curseur allant de k à N, qui se souvient des éléments déjà pris, évitant ainsi de sélectionner des éléments plus d’une fois.