Quel est le problème avec cet algorithme de mélange «naïf»?

23

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)?

Thilo
la source
4
Je ne comprends tout simplement pas pourquoi les gens pensent que cet échange est `` plus simple '' ou `` plus naïf '' que FY ... Quand je résolvais ce problème pour la première fois, je viens d'implémenter FY (sans savoir qu'il a même un nom) , juste parce que cela me semblait le moyen le plus simple de le faire.
1
@mbq: personnellement, je les trouve tout aussi faciles, bien que je convienne que FY me semble plus "naturel".
nico
3
Quand j'ai fait des recherches sur les algorithmes de mélange après avoir écrit le mien (une pratique que j'ai abandonnée depuis), j'étais tout "merde sacrée, c'est fait, et il a un nom !!"
JM n'est pas statisticien le

Réponses:

12

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é =kk21/kpnn 2/(k(k-1))1/(k2)2/(k(k1)). (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+1nnn+1st (k-2)/k(k12)/(k2)(k2)/k =2/(k(k-1)). D'où:1/(k2)2/(k(k1))

parce que le premier élément commence à sa place légitime;

p0=1

pn+1=k2kpn+2k(k1)(1pn).

La solution est

pn=1/k+(k3k1)nk1k.

En soustrayant , nous voyons que la fréquence est fausse de ( k - 31/k . Pour les grandsketn, une bonne approximation estk-1(k3k1)nk1kkn. 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à.k1kexp(2nk1)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

n>12(1(k1)log(ϵ))

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ϵ est de l'ordre de 0,01 fois 1 / k environ).ϵ1/knkϵ0.011/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=2k

  • 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/knvrais échanges se sont produits.k1kN<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 .(k1)/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=3k=32n(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.k4

whuber
la source
1
"Soyons généreux aussi, et supposons que vous sélectionniez en fait de manière uniforme et aléatoire des paires distinctes d'index pour vos shuffles". Je ne comprends pas pourquoi cette hypothèse peut être émise et comment elle est généreuse. Il semble écarter les éventuelles permutations, ce qui entraîne une distribution encore moins aléatoire.
Thilo
1
@Thilo: Merci. Votre commentaire mérite une réponse détaillée, je l'ai donc placé dans la réponse elle-même. Permettez-moi de souligner ici qu'être «généreux» n'écarte en fait aucune permutation: il élimine simplement les étapes de l'algorithme qui, autrement, ne feraient rien.
whuber
2
Ce problème peut être analysé entièrement comme une chaîne de Markov sur le graphe de Cayley du groupe de permutation. Les calculs numériques pour k = 1 à 7 (une matrice 5040 par 5040!) Confirment que les valeurs propres les plus grandes en taille (après 1 et -1) sont exactement . Cela implique qu'une fois que vous avez résolu le problème de l'alternance du signe de la permutation (correspondant à la valeur propre de -1), les erreurs dans toutes les probabilités se désintègrent au rythme ( 1 - 2 /(k3)/(k1)=12/(k1) ou plus rapide. Je soupçonne que cela continue de s'appliquer à tous les k plus grands. (12/(k1))nk
whuber
1
Vous pouvez faire beaucoup mieux que car les probabilités sont invariantes sur les classes de conjugaison, et il n'y a que 15 partitions de 7 , vous pouvez donc analyser une matrice 15 × 15 à la place. 5040×504015715×15
Douglas Zare
8

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:

{A,B,C}, {A,B,C}, {A,B,C} #You get this if choose the same RN twice.
{A,C,B}, {A,C,B}
{C,B,A}, {C,B,A}
{B,A,C}, {B,A,C}

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:

Pr(A in position 1 after 2 shuffles) = 5/9*Pr(A in position 1 after 1 shuffle) 
                                     + 2/9*Pr(A in position 2 after 1 shuffle) 
                                     + 2/9*Pr(A in position 3 after 1 shuffle) 

Cela donne 0,407.

En utilisant la même idée, nous pouvons former une relation de récurrence, c'est-à-dire:

Pr(A in position 1 after n shuffles) = 5/9*Pr(A in position 1 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 2 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 3 after (n-1) shuffles).

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

## m is the probability matrix of card position
## Row is position
## Col is card A, B, C
m = matrix(0, nrow=3, ncol=3)
m[1,1] = 1; m[2,2] = 1; m[3,3] = 1

## Transition matrix
m_trans = matrix(2/9, nrow=3, ncol=3)
m_trans[1,1] = 5/9; m_trans[2,2] = 5/9; m_trans[3,3] = 5/9

for(i in 1:10){
  old_m = m
  m[1,1] = sum(m_trans[,1]*old_m[,1])
  m[2,1] = sum(m_trans[,2]*old_m[,1])
  m[3,1] = sum(m_trans[,3]*old_m[,1])

  m[1,2] = sum(m_trans[,1]*old_m[,2])
  m[2,2] = sum(m_trans[,2]*old_m[,2])
  m[3,2] = sum(m_trans[,3]*old_m[,2])

  m[1,3] = sum(m_trans[,1]*old_m[,3])
  m[2,3] = sum(m_trans[,2]*old_m[,3])
  m[3,3] = sum(m_trans[,3]*old_m[,3])
}  
m
csgillespie
la source
1
+1. Cela démontre que la probabilité qu'une carte donnée se retrouve dans une position donnée se rapproche du ratio attendu à mesure que le nombre de shuffles augmente. Cependant, il en serait de même pour un algorithme qui ne fait tourner le tableau qu'une seule fois d'un montant aléatoire: toutes les cartes ont une probabilité égale de se retrouver dans toutes les positions, mais il n'y a toujours aucun hasard (le tableau reste trié).
Thilo
@Thilo: Désolé de ne pas suivre votre commentaire. Un "algorithme tourne par une quantité aléatoire" mais il n'y a toujours "pas d'aléatoire"? Pourriez-vous expliquer davantage?
csgillespie
Si vous "mélangez" un tableau à N éléments en le faisant pivoter entre 0 et N-1 positions (au hasard), alors chaque carte a exactement la même probabilité de se retrouver dans l'une des N positions, mais 2 est toujours toujours situé entre 1 et 3.
Thilo
1
@Thio: Ah, je comprends votre point. Eh bien, vous pouvez calculer la probabilité (en utilisant exactement la même idée que ci-dessus), pour le Pr (A en position 2) et Pr (A en position 3) - dito pour les cartes B et C. Vous verrez que toutes les probabilités ont tendance à 1/3. Remarque: ma réponse ne donne qu'un cas particulier, tandis que @whuber nice answer donne le cas général.
csgillespie
4

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 is 1/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 n3 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 takes 12nlogn 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.

Douglas Zare
la source
2

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):

numElements <- 1000
numTrials <- 5000

swapVec <- function()
    {
    vec.swp <- vec

    for (i in 1:numElements)
        {
        i <- sample(1:numElements)
        j <- sample(1:numElements)

        tmp <- vec.swp[i]
        vec.swp[i] <- vec.swp[j]
        vec.swp[j] <- tmp
        }

    return (vec.swp)
    }

# Create a normally distributed array of numElements length
vec <- rnorm(numElements)

# Do several "swapping trials" so we can make some stats on them
swaps <- vec
prog <- txtProgressBar(0, numTrials, style=3)

for (t in 1:numTrials)
    {
    swaps <- rbind(swaps, swapVec())
    setTxtProgressBar(prog, t)
    }

This will generate a matrix swaps with numTrials+1 rows (one per trial + the original) and numElements 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

par(mfrow= c(2,2))
# Our original data
hist(swaps[1,], 100, col="black", freq=FALSE, main="Original")
# Three "randomly" chosen columns
hist(swaps[,1], 100, col="black", freq=FALSE, main="Trial # 1") 
hist(swaps[,257], 100, col="black", freq=FALSE, main="Trial # 257")
hist(swaps[,844], 100, col="black", freq=FALSE, main="Trial # 844")

We get:

Histograms of random trials

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

ks.test(swaps[1, ], swaps[, 234])

Which gives us p=0.9926

If we check all of the columns:

ks.results <- apply(swaps, 2, function(col){ks.test(swaps[1,], col)})
p.values <- unlist(lapply(ks.results, function(x){x$p.value})

And we run

hist(p.values, 100, col="black")

we get:

Histogram of Kolmogorov-Smirnov test p values

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.

1> quantile(p.values)
       0%       25%       50%       75%      100% 
0.6819832 0.9963731 0.9999188 0.9999996 1.0000000

Note that, obviously, with a lower number of trials the situation is not as good:

50 trials

1> quantile(p.values)
          0%          25%          50%          75%         100% 
0.0003399635 0.2920976389 0.5583204486 0.8103852744 0.9999165730

100 trials

          0%         25%         50%         75%        100% 
 0.001434198 0.327553996 0.596603804 0.828037097 0.999999591 

500 trials

         0%         25%         50%         75%        100% 
0.007834701 0.504698404 0.764231550 0.934223503 0.999995887 
nico
la source
0

Here's how I am interpreting your algorithm, in pseudo code:

void shuffle(array, length, num_passes)
  for (pass = 0; pass < num_passes; ++pass) 
    for (n = 0; n < length; ++)
      i = random_in(0, length-1)
      j = random_in(0, lenght-1)
      swap(array[i], array[j]

We can associate a run of this algorithm with a list of 2×length×num_passes integers, namely the integers returned by random_in() as the program runs. Each of these integers is in [0,length1], and so has length possible values. Call one of these lists a trace of the program.

That means there are length2×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 are length! 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 have length!|length2×length×num_passes.

Pick any prime p such that p<length, but such that plength, 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. If length were divisible by all primes p<length, then length1 must be prime, but then length1 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 among length options. The second iteration has length1 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.

tzs
la source