Je voudrais produire des mélanges aléatoires rapides à plusieurs reprises avec un biais minimal.
Il est connu que le Fisher-Yates Shuffle est impartiale tant que le générateur de nombres aléatoires sous-jacents (RNG) est impartial. P>
To shuffle an array a of n elements:
for i from n − 1 downto 1 do
j ↠random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
5 Réponses :
Quelques points:
1) Toute personne utilisant le Fisher Yates Shuffle devrait lire Ceci et faire doublement sûr que leur mise en œuvre est correcte.
2) Ne répétant pas le shuffle battu le but d'utiliser un générateur de nombres aléatoires plus rapide? Sûrement si vous allez devoir répéter chaque aléatoire 5 fois pour obtenir l'entropie souhaitée, vous feriez mieux d'utiliser un générateur de biais bas.
3) Avez-vous une configuration là où vous pouvez tester cela? Si oui, commencez à essayer des choses - les graphiques Jeffs indiquent clairement que vous pouvez facilement détecter de nombreuses erreurs en utilisant de petits ponts et décrivant visuellement les résultats.
Le shuffle indiqué dans la question initiale est Fisher-Yates et est correctement mis en œuvre.
J'ai trouvé 1.) Intéressant parce que je pensais que la plupart des codeurs savaient déjà comment shuffer correctement. Cependant, je regardais la suite de tests de tri pour Open JDK et j'ai vu qu'ils faisaient juste le shuffle naïf à plusieurs reprises lors de la remaniement des données de test. Je me demandais s'ils avaient une raison pour cela, mais je suppose que non.
A propos du point 2, je veux utiliser chaque shuffle aléatoire, mais simplement le réutiliser pour le prochain shuffle. Pas mélanger 2 fois ou plus avant d'utiliser la permutation.
En ce qui concerne les graphiques de Jeff, l'utilisation de petits ensembles indique facilement les différences facilement, mais pour le mélange de disent, un jeu de cartes, N = 52, la quantité de fois que vous devriez porter à montrer des différences statistiquement significatives est assez étonnante. Donc, pour ceux qui sont beaucoup plus faciles à utiliser des preuves.
Je conviens qu'un test simple serait de voir que chaque permutation (par exemple de 5 sur 25) est produite à peu près également sur une taille d'échantillon élevée. Avec un jeu de cartes, comme Nicklalarsen Spoint, cela est plus difficile à faire, si nous voulons des permutations complètes de 52.
@Nicklarsen: Dépend de la manière dont votre rng est biaisé. Si elle alterne entre les sorties impaires et même les sorties, vous pourrez peut-être détecter le biais avec une confiance accablante dans un Single shuffle d'un pont de 52 cartes.
Je ne peux pas répondre complètement à votre question, mais cette observation semblait trop longtemps pour un commentaire.
Que se passe-t-il si vous vous assurez que le nombre de nombres aléatoires tirés de votre RNG pour chaque itération de Fisher-Yates a un multiple le moins commun élevé avec la période RNG? Cela peut signifier que vous «perdez» un entier aléatoire à la fin de l'algorithme. Lorsque vous mélangez 25 éléments, vous avez besoin de 24 numéros aléatoires. Si vous tirez un numéro aléatoire de plus à la fin, effectuez 25 numéros aléatoires, vous n'êtes pas garanti d'avoir une répétition plus longue que la période RNG. Maintenant, au hasard, vous pourriez avoir le même nombre de 25 numéros se produisent successivement avant d'atteindre la période, bien sûr. Mais, comme 25 n'a aucun facteur commun autre que 1 avec 2 ^ 32, vous ne frapperiez pas une répétition garantie avant 25 * (2 ^ 32). Maintenant, ce n'est pas une énorme amélioration, mais que vous avez dit que RNG est rapide. Et si la valeur "déchets" était beaucoup plus grande? Il ne peut toujours pas être pratique d'obtenir toutes les permutations, mais vous pouvez au moins augmenter le nombre que vous pouvez atteindre.
C'est une observation intéressante. Je suppose que les permutations répétées ne sont généralement pas un problème. Je pense que le "branlant le tableau précédemment mélangé" pourrait seulement rendre la période plus longue entre les répétitions.
Si le RNG n'a qu'une période de 2 ^ 32 ~ 10 ^ 9 Nous ne pouvons pas produire tous les possibles permutation des 25 éléments parce que C'est 25! ~ 10 ^ 25 permutations
Ceci n'est vrai que tant que la graine détermine chaque sélection successive. Tant que votre RNG peut être censé livrer une distribution précise même sur la plage spécifiée pour chaque sélection suivante, elle peut produire chaque permutation. Si votre RNG ne peut pas faire cela, une base de semences plus grande ne vous aidera pas.
Quant à votre question secondaire, vous pourriez aussi bien réexécuter pour chaque tirage au sort. Cependant, la réensemencement du générateur n'est utile que si la réensorisation contient suffisamment d'entropie. Les horodatages ne contiennent pas beaucoup d'entropie, ni les calculs algorithmiques.
Je ne suis pas sûr de la partie de cette solution car vous ne l'avez pas répertorie, mais si vous essayez de calculer quelque chose à partir d'un domaine plus vaste à l'aide d'une entrée aléatoire, il existe probablement de meilleures méthodes.
Non, il a raison - si votre RNG a une période de 10 ^ 9, il ne peut pas générer 25! séquences distinctes, et donc tous les mélanges ne sont pas également probables. Je ne m'attendrais pas à voir un parti pris systématique dans lequel les mélanges sont possibles, si le PRNG est même parfait à distance.
Je n'ai jamais dit qu'il avait tort. J'ai souligné que ce qu'il a dit uniquement lors de l'utilisation d'une RNG avec une période inférieure à la permutation totale et que la graine détermine chaque nombre successif généré. Il existe un certain nombre de méthodes de RNG alternatives qui n'utilisent pas de graines ou ont des périodes. Lorsque vous retirez la dépendance d'une graine, mes revendications sont correctes.
Bon point. Je considérais seulement les RNG qui produisent une séquence unique avec une certaine période (disons 2 ^ 32) et la graine ne détermine que le point de départ de cette séquence, telle que de simples générateurs congrandentiels linéaires.
Mon sentiment est que, avec une RNG biaisée, des courses répétées du knuth Shuffle produiraient toutes les permutations, mais je ne suis pas capable de le prouver (cela dépend de la période de la RNG et du Combien de biaiser est ).
Inversons la question suivante: Étant donné un algorithme qui nécessite une entrée aléatoire et une RNG biaisée, est-il plus facile de désenvoyer la production de l'algorithme ou de désembourber la sortie de la RNG?
Sans surprise, ce dernier est beaucoup plus facile à faire (et est d'un intérêt plus large): il existe plusieurs techniques standard pour le faire. Une technique simple, due à Von Neumann, est la suivante: étant donné un bitstream provenant d'une rng biaisée, prenez des bits par paires, jetez chaque paire (0,0) et (1,1), retourne 1 pour chaque (1,0) paire et un 0 pour chaque paire (0,1). Cette technique suppose que les bits proviennent d'un flux où chaque bit a la même probabilité d'être un 0 ou 1 comme tout autre bit dans le flux et que les bits ne sont pas corrélés. Elias généralisée Technique de Von Neumann's à un schéma plus efficace (un où moins de bits sont jetés).
mais même fortement biaisés ou corrélés, peut contenir des quantités utiles de aléatoire, par exemple Utilisation d'une technique basée sur une transformation FAIS FOURIER .
Une autre option consiste à alimenter la sortie RNG biaisée à une fonction cryptographiquement forte, par exemple un algorithme de digère de message et utilisez sa sortie.
Pour plus d'informations sur les générateurs de nombres aléatoires désignés, je vous suggère de lire le Recommandations de randomneur pour la sécurité RFC .
Mon point est que la qualité si la sortie d'un algorithme à base aléatoire est supérieure à la limite supérieure par l'entropie fournie par le RNG: s'il est extrêmement biaisé, la sortie sera extrêmement biaisée, peu importe ce que vous faites. L'algorithme ne peut pas presser plus d'entropie que celle contenue dans le Bitstream aléatoire biaisé. Pire: ça va probablement perdre des bits aléatoires. Même en supposant que l'algorithme fonctionne avec une RNG biaisée, pour obtenir de bons résultats, vous devrez mettre un effort informatique au moins aussi grand que les efforts qu'il faudrait pour désembarrer la RNG (mais cela nécessitera probablement plus d'effort, Depuis que vous devrez gérer l'algorithme et "vaincre" la biaiser en même temps).
Si votre question est juste théorique, veuillez ignorer cette réponse. Si c'est pratique, veuillez considérer sérieusement à désagréger votre RNG au lieu de faire de l'hypothèse sur la sortie de l'algorithme.
Merci pour votre réponse. Je pense que désagréguer coûterait plus que simplement utiliser un RNG plus lent, mais mieux.
J'ai édité ma réponse pour clarifier mon point (c'était trop long pour un commentaire). La ligne de fond est la suivante: l'entropie de l'algorithme ne peut pas être supérieure à l'entropie fournie par le RNG, ainsi que même si l'algorithme fonctionne avec des rngs biaisés, vous devez l'appliquer à nouveau un certain nombre de temps suffisamment aléatoire. BITS - Cet effort de calcul ne peut être inférieur à celui requis pour désembourber la RNG (et il est en fait probablement beaucoup plus élevé).
Pour mélanger un tableau de 25 éléments, nous devons prendre les numéros aléatoires bruts, puis appliquer le module 25, 24, 23, ..., 2. Cela semblerait ajouter au hasard. La réutilisation également de la liste de shuffle précédente ajoute à l'état "State", alors ne pouvons-nous pas penser à l'algorithme RNG + "de shuffle à l'aide d'un aléatoire précédent" comme un "générateur de permutation aléatoire" avec plus d'état que le RNG sous-jacent, et donc plus "aléatoire" ?
Non, nous ne pouvons pas. A (P) RNG est un algorithme qui prend peu de bits vraiment aléatoires (la graine) et "répandre" leur entropie sur un long flux de bits. L'état de la RNG assure que compte tenu d'une graine de bits N, le RNG sortira l'une des sorties de 2 ^ n possibles et que toutes les graines différentes entraînent une bite de sortie différente. Ajout de plus de bits d'état, de quelque manière que ce soit (y compris les alimentant à un algorithme) ne génère pas d'entropie, vous en perdez probablement certains parce que votre état supplémentaire (dans votre cas la position des cartes) n'est pas conçu pour mapper quelques bits d'entropie à un long bitstream pseudo-aléatoire.
Il n'a pas ajouté au hasard dans le sens où si vous connaissez l'état de départ, vous pouvez prédire toutes les permutations successives. Mais si vous ne connaissez pas la graine de départ, dites-vous qu'en regardant la séquence de sortie des permutations, vous pouvez dire qu'elles ne sont pas vraiment aléatoires aussi facilement que de regarder la séquence de nombres produits par le RNG sous-jacent? La période des permutations est plus longue que la période de la RNG, de sorte que cet essai de hasard est plus difficile à tromper.
Je vois ce que tu veux dire. Mon sentiment d'intestin est que cela augmenterait la complexité spatiale mais pas la complexité de temps. Mais je ne suis pas sûr et je ne peux pas le prouver, alors mon conseil est: à moins que vous ne puissiez justifier fortement pourquoi utiliser plusieurs mélanges est le meilleur choix, vous devriez désigné votre RNG ou utiliser un meilleur - ce qui est le meilleur s'entraîner. À titre de note latérale, la sortie de nombreux RNG peut être prédite même sans connaître leur état de départ, juste en observant leur sortie passée (par exemple, voir springerlink.com/content/p4526x2j040m7j12 portail. acm.org/citation.cfm?id=1290930.1290938 ).
Il existe une classe spéciale de RNG qui, compte tenu de certaines hypothèses, garantissent vivement que leur production ne fuit pas son état interne. Ces RNG sont appelés CSprng (Cryptographiquement fort RNG). Si vous ne pouvez pas risquer que quelqu'un devine l'état de votre RNG, vous devez utiliser un CSprng. Et certains d'entre eux sont assez rapides aussi (par exemple, Isaac).
Merci pour toutes ces informations. Tout est très intéressant, mais je n'ai pas besoin d'un rng cryptographique robuste. J'ai vraiment besoin de quelque chose qui produit toutes les permutations possibles avec une probabilité égale. En utilisant le shuffle précédent sur les itérations successives, semble que cela ne puisse pas nuire et est plus efficace. Et certains tests simples devraient être suffisamment bons.
@JOHNPS Il me semble que si vous répétez plusieurs fois la permutation la même la même la permanence, limitant au moins l'ensemble des permutations réalisables (en plus de la limitation causée par la petite période de Le PRNG que vous mentionnez dans votre message d'origine et par le petit ensemble de valeurs de semences disponibles) en limitant les permutations de carrés (ou de cubes, etc.) d'autres permutations. Je me demande si l'application de plusieurs permutations différentes de succession pourrait augmenter le nombre de permutations pouvant être obtenues?
Je suppose que cela a trait à la génération de jeux pour le groupe symétrique sur les symboles n et les longueurs de mots par rapport à ces ensembles générateurs.
Cela dépend entièrement du biais. En général, je dirais "ne comptez pas dessus".
Ne rien faire la moitié du temps, et un mélange correct d'une autre moitié. Converge vers le non-biaisé de manière exponentielle. Après n Shuffles, il y a une chance de 1-1 / 2 ^ N, le shuffle n'est pas biaisé et une chance 1/2 ^ N la séquence d'entrée a été sélectionnée.
Mélangez tous les éléments sauf le dernier. Polariquement biaisé pour ne pas déplacer le dernier élément.
Pensez à un algorithme de shuffle comme un graphique pondéré dirigé des permutations, où les poids d'un nœud correspondent à la probabilité de transition d'une permutation à une autre lorsqu'il est mélangé. Un algorithme de shuffle biaisé aura des poids non uniformes.
Supposons maintenant que vous avez rempli un nœud dans ce graphique avec de l'eau et l'eau a coulé d'un nœud au prochain basé sur les poids. L'algorithme convergera à des non-biaisés si la distribution de l'eau converge en uniforme, quel que soit le nœud de départ.
Donc, dans quels cas l'eau ne se répandra pas uniformément? Eh bien, si vous avez un cycle de poids supérieurs à la moyenne, les nœuds du cycle auront tendance à se nourrir et à rester au-dessus de la quantité moyenne d'eau. Ils ne prendront pas tout cela, car comme ils obtiennent plus d'eau, le montant de la diminution et le montant sortit augmente, mais ce sera au-dessus de la moyenne.
"Mélangez tous les éléments sauf le dernier." Mais je demande quoi si l'algorithme de shuffle n'est pas biaisé, mais le RNG sous-jacent est? C'est peut-être ce que vous avez adressé dans la dernière partie. Je pouvais croire que des permutations consécutives pourraient être corrélées si le RNG est biaisé, mais je pense que le RNG devra être plutôt mauvais pour remarquer juste en examinant les permutations. Je suppose que les tests sont nécessaires pour savoir à coup sûr.
En supposant une fonction de shuffle qui n'a pas de permutations inaccessibles, le RNG peut être utilisé pour simuler n'importe quel algorithme que vous souhaitez.
Avez-vous déjà testé cela pour obtenir la réponse?
Je n'ai pas fait de tests formels sur le biais. Je crois qu'avec un RNG biaisé, il y aurait un biais d'un mélange à l'autre, mais peut-être pas perceptible lorsque vous regardez les totaux de chaque permutation sélectionnée sur des millions de permutations. J'ai fini par utiliser un générateur de fibonacci (LFG) à retardement (LFG) et laissant le pont dans l'état mélangé pour commencer la prochaine permutation. Je pense que cela est impartial, et c'est assez rapide pour moi. Je suis donc allé avec le RNG rapide et optimiser tout le plus possible.
Au moment où vous avez mélangé suffisamment pour éliminer les biais, vous aurez été mieux en train d'utiliser l'une une fois.