La meilleure méthode pour transformer une séquence à faible écart en distribution normale?

9

J'utilise des séquences à faible écart depuis un certain temps pour les distributions uniformes, car j'ai trouvé leurs propriétés utiles (principalement en infographie pour leur apparence aléatoire et leur capacité à couvrir densément [0,1] de manière incrémentielle).

Par exemple, des valeurs aléatoires ci-dessus, des valeurs de séquence Halton ci-dessous:

J'envisageais de les utiliser pour une planification d'analyse financière, mais j'ai besoin de distributions différentes de celles d'uniforme. J'ai commencé à essayer de générer une distribution normale à partir de mes distributions uniformes via l'algorithme polaire de Marsaglia, mais les résultats ne semblent pas aussi bons qu'avec la distribution uniforme.

Un autre exemple, encore aléatoire au-dessus, Halton ci-dessous:

Ma question est la suivante: quelle est la meilleure méthode pour obtenir une distribution normale avec les propriétés que j'obtiens d'une séquence uniforme à faible écart - couverture, remplissage incrémentiel, non-corrélation sur plusieurs dimensions? Suis-je sur la bonne voie, ou devrais-je adopter une approche complètement différente?

(Code Python pour les distributions uniformes et normales que j'utilise ci-dessus: Gist 2566569 )

normal-distribution random-generation Edouard Poor
la source

3

Vous avez sûrement examiné la réponse naturelle et évidente, qui consiste à appliquer la transformation de probabilité aux valeurs uniformes. À quel (s) égard (s) cette approche ne répond-elle pas à vos besoins?

whuber

C'est ce que j'avais supposé être la façon normale de créer de telles distributions à partir d'une entrée uniforme, mais j'ai eu du mal à trouver de tels algorithmes (je suis un programmeur, pas un statisticien, donc je partais de zéro dans ma recherche). Les méthodes que j'avais trouvées étaient Box Muller, Marsaglia Polar, Ziggarat et Ratio of Uniforms, qui nécessitent toutes de mélanger plus d'un échantillon d'entrée qui semble détruire les caractéristiques que j'essayais de préserver dans les séquences à faible écart. Je viens de trouver la page suivante: home.online.no/~pjacklam/notes/invnorm qui m'a donné les informations que je veux.

Edouard Poor

3

Oui, ce site implémente la transformation de probabilité pour la distribution normale. Vous avez peut-être eu du mal à rechercher cela, car il est si bien connu que pratiquement toute autre méthode de génération de valeurs aléatoires suppose implicitement que vous pouvez utiliser cette méthode, puis recherche des moyens plus efficaces dans des cas spéciaux (y compris les quatre méthodes que vous énumérez).

whuber

3

L'inversion sera la seule méthode valable dans ce cas!

kjetil b halvorsen

Je me demande si nous pouvons également obtenir d'autres valeurs quasi-aléatoires de distribution, par exemple la valeur quasi-aléatoire de distribution bêta?

user315648

5

Vous pouvez transformer des variables aléatoires en toute autre distribution en utilisant l'inverse du CDF, également appelé fonction de point de pourcentage. Il est implémenté dans as scipy.stats.norm.ppf . $\mathcal U(0, 1)$ scipy

Brian Z
la source

6

J'ai récemment trébuché sur ce problème. Naïvement, je pensais que toute transformation de l'uniforme fonctionnerait, alors j'ai branché une séquence 1D Sobol (et Halton) comme si la séquence où un générateur de nombres aléatoires dans une std::normal_distribution<>variable. À ma grande surprise, cela n'a pas fonctionné, il a évidemment généré une distribution non normale.

Ok, alors j'ai pris la fonction Numérique Recettes Troisième Edition Chapitre 7.3.9 Normal_devpour générer des nombres normaux à partir des séquences de Sobol ou Halton par la méthode de "Ratio-d'uniformes" et cela a échoué de la même manière. Ensuite, je pense, ok, si vous regardez le code, il faut deux nombres aléatoires uniformes pour générer deux nombres aléatoires normalement distribués. Peut-être que si j'utilisais une séquence 2D Sobol (ou Halton), cela fonctionnerait. Eh bien, cela a encore échoué.

Je me suis souvenu de la "méthode Box-Muller" (mentionnée dans les commentaires) et comme elle a une interprétation plus géométrique, j'ai pensé que cela pouvait fonctionner. Eh bien, cela a fonctionné! J'étais très excité de commencer à faire d'autres tests, la distribution semble normale.

Le problème que j'ai vu était que la distribution n'était pas meilleure qu'aléatoire, c'est-à-dire en termes de remplissage, donc j'étais un peu déçu, mais prêt à publier le résultat.

Ensuite, j'ai fait une recherche plus approfondie (maintenant que je savais quoi chercher), et il s'est avéré qu'il y avait déjà un article sur ce sujet: http://www.sciencedirect.com/science/article/pii/S0895717710005935

Dans cet article, il est en fait affirmé

Deux méthodes bien connues utilisées avec des nombres pseudo-aléatoires sont le Box-Muller et les méthodes de transformation inverse. Certains chercheurs et ingénieurs financiers ont prétendu qu'il était incorrect d'utiliser la méthode de Box-Muller avec des séquences à faible écart, et que la méthode de transformation inverse devrait plutôt être utilisée. Dans cet article, nous prouvons que la méthode de Box – Muller peut être utilisée avec des séquences à faible écart et discutons du moment où son utilisation pourrait être avantageuse.

La conclusion générale est donc la suivante:

1) Vous pouvez utiliser le Box-Muller sur des séquences 2D à faible discordance pour obtenir des séquences distribuées normalement. Mais mes quelques expériences semblent montrer que la faible différence / espace, par exemple les propriétés de remplissage, est perdue dans la séquence transformée normale.

2) Vous pouvez utiliser la méthode inverse, sans doute les propriétés de faible écart / remplissage d'espace seront préservées.

3) Le rapport d'uniformes ne peut pas être utilisé.

EDIT : Ce https://mathoverflow.net/a/144234 pointe vers les mêmes conclusions.

J'ai fait une illustration (la première figure (Ratio d'uniformes sur Sobol) montre que la distribution obtenue n'est pas normale mais les ohters (Box-Muller et aléatoire pour comparaison) le sont):

EDIT2:

Le point principal est que, même si vous trouvez une méthode qui peut transformer la "distribution" d'une séquence à faible écart, il n'est pas évident que vous conserverez les bonnes propriétés de remplissage. Vous n'êtes donc pas meilleur qu'avec une distribution normale vraiment aléatoire (standard). Je n'ai pas encore trouvé de méthode à faible divergence et pourtant elle se remplit bien avec une distribution non uniforme. Je parie qu'une telle méthode n'est pas évidente et peut-être un problème ouvert.

alfC
la source

Dans l'article mentionné ci-dessus ( sciencedirect.com/science/article/pii/S0895717710005935 ), la dernière phrase se lit comme suit: "Sur la base de ces résultats, nous concluons que Box-Muller est une bonne alternative à la méthode de transformation inverse pour générer des séquences à faible écart de la distribution normale. " Cela ne contredit-il pas le point 1 des conclusions énoncées?

ngiann

@ngiann, pas contradictoire. Le papier arrive à ma même conclusion que la distribution est correctement obtenue par la transformation BM mais pas par les autres méthodes. La deuxième partie de la phrase ("Mais les propriétés de faible écart / remplissage d'espace semblent être perdues.") Est liée à une propriété secondaire que l'on recherche dans les séquences à faible écart, comme le remplissage efficace de l'espace. Mon expérience n'a pas montré que cette propriété se traduisait par la séquence transformée normale. Si je me souviens bien, le document n'entre pas dans ce problème spécifique. Je pense que cela nécessite plus d'études pour être concluant.

alfC

1

Il existe deux bonnes méthodes. Tout d'abord, comme indiqué ci-dessus, une approximation précise de l'inverse de la distribution gaussienne peut être utilisée. Ensuite, on peut transformer n'importe quelle séquence à faible écart en gaussienne.

La deuxième méthode est le Box-Muller. Cette méthode nécessite deux numéros d'entrée (R et A) et génère deux sorties. Une séquence bidimensionnelle à faible écart est nécessaire. On prend (par exemple dans la séquence de Halton), des paires de nombres premiers sont utilisées, une pour la composante radiale (R) et une pour la composante angulaire (A). On obtient Sqrt (-2 * Log (R)) pour la composante radiale et Sin (2 * Pi * A) et Cos (2 * Pi * A) pour les composantes angulaires. La multiplication de la radiale par les deux composantes angulaires (séparément) donne deux Gaussiennes. L'efficacité est la même que ci-dessus; deux entrées quasi-aléatoires et deux sorties gaussiennes.

Toute séquence multidimensionnelle à faible écart peut être utilisée, selon la dimensionnalité du problème.

ttw
la source

0

La méthode la plus native serait en effet d'utiliser le CDF inverse pour se transformer en gaussien normal, mais il y a aussi un problème avec cela. Si vous avez par exemple un ensemble de points LDS créé par des réseaux de rang 1, alors ce serait que le point de départ est toujours (0,0), donc pour le transformer, vous avez besoin d'un petit décalage, mieux pour avoir le même écart que pour le coin (1,1).

Jusqu'à présent, aucun problème, mais pour une distribution gaussienne idéale, N (0,1) + N (0,1) devrait donner la même distribution que la différence. Cependant, ce ne serait pas le cas en utilisant LDS de réseau de rang 1 et iCDF sur chaque variable, car le point de départ dans chaque variable donnerait un certain iCDF, comme $-3\sigma$ (en fonction de N), la différence serait donc $-6\sigma$ .

Et c'est une valeur trop extrême, menant vraiment à une erreur systématique (par exemple, vous n'obtiendrez pas $+6\sigma$ de l'autre côté). Inspectez mieux votre LDS transformé également pour la somme et les différences, vérifiez ces points extrêmes ainsi que l'inclinaison et le kurtosis.

Stephan
la source

La meilleure méthode pour transformer une séquence à faible écart en distribution normale?

Réponses: