Faux nombres aléatoires uniformes: Plus uniformément distribués que de vraies données uniformes

43

Je cherche un moyen de générer des nombres aléatoires qui semblent distribués de manière uniforme - et chaque test montrera qu'ils sont uniformes - sauf qu'ils sont distribués de manière plus uniforme que les données véritablement uniformes .

Le problème que j'ai avec les "vrais" aléas uniformes, c'est qu'ils vont parfois se regrouper. Cet effet est plus fort lorsque l'échantillon est petit. En gros, quand je dessine deux ronds uniformes dans U [0; 1], il y a de bonnes chances qu'ils se situent dans une fourchette de 0,1% à 1%, et à 1% dans un intervalle de 0,01.

Je cherche donc un bon moyen de générer des nombres aléatoires mieux répartis que les aléas uniformes .

Exemple d'utilisation: disons que je fais un jeu d'ordinateur et que je veux placer un trésor au hasard sur une carte (sans se soucier de rien d'autre). Je ne veux pas que le trésor soit tout au même endroit, il devrait être partout sur la carte. Avec des randoms uniformes, si je place, disons, 10 objets, les chances qu’il y en ait 5 vraiment très proches ne sont pas très faibles. Cela peut donner à un joueur un avantage sur un autre. Pensez au dragueur de mines, les chances (bien que faibles, s’il ya suffisamment de mines) sont que vous ayez vraiment de la chance et que vous gagniez en un seul clic.

Une approche très naïve de mon problème consiste à diviser les données en une grille. Tant que le nombre est assez grand (et comporte des facteurs), on peut imposer une uniformité supplémentaire de cette façon. Ainsi, au lieu de tirer 12 variables aléatoires de U [0; 1], je peux en tirer 6 de U [0; 0,5] et 6 de U [0,5; 1] ou 4 de U [0; 1/3] + 4. de U [1/3; 2/3] + 4 de U [2/3; 1].

Y a-t-il un meilleur moyen d'obtenir cette uniformité supplémentaire dans l'uniforme? Cela ne fonctionne probablement que pour les aléas de lot (lorsque je trace un seul hasard, je dois évidemment prendre en compte toute la gamme). En particulier, je pourrai mélanger à nouveau les disques par la suite (donc ce ne sont pas les quatre premiers du premier tiers).

Pourquoi ne pas le faire progressivement? Donc, le premier est sur U [0; 1], puis deux de chaque moitié, une de chaque troisième, une de chaque quatrième? At-on enquêté sur cette question et quelle est sa qualité? Je devrais faire attention à utiliser des générateurs différents pour x et y afin de ne pas les mettre en corrélation (le premier xy serait toujours dans la moitié inférieure, le second dans la moitié gauche et le troisième en bas, le troisième au centre et le troisième en haut). Donc, au moins une certaine permutation aléatoire des bacs est également nécessaire et, à long terme, elle sera trop uniforme, je suppose.

En tant que nœud latéral, existe-t-il un test bien connu permettant de déterminer si une distribution est trop uniformément répartie pour être vraiment uniforme? Donc, tester "vrai uniforme" contre "quelqu'un a foiré les données et a distribué les articles plus équitablement". Si je me souviens bien, Hopkins Statistic peut mesurer cela, mais peut-il aussi être utilisé pour des tests? Également un test KS inverse: si la plus grande déviation est inférieure à un certain seuil prévu, les données sont trop uniformément distribuées?

Anony-Mousse
la source
7
Avez-vous entendu parler de séquences de Halton ? Pour "trop ​​uniformément", les gens (à commencer par l'enquête de Fisher sur les résultats de l'expérience de pois de Mendel) ont fait référence à la statistique (habituelle) du khi-carré à la queue inférieure d'une distribution du khi-carré.
whuber
Une façon de formaliser ce serait vouloir une distribution tel que (1) g ( ) marginalise à 1 sur x 1 , . . . , X n - 1 , (2) g est symétrique, à savoir X 1 , . . . , X n sont échangeables, et (3) g ( x 1 , .g(x1,...,xn)g()1x1,...,xn1gX1,...,Xn est grande lorsque x 1 , . . . , x n sont dispersés. Je pense qu'il ya un vrai problème avec (2) et (3) puisqueséquences échangeables infinies R ne peuvent pas être corrélées négativement,sortele plus grand n que nous voulons utiliser la répulsion moins nous pouvons appliquer; Par contre, pour le grand n , nous devrions quand même avoir une bonne propagation. g(x1,...,xn)x1,...,xnRnn
mec
La séquence de Halton est assez proche de l’approche à laquelle je pensais. Y compris sauter les premières entrées pour réduire le risque de corrélation. Je pensais aussi à utiliser une permutation aléatoire pour chaque niveau. Merci pour ce pointeur, car cela me donne un bon point pour rechercher des méthodes apparentées!
Anony-Mousse
wrt. Halton séquence à nouveau. Je dois les avoir non déterministes, au moins sauf pour une graine initiale. Je vois deux façons ici. Je peux effectuer un décalage cyclique par un décalage aléatoire + un décalage de départ aléatoire + une taille de pas. Le problème est que, bien sûr, le "trésor" à rester dans l'exemple de jeu ne doit pas non plus être dans les mêmes positions les unes par rapport aux autres. Ou je pourrais utiliser cette approche uniforme de sous-intervalle que j'avais dans ma question pour ajouter une certaine quantité de "torsion aléatoire". Donc, dire: Halton semble encore trop prévisible et régulier pour mon utilisation.
Anony-Mousse
3
en.wikipedia.org/wiki/Low-discrepancy_sequence ou mathworld.wolfram.com/QuasirandomSequence.html . Plusieurs des tests courants de RNG uniformes (tels que ceux des batteries de tests Diehard / Dieharder) sont sensibles à de telles choses; Par exemple, il y a trop peu de «petites distances» entre les points.
Glen_b

Réponses:

60

Oui , il existe de nombreuses façons de produire une suite de nombres mieux distribuée que les uniformes aléatoires. En fait, tout un domaine est dédié à cette question; c'est l'épine dorsale de quasi-Monte Carlo (QMC). Vous trouverez ci-dessous un bref aperçu des bases absolues.

Mesure de l'uniformité

nx1,x2,,xn[0,1]dd

Dn:=supRR|1ni=1n1(xiR)vol(R)|,
R[a1,b1]××[ad,bd][0,1]d0aibi1 et est l'ensemble de tous ces rectangles. Le premier terme à l'intérieur du module est la proportion "observée" de points à l'intérieur de et le second terme est le volume de , .RRRvol(R)=i(biai)

La quantité est souvent appelée écart ou écart extrême de l'ensemble des points . Intuitivement, nous trouvons le "pire" rectangle où la proportion de points diffère le plus de ce à quoi nous nous attendions sous une uniformité parfaite.Dn(xi)R

C'est difficile à manier et difficile à calculer. Pour la plupart, les gens préfèrent travailler avec la discordance en étoile , La seule différence est l'ensemble sur lequel le supremum est pris. C'est l'ensemble des rectangles ancrés (à l'origine), c'est-à-dire où .

Dn=supRA|1ni=1n1(xiR)vol(R)|.
Aa1=a2==ad=0

Lemme : pour tout , . Preuve . La main gauche est évidente liée depuis . La borne de droite suit parce que chaque peut être composé via des unions, des intersections et des compléments de rectangles ancrés au maximum (c'est-à-dire, dans ).DnDn2dDnnd
ARRR2dA

Ainsi, nous voyons que et sont équivalents en ce sens que si l'un est petit comme grandit, l'autre le sera aussi. Voici une image (dessin animé) montrant les rectangles candidats pour chaque écart.DnDnn

divergence extrême et étoile

Exemples de "bonnes" séquences

Sans surprise, les séquences avec une différence d'étoile vérifiable, sont souvent appelées séquences de divergences faibles .Dn

van der Corput . C'est peut-être l'exemple le plus simple. Pour , les séquences de van der Corput sont formées en développant le nombre entier en binaire, puis en "reflétant les chiffres" autour du point décimal. Plus formellement, cela se fait avec la fonction inverse radicale en base , où et sont les chiffres du développement en base de . Cette fonction constitue également la base de nombreuses autres séquences. Par exemple, en binaire est et ainsid=1ib

ϕb(i)=k=0akbk1,
i=k=0akbkakbi41101001a0=1 , , , , et . Ainsi, le 41ème point de la suite de van der Corput est .a1=0a2=0a3=1a4=0a5=1x41=ϕ2(41)=0.100101(base 2)=37/64

Notez que parce que le bit le moins significatif de oscille entre et , les points pour les impairs sont dans , alors que les points pour les pairs sont dans .i01xii[1/2,1)xii(0,1/2)

Séquences de Halton . Parmi les plus classiques des séquences classiques à faible divergence, il s'agit d'extensions de la séquence de van der Corput à plusieurs dimensions. Laissez le e plus petit nombre premier. Ensuite, le ème point de la séquence de dimension dimensionale est Pour les faibles ceux-ci fonctionnent assez bien, mais ont des problèmes dans les dimensions supérieures .pjjixid

xi=(ϕp1(i),ϕp2(i),,ϕpd(i)).
d

Les séquences de Halton satisfont à . Ils sont également intéressants parce qu’ils sont extensibles en ce sens que la construction des points ne dépend pas d’ un choix a priori de la longueur de la séquence .Dn=O(n1(logn)d)n

Séquences de Hammersley . Il s’agit d’une modification très simple de la séquence de Halton. Nous utilisons plutôt Peut-être étonnamment, l’avantage est qu’ils ont une meilleure discordance entre les étoiles .

xi=(i/n,ϕp1(i),ϕp2(i),,ϕpd1(i)).
Dn=O(n1(logn)d1)

Voici un exemple des séquences de Halton et Hammersley en deux dimensions.

Halton et Hammersley

Séquences de Halton permuté par Faure . Un ensemble spécial de permutations (fixées en fonction de ) peut être appliqué au développement de chiffres pour chaque lors de la production de la séquence de Halton. Cela permet de remédier (dans une certaine mesure) aux problèmes évoqués dans les dimensions supérieures. Chacune des permutations a la propriété intéressante de garder et tant que points fixes.iaki0b1

Règles de treillis . Soit entiers. Prenez où désigne la partie de . Un choix judicieux des valeurs donne de bonnes propriétés d'uniformité. De mauvais choix peuvent conduire à de mauvaises séquences. Ils ne sont pas non plus extensibles. Voici deux exemples.β1,,βd1

xi=(i/n,{iβ1/n},,{iβd1/n}),
{y}yβ

Bons et mauvais réseaux

(t,m,s) filets . réseaux de la base sont des ensembles de points tels que chaque rectangle de volume dans contient points. C'est une forme forte d'uniformité. Petit est votre ami, dans ce cas. Les séquences de Halton, Sobol 'et Faure sont des exemples de réseaux . Celles-ci se prêtent bien à la randomisation via le brouillage. Le brouillage aléatoire (fait à droite) d'un réseau produit un autre réseau . Le projet MinT conserve une collection de telles séquences.(t,m,s)bbtm[0,1]sbtt(t,m,s)(t,m,s)(t,m,s)

Randomisation simple: rotations Cranley-Patterson . Soit une suite de points. Soit . Alors les points sont uniformément distribués dans .xi[0,1]dUU(0,1)x^i={xi+U}[0,1]d

Voici un exemple où les points bleus sont les points d'origine et les points rouges sont les points pivotés avec des lignes les reliant (et représentés, le cas échéant).

Cranley Patterson

Séquences complètement uniformément distribuées . C'est une notion encore plus forte d'uniformité qui entre parfois en jeu. Soit la suite de points dans et forme maintenant des blocs superposés de taille pour obtenir la suite . Donc, si , on prend puis , etc. Si, pour tout , , alors est dit être uniformément distribué . En d' autres termes, la séquence donne un ensemble de points de toute(ui)[0,1]d(xi)s=3x1=(u1,u2,u3)x2=(u2,u3,u4) s1Dn(x1,,xn)0(ui)dimension qui possède des propriétés souhaitables .Dn

A titre d’exemple, la suite de van der Corput n’est pas complètement uniformément distribuée car pour , les points sont dans le carré et les points sont dans . Il n’ya donc pas de points dans le carré ce qui implique que pour , pour tout .s=2x2i(0,1/2)×[1/2,1)x2i1[1/2,1)×(0,1/2)(0,1/2)×(0,1/2)s=2Dn1/4n

Références standard

La monographie de Niederreiter (1992) et le texte de Fang et Wang (1994) sont des endroits à explorer.

cardinal
la source
4
Cette réponse est excellente et je voulais simplement apprécier les efforts que vous avez déployés. Merci!
Anony-Mousse
1
Une petite question de suivi. Les séquences de Halton semblent bonnes, car elles ne semblent pas non plus trop régulières. Le matériel en treillis est beaucoup trop habituel pour moi, et la séquence de Hammersley semble avoir beaucoup d'objets sur les lignes qui traversent l'origine. Quel est le bon moyen de contrôler l’équilibre entre le véritable uniforme et le faux uniforme? Il suffit de prendre 80% de contribution de Halton + 20% d’aléatoire uniforme?
Anony-Mousse
1
+ 10k et certainement avec un record record (87 !!!!) répond! Oh, et j'aime beaucoup ce post. J'ai marqué la question à cause de cela, en fait. Bien fait, cardinal.
Macro
@ Macro: Merci pour ce commentaire! Vous êtes très gentil. Je pense que cette chose 10K peut être temporaire pour moi. Je soupçonne que je pourrais tomber bien en dessous de 10K dès que les votes de Procrastinator seront annulés. Je suis surpris que ce ne soit pas encore arrivé. Je crois qu'ils ont enregistré près de 3000 votes sur ce site. Merci aussi d'avoir posté ici; D'une manière ou d'une autre, je n'ai jamais vu les questions de suivi d'Anony-Mousse!
cardinal
@ Anony-Mousse: Toutes mes excuses pour le retard terrible à répondre. J'ai dû oublier ces commentaires. Je pense que la création d'un équilibre dépend de vos objectifs. Théoriquement, l’introduction de points uniformes aléatoires va nécessairement détruire les propriétés optimales de , par exemple. En pratique, il peut être préférable d’utiliser une très petite gigue des points de la console QMC, la gigue étant choisie en fonction des propriétés de la séquence. Vous pouvez également introduire des transformations aléatoires de corps rigides sur tous les points, par exemple des décalages et des rotations de coordonnées. DD
cardinal
3

Une façon de le faire serait de générer des nombres aléatoires uniformes, puis de tester la "proximité" en utilisant la méthode de votre choix, puis de supprimer les éléments aléatoires trop proches des autres et de choisir un autre ensemble d'uniformes aléatoires pour les compenser.

Une telle distribution réussirait-elle tous les tests d'uniformité? J'espère bien que non! Ce n'est plus uniformément distribué, c'est maintenant une autre distribution.

Un aspect non intuitif de la probabilité est que la chance est volumineuse. Dans les données aléatoires, il y a plus d'essais que nous le pensons. Je pense que Tversky a fait des recherches à ce sujet (il a tellement fait des recherches qu'il est difficile de s'en souvenir).

Peter Flom - Rétablir Monica
la source
2
L'un des (nombreux) problèmes de cette approche est qu'il est très difficile de caractériser la distribution résultante.
whuber
Le PO semble le plus préoccupé par la petite taille des échantillons. Cela suggérerait qu'il n'a pas besoin de se soucier de la distribution entière. Supposons que vous ayez un ensemble de coordonnées, que vous en génériez un autre, puis calculiez la distance euclidienne par rapport à tous les autres. Si la distance minimale est inférieure à un seuil, jetez le nombre et générez-en un nouveau. Je pense que la solution de Peter fonctionne bien.
Jean
@ whuber Il ne semble pas s'intéresser à cela, bien que je puisse me tromper.
Peter Flom - Rétablir Monica
2
Permettez-moi de préciser un peu plus mon objection, Peter: lorsque vous supprimez et / ou ajustez des valeurs pseudo-aléatoires de manière ad hoc afin de vous rapprocher d'une propriété souhaitée, telle que l'absence de regroupement, il est difficile de garantir que les séquences résultantes ont toutes les propriétés souhaitables. Avec votre méthode, par exemple, pourriez-vous même nous dire quel serait le premier moment du processus résultant? (C'est-à-dire, pouvez-vous même nous assurer que l'intensité est uniforme?) Qu'en est-il du deuxième moment? Celles-ci constituent généralement l’information minimale nécessaire pour utiliser efficacement les séquences à des fins d’inférence.
whuber
2
D'accord, mais dans l'exemple de la question, il veut placer un trésor sur une carte dans un jeu. Cela n'impliquera pas d'inférence ou de moments ou quoi que ce soit de la sorte. J'admets que ma méthode ne conviendrait pas pour beaucoup de choses, mais je pense qu'elle correspond à l'exemple. Bien sûr, l'exemple n'est peut-être pas ce qu'il veut ... Peut-être qu'il veut quelque chose de plus formel, auquel cas toutes les autres réponses devraient être examinées.
Peter Flom - Rétablir Monica
3

Ce processus est connu sous le nom de processus «noyau dur» de poisson - ainsi nommé par Brian Ripley dans les années 1970; vous voulez que ce soit aléatoire, mais vous ne voulez pas que les points soient trop proches les uns des autres. Le "noyau dur" peut être imaginé comme une zone tampon autour de laquelle d'autres points ne peuvent pas s'immiscer.

Imaginez que vous enregistrez la position de certaines voitures dans une ville - mais que vous enregistrez uniquement le point situé au centre nominal de la voiture. Alors qu'ils sont dans la rue, il est impossible de rapprocher deux paires car les points sont protégés par le "noyau dur" de la carrosserie - nous ignorerons la super-position potentielle dans les parkings à plusieurs étages :-)

Il existe des procédures pour générer de tels processus ponctuels - une façon consiste simplement à générer des points uniformément, puis à supprimer ceux qui sont trop rapprochés!

Pour plus de détails sur ces processus, reportez-vous à cet exemple.

Sean
la source
2

En ce qui concerne la génération de lots à l'avance, je générerais un grand nombre d'ensembles de variables pseudo-aléatoires, puis les tester avec un test tel que le test de Kolmogorov-Smirnov. Vous voudrez sélectionner le jeu qui a la plus haute valeur de p (ie, est idéal). Notez que cela sera lent, mais que devient plus grand, il devient probablement moins nécessaire. p1N

En ce qui concerne la génération incrémentale, vous recherchez essentiellement une série avec une autocorrélation modérément négative. Je ne sais pas quelle serait la meilleure façon de le faire, car mon expérience des séries chronologiques est très limitée, mais je soupçonne qu'il existe des algorithmes pour cela.

En ce qui concerne un test "trop ​​pair", tout test visant à déterminer si un échantillon suit une distribution spécifique (telle que la KS indiquée ci-dessus) suffit. Vous souhaitez simplement vérifier si , plutôt que le approche standard. J'ai écrit sur un exemple de cette approche alternative ici: le chi-carré est toujours un test à sens unique . p>(1α)

gung - Rétablir Monica
la source
1

Je voudrais formaliser votre problème de la manière suivante: vous voulez une distribution sur telle que la densité soit pour un certain quantifiant la répulsion des points.[0,1]nf(x)e(1kij|xixj|k)1kk<0

Un moyen simple de générer de tels vecteurs consiste à effectuer un échantillonnage de Gibbs.

Neil G
la source
Pouvez-vous élaborer sur ce sujet? L'échantillonnage de Gibbs ne semble pas aider ici, car distribution conditionnelle = distribution marginale = uniforme? Ou bien suggérez-vous d’utiliser les échantillons précédents pour créer des "trous" dans la distribution à partir desquels échantillonner?
Anony-Mousse
Choisissez un vecteur aléatoire uniforme, puis choisissez de manière répétée et uniforme un index et rééchantillonnez . Calculez le rapport de avant et après le ré-échantillonnage et rejetez votre ré-échantillonnage avec la cote . C'est beaucoup plus rapide que les autres réponses que vous avez obtenues lorsque vous avez un très long vecteur car vous effectuez des rejets locaux plutôt que globaux. ixirf(x)r
Neil G