Il s'agit d'une suite à une question de Stackoverflow sur le mélange aléatoire d'un tableau .
Il existe des algorithmes établis (tels que le shuffle de Knuth-Fisher-Yates ) que l'on devrait utiliser pour mélanger un tableau, plutôt que de s'appuyer sur des implémentations ad hoc "naïves".
Je veux maintenant prouver (ou réfuter) que mon algorithme naïf est cassé (comme dans: ne génère pas toutes les permutations possibles avec une probabilité égale).
Voici l'algorithme:
Faites une boucle plusieurs fois (la longueur du tableau devrait suffire), et à chaque itération, obtenez deux index de tableau aléatoires et échangez-y les deux éléments.
De toute évidence, cela nécessite plus de nombres aléatoires que KFY (deux fois plus), mais à part cela, cela fonctionne-t-il correctement? Et quel serait le nombre d'itérations approprié (la "longueur du tableau" est-elle suffisante)?
la source
Réponses:
Il est cassé, bien que si vous effectuez suffisamment de mélanges, cela peut être une excellente approximation (comme les réponses précédentes l'ont indiqué).
Juste pour avoir une idée de ce qui se passe, considérez la fréquence à laquelle votre algorithme va générer des mélanges d'un tableau d'éléments dans lequel le premier élément est fixe, k ≥ 2 . Lorsque des permutations sont générées avec une probabilité égale, cela devrait se produire 1 / k du temps. Soit p n la fréquence relative de cette occurrence après n mélange avec votre algorithme. Soyons généreux également, et supposons que vous sélectionnez en fait de manière uniforme et aléatoire des paires distinctes d'index pour vos mélanges, de sorte que chaque paire soit sélectionnée avec la probabilité =k k≥2 1/k pn n 2/(k(k-1))1/(k2) 2/(k(k−1)) . (Cela signifie qu'il n'y a pas de shuffles "triviaux" gaspillés. D'un autre côté, cela casse totalement votre algorithme pour un tableau à deux éléments, car vous alternez entre la fixation des deux éléments et leur permutation, donc si vous vous arrêtez après un nombre prédéterminé de étapes, il n'y a aucun hasard au résultat!)
Cette fréquence satisfait une simple récurrence, car le premier élément se retrouve à sa place d'origine après shuffles de deux manières disjointes. L'un est qu'il a été corrigé après shuffles et le shuffle suivant ne déplace pas le premier élément. L'autre est qu'il a été déplacé après shuffles mais le shuffle le ramène. La chance de ne pas déplacer le premier élément est égale à = , tandis que la chance de reculer le premier élément est égale à 1 / ( kn n n + 1 s t ( k - 1n+1 n n n+1st (k-2)/k(k−12)/(k2) (k−2)/k =2/(k(k-1)). D'où:1/(k2) 2/(k(k−1))
parce que le premier élément commence à sa place légitime;
La solution est
En soustrayant , nous voyons que la fréquence est fausse de ( k - 31/k . Pour les grandsketn, une bonne approximation estk-1(k−3k−1)nk−1k k n . Cela montre que l'erreurdans cette fréquence particulièrediminuera de façon exponentielle avec le nombre de swaps par rapport à la taille du tableau (n/k), indiquant qu'il sera difficile à détecter avec de grands tableaux si vous avez effectué un nombre relativement important de swaps --mais l'erreur est toujours là.k−1kexp(−2nk−1) n/k
Il est difficile de fournir une analyse complète des erreurs dans toutes les fréquences. Il est probable qu'ils se comporteront comme celui-ci, cependant, ce qui montre qu'au minimum, vous auriez besoin que (le nombre de swaps) soit suffisamment grand pour que l'erreur soit suffisamment petite. Une solution approximative estn
où devrait être très petit par rapport à 1 / k . Cela implique que n devrait être plusieurs fois k pour des approximations même brutes ( c'est-à - dire où ϵ est de l'ordre de 0,01 fois 1 / k environ).ϵ 1/k n k ϵ 0.01 1/k
Tout cela soulève la question: pourquoi choisiriez-vous d'utiliser un algorithme qui n'est pas tout à fait (mais seulement approximativement) correct, emploie exactement les mêmes techniques qu'un autre algorithme qui est prouvablement correct, et pourtant qui nécessite plus de calcul?
modifier
Le commentaire de Thilo est approprié (et j'espérais que personne ne le soulignerait, donc je pourrais être épargné ce travail supplémentaire!). Permettez-moi d'expliquer la logique.
Si vous vous assurez de générer des swaps réels à chaque fois, vous êtes complètement foutu. Le problème que j'ai signalé pour le cas s'étend à tous les tableaux. Seule la moitié de toutes les permutations possibles peut être obtenue en appliquant un nombre pair de swaps; l'autre moitié est obtenue en appliquant un nombre impair de swaps. Ainsi, dans cette situation, vous ne pouvez jamais générer une distribution uniforme de permutations (mais il y en a tellement de possibles qu'une étude de simulation pour tout k important ne sera pas en mesure de détecter le problème). C'est vraiment mauvais.k=2 k
Par conséquent, il est sage de générer des swaps au hasard en générant les deux positions indépendamment au hasard. Cela signifie qu'il y a chance à chaque fois de permuter un élément avec lui-même; c'est-à-dire de ne rien faire. Ce processus ralentit effectivement un peu l'algorithme: après n étapes, nous attendons seulement environ k - 11/k n vrais échanges se sont produits.k−1kN<N
Notez que la taille de l'erreur diminue de façon monotone avec le nombre de swaps distincts. Par conséquent, effectuer moins de swaps en moyenne augmente également l'erreur, en moyenne. Mais c'est un prix que vous devriez être prêt à payer pour surmonter le problème décrit dans la première puce. Par conséquent, mon estimation d'erreur est prudemment faible, approximativement d'un facteur .(k−1)/k
Je voulais également signaler une exception apparente intéressante: un examen attentif de la formule d'erreur suggère qu'il n'y a pas d' erreur dans le cas . Ce n'est pas une erreur: c'est correct. Cependant, ici, je n'ai examiné qu'une seule statistique liée à la distribution uniforme des permutations. Le fait que l'algorithme puisse reproduire cette seule statistique lorsque k = 3 (à savoir, obtenir la bonne fréquence de permutations qui fixent une position donnée) ne garantit pas que les permutations ont effectivement été réparties uniformément. En effet, après 2 n swaps réels, les seules permutations possibles pouvant être générées sont ( 123 ) , (k=3 k=3 2n (123) et l'identité. Seul ce dernier fixe une position donnée, donc en effet exactement un tiers des permutations fixent une position. Mais la moitié des permutations manquent! Dans l'autre cas, après 2 n + 1 swaps réels, les seules permutations possibles sont ( 12 ) , ( 23 ) et ( 13 ) . Encore une fois, exactement l'un d'entre eux fixera une position donnée, donc encore une fois nous obtenons la fréquence correcte de permutations fixant cette position, mais encore une fois nous n'obtenons que la moitié des permutations possibles.(321) 2n+1 (12) (23) (13)
Ce petit exemple permet de révéler les principaux volets de l'argument: en étant «généreux», nous sous- estimons prudemment le taux d'erreur pour une statistique particulière. Parce que ce taux d'erreur est non nul pour tous les , nous voyons que l'algorithme est cassé. De plus, en analysant la décroissance du taux d'erreur pour cette statistique, nous établissons une limite inférieure sur le nombre d'itérations de l'algorithme nécessaire pour avoir un quelconque espoir d'approcher une distribution uniforme des permutations.k≥4
la source
Je pense que votre algorithme simple mélangera les cartes correctement car le nombre de remaniements tend à l'infini.
Supposons que vous ayez trois cartes: {A, B, C}. Supposons que vos cartes commencent dans l'ordre suivant: A, B, C. Ensuite, après un mélange, vous avez les combinaisons suivantes:
Par conséquent, la probabilité que la carte A soit en position {1,2,3} est {5/9, 2/9, 2/9}.
Si nous mélangeons les cartes une deuxième fois, alors:
Cela donne 0,407.
En utilisant la même idée, nous pouvons former une relation de récurrence, c'est-à-dire:
Le codage de ceci dans R (voir le code ci-dessous), donne la probabilité que la carte A soit en position {1,2,3} comme {0,33334, 0,33333, 0,33333} après dix shuffles.
Code R
la source
One way to see that you won't get a perfectly uniform distribution is by divisibility. In the uniform distribution, the probability of each permutation is1/n! . When you generate a sequence of t random transpositions, and then collect sequences by their product, the probabilities you get are of the form A/n2t for some integer A . If 1/n!=A/n2t , then n2t/n!=A . By Bertrand's Postulate (a theorem), for n≥3 there are primes which occur in the denominator and which do not divide n , so n2t/n! is not an integer, and there isn't a way to divide the transpositions evenly into n! permutations. For example, if n=52 , then the denominator of 1/52! is divisible by 3,5,7,...,47 while the denominator of 1/522t is not, so A/522t can't reduce to 1/52! .
How many do you need to approximate a random permutation well? Generating a random permutation by random transpositions was analyzed by Diaconis and Shahshahani using representation theory of the symmetric group in
Diaconis, P., Shahshahani, M. (1981): "Generating a random permutation with random transpositions." Z. Wahrsch. Verw. Geb. 57, 159–179.
One conclusion was that it takes12nlogn transpositions in the sense that after (1−ϵ)12nlogn the permutations are far from random, but after (1+ϵ)12nlogn the result is close to random, both in the sense of total variation and L2 distance. This type of cutoff phenomenon is common in random walks on groups, and is related to the famous result that you need 7 riffle shuffles before a deck becomes close to random.
la source
Bear in mind I am not a statistician, but I'll put my 2cents.
I made a little test in R (careful, it's very slow for high
numTrials
, the code can probably be optimized):This will generate a matrix
swaps
withnumTrials+1
rows (one per trial + the original) andnumElements
columns (one per each vector element). If the method is correct the distribution of each column (i.e. of the values for each element over the trials) should not be different from the distribution of the original data.Because our original data was normally distributed we would expect all the columns not to deviate from that.
If we run
We get:
which looks very promising. Now, if we want to statistically confirm the distributions do not deviate from the original I think we could use a Kolmogorov-Smirnov test (please can some statistician confirm this is right?) and do, for instance
Which gives us p=0.9926
If we check all of the columns:
And we run
we get:
So, for the great majority of the elements of the array, your swap method has given a good result, as you can also see looking at the quartiles.
Note that, obviously, with a lower number of trials the situation is not as good:
50 trials
100 trials
500 trials
la source
Here's how I am interpreting your algorithm, in pseudo code:
We can associate a run of this algorithm with a list of2×length×num_passes integers, namely the integers returned by random_in() as the program runs. Each of these integers is in [0,length−1] , and so has length possible values. Call one of these lists a trace of the program.
That means there arelength2×length×num_passes such traces, and each trace is equally likely. We can also associate with each trace a permutation of the array. Namely, the permutation at the end of the run associated with the trace.
There arelength! possible permutations. length!<length2×length×num_passes so in general a given permutation is associated with more than one trace.
Remember, the traces are all equally likely, so for all permutations to be equally likely, any two permutations must be associated with the same number of traces. If that is true, then we must havelength!∣∣length2×length×num_passes .
Pick any primep such that p<length , but such that p∤length , which you can do for any length>2 . Then p∣∣length! but does not divide length2×length×num_passes . It follows that length!∤length2×length×num_passes and so all permutations cannot be equally likely if length>2 .
Does such a prime exist? Yes. Iflength were divisible by all primes p<length , then length−1 must be prime, but then length−1 would be such a prime that is less than but does not divide length .
Compare this to Fisher-Yates. In the first iteration, you make a choice amonglength options. The second iteration has length−1 options, and so on. In other words you have length! traces, and length!∣∣length! . It's not hard to show that each trace results in a different permutation, and from there it is easy to see that Fisher-Yates generates each permutation with equal probability.
la source