pourquoi ce simple algorithme de mélange produit-il des résultats biaisés? ce qui est une simple raison?
il semble que cet algorithme simple de mélange produira des résultats biaisés:
# suppose $arr is filled with 1 to 52
for ($i < 0; $i < 52; $i++) {
$j = rand(0, 51);
# swap the items
$tmp = $arr[j];
$arr[j] = $arr[i];
$arr[i] = $tmp;
}
vous pouvez essayer... au lieu d'utiliser 52, utilisez 3 (supposons que seulement 3 cartes soient utilisées), et lancez-le 10 000 fois et additionnez les résultats, vous verrez que les résultats sont biaisés vers certains modèles...
la question Est... ce qui est une simple explication qu'il va se passer?
la bonne solution est d'utiliser quelque chose comme
for ($i < 0; $i < 51; $i++) { # last card need not swap
$j = rand($i, 51); # don't touch the cards that already "settled"
# swap the items
$tmp = $arr[j];
$arr[j] = $arr[i];
$arr[i] = $tmp;
}
mais la question Est... pourquoi la première méthode, apparemment aussi totalement aléatoire, rendra les résultats biaisés?
mise à Jour 1: merci pour les gens ici, en précisant qu'elle doit être rand($i, 51) mélanger correctement.
12 réponses
Voici l'arbre de probabilité complet pour ces remplacements.
supposons que vous commenciez par la séquence 123, puis nous énumérerons toutes les différentes façons de produire des résultats aléatoires avec le code en question.
123
+- 123 - swap 1 and 1 (these are positions,
| +- 213 - swap 2 and 1 not numbers)
| | +- 312 - swap 3 and 1
| | +- 231 - swap 3 and 2
| | +- 213 - swap 3 and 3
| +- 123 - swap 2 and 2
| | +- 321 - swap 3 and 1
| | +- 132 - swap 3 and 2
| | +- 123 - swap 3 and 3
| +- 132 - swap 2 and 3
| +- 231 - swap 3 and 1
| +- 123 - swap 3 and 2
| +- 132 - swap 3 and 3
+- 213 - swap 1 and 2
| +- 123 - swap 2 and 1
| | +- 321 - swap 3 and 1
| | +- 132 - swap 3 and 2
| | +- 123 - swap 3 and 3
| +- 213 - swap 2 and 2
| | +- 312 - swap 3 and 1
| | +- 231 - swap 3 and 2
| | +- 213 - swap 3 and 3
| +- 231 - swap 2 and 3
| +- 132 - swap 3 and 1
| +- 213 - swap 3 and 2
| +- 231 - swap 3 and 3
+- 321 - swap 1 and 3
+- 231 - swap 2 and 1
| +- 132 - swap 3 and 1
| +- 213 - swap 3 and 2
| +- 231 - swap 3 and 3
+- 321 - swap 2 and 2
| +- 123 - swap 3 and 1
| +- 312 - swap 3 and 2
| +- 321 - swap 3 and 3
+- 312 - swap 2 and 3
+- 213 - swap 3 and 1
+- 321 - swap 3 and 2
+- 312 - swap 3 and 3
Maintenant, la quatrième colonne de nombres, celle d'avant l'échange d'information, contient le résultat final, avec 27 résultats possibles.
comptons combien de fois chaque motif se produit:
123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
27 times total
si vous exécutez le code qui change au hasard pour un nombre infini de fois, les patterns 132, 213 et 231 se produiront plus souvent que les patterns 123, 312, et 321, simplement parce que la façon dont les swaps de code rendent cela plus susceptible de se produire.
maintenant, bien sûr, vous pouvez dire que si vous exécutez le code 30 fois (27 + 3), vous pourriez finir par tous les modèles se produisant 5 fois, mais en traitant des statistiques vous devez regarder le long terme tendance.
voici le code C # qui explore le caractère aléatoire pour un de chaque motif possible:
class Program
{
static void Main(string[] args)
{
Dictionary<String, Int32> occurances = new Dictionary<String, Int32>
{
{ "123", 0 },
{ "132", 0 },
{ "213", 0 },
{ "231", 0 },
{ "312", 0 },
{ "321", 0 }
};
Char[] digits = new[] { '1', '2', '3' };
Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2)
{
Char[] result = new Char[] { input[0], input[1], input[2] };
Char temp = result[pos1];
result[pos1] = result[pos2];
result[pos2] = temp;
return result;
};
for (Int32 index1 = 0; index1 < 3; index1++)
{
Char[] level1 = swap(digits, 0, index1);
for (Int32 index2 = 0; index2 < 3; index2++)
{
Char[] level2 = swap(level1, 1, index2);
for (Int32 index3 = 0; index3 < 3; index3++)
{
Char[] level3 = swap(level2, 2, index3);
String output = new String(level3);
occurances[output]++;
}
}
}
foreach (var kvp in occurances)
{
Console.Out.WriteLine(kvp.Key + ": " + kvp.Value);
}
}
}
Ce sorties:
123: 4
132: 5
213: 5
231: 5
312: 4
321: 4
donc, bien que cette réponse compte en fait, ce n'est pas une réponse purement mathématique, vous avez juste à évaluer toutes les façons possibles la fonction aléatoire peut aller, et regarder les résultats finaux.
Voir ce:
Le Danger de la Naïveté (Code de l'Horreur)
regardons votre jeu de cartes comme un exemple. En utilisant un deck 3 cartes, il n'y a que 6 commandes possibles pour le deck après un shuffle: 123, 132, 213, 231, 312, 321.
avec votre 1er algorithme il y a 27 chemins possibles (résultats) pour le code, en fonction des résultats de la fonction rand() à différents points. Chacun de ces résultats sont tout aussi probable (impartial). Chacun de ces résultats correspondra au même résultat de la liste des six résultats "réels" possibles ci-dessus. Nous avons maintenant 27 articles et 6 seaux pour les mettre. Étant donné que 27 n'est pas divisible également par 6, certaines de ces 6 combinaisons doivent être sur-représentées.
avec le 2ème algorithme, il y a 6 résultats possibles qui correspondent exactement aux 6 résultats "réels" possibles de mélange, et ils devraient tous être représentés également au cours du temps.
C'est important parce que les seaux qui sont sur-représentés dans le premier algorithme ne sont pas aléatoires. Les seaux choisis pour le biais sont reproductibles et prévisible. donc si vous êtes en train de construire un jeu de poker en ligne et d'utiliser le 1er algorithme, un hacker pourrait comprendre que vous avez utilisé le type naïf et de ce travail que certains arrangements de deck sont beaucoup plus susceptibles de se produire que d'autres. Alors ils peuvent placer des paris conséquent. Ils en perdront un peu, mais ils gagneront beaucoup plus qu'ils ne perdront et vous mettrez rapidement en faillite.
de vos commentaires sur les autres réponses, il semble que vous cherchez non seulement une explication de la raison pour laquelle la distribution n'est pas la distribution uniforme (pour laquelle la réponse de divisibilité est simple), mais aussi une explication "intuitive" de la raison pour laquelle elle est en fait loin d'être uniforme .
Voici une façon de le regarder. Supposons que vous commencez avec le tableau initial [1, 2, ..., n] (où n pourrait être 3, ou 52, ou peu importe) et appliquer l'un des deux algorithmes. Si toutes les permutations sont uniformément probables, alors la probabilité que 1 reste dans la première position devrait être 1/n . Et en effet, dans le deuxième algorithme (correct), il est 1/n , car 1 reste à sa place si et seulement si il n'est pas échangé la première fois, i.e. iff l'appel initial à rand(0,n-1) renvoie 0.
Cependant, dans le premier algorithme (erroné), 1 reste intact seulement si elle est ni échangé la première fois ni n'importe quel autre temps - c.-à-d., seulement si le premier rand retourne 0 et aucun de l'autre rand s retourne 0, la probabilité de laquelle est (1/N) * (1-1/n)^(n-1) ≈ 1/(ne) ≈ 0,37/n, pas 1/n.
et c'est l'explication" intuitive": dans votre premier algorithme, Les articles plus anciens sont beaucoup plus susceptibles d'être déplacés que les articles plus récents, donc les permutations que vous obtenez sont orientés vers des modèles dans lesquels les premiers éléments sont pas dans leurs lieux d'origine.
(c'est un peu plus subtil que cela, par exemple, 1 peut être échangé dans une position ultérieure et finir toujours par être échangé de nouveau dans la place par une série compliquée de swaps, mais ces probabilités sont relativement moins importantes.)
la meilleure explication que J'ai vu pour cet effet était de Jeff Atwood sur son Codinghorro blog ( le Danger de Naïveté ).
utilisant ce code pour simuler un mélange aléatoire de trois cartes...
for (int i = 0; i < cards.Length; i++)
{
int n = rand.Next(cards.Length);
Swap(ref cards[i], ref cards[n]);
}
...vous avez cette distribution.
le code shuffle (ci-dessus) donne 3^3 (27) combinaisons possibles de pont. Mais les mathématiques nous disent qu'il n'y a que 3! ou 6 combinaisons possibles d'un deck 3 cartes. Certaines combinaisons sont donc sur-représentées.
vous devez utiliser un Fisher-Yates shuffle pour bien (au hasard) mélanger un jeu de cartes.
voici une autre intuition: le simple shuffle swap ne peut pas créer la symétrie dans la probabilité d'occuper une position à moins qu'au moins la symétrie bidirectionnelle existe déjà. Appeler les trois positions de A, B, et C. Maintenant laisser la probabilité de carte 2 en position A, b, la probabilité de carte 2 en position B, et c, la probabilité d'être en position C, avant un échange de la déplacer. Supposons que deux probabilités sont les mêmes: un!=b, b!=c, c!=un. Maintenant calculer les probabilités a', b' et c' de la carte se trouvant dans ces trois positions à la suite d'un échange. Disons que ce swap consiste en un échange de position C avec une des trois positions au hasard. Puis:
a' = a*2/3 + c*1/3
b' = b*2/3 + c*1/3
c' = 1/3.
C'est-à-dire, la probabilité que la carte se termine en position A est la probabilité qu'elle était déjà là fois les 2/3 de la position de temps A n'est pas impliqué dans l'échange, plus la probabilité qu'il était en position C fois la 1/3 de probabilité que C échangé avec un, etc. Maintenant, en soustrayant les deux premières équations, nous obtenons:
a' - b' = (a - b)*2/3
ce qui signifie que parce que nous avons supposé un!= b, puis a'!=b' (bien que la différence se rapprochera de 0 au fil du temps, étant donné le nombre suffisant de swaps). Mais depuis un'+b'+c'=1, si un"!=b', alors ni l'un ni l'autre ne peut être égal à c' non plus, qui est 1/3. Donc, si les trois probabilités commencent toutes différentes avant un échange, elles seront toutes différentes après un échange. Et cela serait valable quelle que soit la position qui a été échangée - nous avons juste échange les rôles des variables ci-dessus.
maintenant le tout premier swap a commencé par échanger la carte 1 en position A avec l'une des autres. Dans ce cas, il y avait symétrie bidirectionnelle avant l'échange, parce que la probabilité de la carte 1 EN position B = Probabilité de la carte 1 en position C = 0. Donc, en fait, la carte 1 peut finir avec des probabilités symétriques et il se retrouve dans chacune des trois positions avec une probabilité égale. Cela reste vrai pour tous les swaps. Mais la carte 2 se retrouve dans les trois positions après le premier échange avec Probabilité (1/3, 2/3, 0), et de même la carte 3 se retrouve dans les trois positions avec Probabilité (1/3, 0, 2/3). Donc, peu importe le nombre de swaps subséquents que nous faisons, nous ne nous retrouverons jamais avec la carte 2 ou 3 ayant exactement la même probabilité d'occuper les trois positions.
Voir le Codage d'Horreur post Le Danger de la Naïveté .
(suposing 3 cartes):
Le naïf shuffle résultats dans 33 (27) combinaisons possibles de pont. C'est bizarre, parce que les mathématiques nous disent qu'il n'y a que 3! ou de 6 combinaisons possibles d'une carte 3 pont. Dans le KFY shuffle, nous commençons avec une commande initiale, swap à partir de la troisième position avec l'une des trois cartes, puis échanger à nouveau à partir de la deuxième position avec les deux cartes restantes.
la réponse simple est qu'il y a 52^52 façons possibles de faire fonctionner cet algorithme, mais il n'y en a que 52! arrangements possibles de 52 cartes. Pour l'algorithme pour être juste, il doit produire chacun de ces dispositions tout aussi probable. 52^52 n'est pas un multiple entier de 52!. Par conséquent, certaines dispositions doivent être plus que d'autres.
une approche illustrative pourrait être celle-ci:
1) considérer seulement 3 cartes.
2) pour que l'algorithme donne des résultats uniformément répartis, la chance de "1" se terminant par un[0] doit être 1/3, et la chance de "2" se terminant par un[1] doit être 1/3 aussi, et ainsi de suite.
3) donc si nous regardons le deuxième algorithme:
probabilité que "1" se termine à un[0]: lorsque 0 est le nombre aléatoire générer, donc 1 cas sur (0,1,2), donc, est 1 sur 3 = 1/3
probabilité que" 2 " se retrouve à un[1]: quand il n'a pas été échangé à un [0] le première fois, et cela n'a pas échangé [2] la seconde fois: 2/3 * 1/2 = 1/3
probabilité "3" aboutit à une[2]: quand il n'a pas été échangé à un [0] le première fois, et cela n'a pas échangé [1] la seconde fois: 2/3 * 1/2 = 1/3
ils sont tous parfaitement 1/3, et nous ne vois pas d'erreur ici.
4) si nous essayons de calculer la probabilité de "1" se terminant par un[0] dans le premier algorithme, le calcul sera un peu long, mais comme le montre l'illustration dans la réponse de lassevk, il est de 9/27 = 1/3, mais "2" se terminant par un[1] a une chance de 8/27, et "3" se terminant par un[2] a une chance de 9/27 = 1/3.
en conséquence, "2" se terminant par un[1] n'est pas 1/3 et donc le algorithme produit joli résultat faussé (environ 3,7% d'erreur, contrairement à toute négligeable de cas comme 3/10000000000000 = 0.00000000003%)
5) La preuve que Joel Coehoorn a, peut en fait prouver que certains cas seront surreprésentés. Je pense que l'explication pourquoi il est n^n est ceci: à chaque itération, il y a n possibilité que le nombre aléatoire peut être, après n itérations, il peut être n^n cas = 27. Ce nombre ne divise pas le nombre de permutations (n! = 3! = 6) également dans le cas de n = 3, de sorte que certains résultats sont surreprésentés. ils sont sur-représentés d'une manière qui au lieu de se présenter 4 fois, il apparaît 5 fois, donc si vous mélangez les cartes des millions de fois de l'ordre initial de 1 à 52, le cas sur-représenté apparaîtra 5 millions de fois par rapport à 4 millions de fois, ce qui est assez grande une différence.
6) je pense que la surreprésentation est montrée, mais "pourquoi" la surreprésentation se produira-t-elle?
7) un test ultime pour que l'algorithme soit correct est que n'importe quel nombre a une probabilité 1/n pour finir à n'importe quelle fente.
Voici une grande analyse d'une carte mélangeant chaînes Markov . Oh attends, c'est que des maths. Désolé. :)
L'algorithme naïf choisit les valeurs de n comme ceci:
n = rand (3)
n = rand (3)
n = rand (3)
3^3 combinaisons possibles de n
1,1,1, 1,1,2....3,3,2 3,3,3 (27 Combinaisons) la réponse de lassevk montre la distribution parmi les cartes de ces combinaisons.
le meilleur algorithme n':
n = rand (3)
n = rand (2)
n! combinaisons possibles de n
1,1, 1,2, 2,1 2,2 3,1 3,2 (6 combinaisons, toutes donnant un résultat différent)
comme mentionné dans les autres réponses, si vous prenez 27 tentatives pour obtenir 6 résultats, vous ne pouvez pas atteindre les 6 résultats avec une distribution égale, puisque 27 n'est pas divisible par 6. Mettez 27 marbres dans 6 seaux et peu importe ce que vous faites, certains seaux auront plus de marbres que d'autres, le mieux que vous pouvez faire est 4,4,4,5,5,5 marbres pour les seaux 1 à 6.
le problème fondamental avec le shuffle naïf est que swaps trop de fois, pour mélanger 3 cartes complètement, vous n'avez besoin que de faire 2 swaps, et le second swap ne doit être parmi les deux premières cartes, puisque la Troisième Carte avait déjà un tiers de chance d'être échangé. continuer à échanger des cartes donnera plus de chances qu'une carte donnée sera échangée, et ces chances seront seulement égaliser à 1/3, 1/3, 1/3 si votre total de combinaisons de swap est divisible par 6.
non pas qu'une autre réponse soit nécessaire, mais j'ai trouvé qu'il valait la peine d'essayer de comprendre exactement pourquoi Fisher-Yates est "1519200920 uniforme".
Si nous parlons d'un pont avec N éléments, alors cette question est: comment pouvons-nous montrer que
Pr(Item i ends up in slot j) = 1/N?
décomposant avec des probabilités conditionnelles, Pr(item i ends up at slot j) est égal à
Pr(item i ends up at slot j | item i was not chosen in the first j-1 draws)
* Pr(item i was not chosen in the first j-1 draws).
et de là il se dilate récursivement de nouveau à la première dessiner.
maintenant, la probabilité que l'élément i n'ait pas été tiré sur le premier tirage est N-1 / N . Et la probabilité qu'il n'ait pas été tiré sur le deuxième tirage conditionnée par le fait qu'il n'a pas été tiré sur le premier tirage est N-2 / N-1 et ainsi de suite.
donc, nous obtenons pour la probabilité que l'élément i n'a pas été tiré dans le premier j-1 tire:
(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)
et bien sûr, nous savons que la probabilité qu'il est tiré au rond j conditionnel à ne pas avoir été tiré plus tôt est juste 1 / N-j .
Avis que, dans le premier terme, les numérateurs tout annuler la subséquente dénominateurs (c'est à dire N-1 annule N-2 annule, le N-j+1 annule, en laissant un peu N-j / N ).
donc la probabilité globale de l'élément i apparaissant dans la fente j est:
[(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)] * (1 / N-j)
= 1/N
comme prévu.
pour obtenir plus général sur le" simple shuffle", la propriété particulière qu'il manque est appelé échangeability . En raison de la "dépendance du chemin" de la façon dont le mélange est créé (c.-à-d. lequel des 27 chemins est suivi pour créer la sortie), vous n'êtes pas en mesure de traiter les différentes variables aléatoires composant-sage comme si elles pouvaient apparaître dans n'importe quel ordre. En fait, c'est peut-être le exemple motivant pour pourquoi l'échangeabilité des questions aléatoires d'échantillonnage.
la réponse la plus claire pour montrer le premier algorithme échoue est de voir l'algorithme en question comme une chaîne de Markov de n étapes sur le graphe de n! les sommets de toutes les permutations de n nombres naturels. L'algorithme saute d'un sommet à l'autre avec une probabilité de transition. Le premier algorithme donne la probabilité de transition de 1/n pour chaque saut. Il y a n^n chemins dont la probabilité de chacun est 1/n^n . Supposons que la probabilité finale d'atterrissage sur chaque sommet est 1/n! qui est une fraction réduite. Pour réaliser cela , il doit y avoir des chemins m avec le même vertex final tel que m/n^n=1/n! ou n^n = mn! pour un nombre naturel quelconque m , ou que n^n est divisible par n! . Mais c'est impossible. Dans le cas contraire, n doit être divisible par n-1 , ce qui n'est possible que lorsque n=2 . Nous sommes en contradiction.