Inverser la technique de Box-Mueller : à partir de chaque paire de normales , deux uniformes indépendants peuvent être construits comme(X,Y) (sur l'intervalle [ - π , π ] ) et exp ( - ( X 2 + Y 2 ) / 2 ) (sur l'intervalle [ 0 , 1 ] ).atan2(Y,X)[−π,π]exp(−(X2+Y2)/2)[0,1]
Prenez les normales par groupes de deux et additionnez leurs carrés pour obtenir une séquence de variées Y 1 , Y 2 , … , Y i , … . Les expressions obtenues à partir des pairesχ22Y1,Y2,…,Yi,…
Xi=Y2iY2i−1+Y2i
aura une distribution , qui est uniforme.Beta(1,1)
Que cela ne nécessite qu'une arithmétique simple et de base devrait être clair.
Étant donné que la distribution exacte du coefficient de corrélation de Pearson d'un échantillon à quatre paires à partir d'une distribution normale bivariée standard est uniformément répartie sur , nous pouvons simplement prendre les normales en groupes de quatre paires (c'est-à-dire, huit valeurs dans chaque ensemble) et renvoyer le coefficient de corrélation de ces paires. (Cela implique une arithmétique simple plus deux opérations de racine carrée.)[−1,1]
Il est connu depuis l'Antiquité qu'une projection cylindrique de la sphère (une surface dans trois espaces) est à aire égale . Cela implique que dans la projection d'une distribution uniforme sur la sphère, la coordonnée horizontale (correspondant à la longitude) et la coordonnée verticale (correspondant à la latitude) auront des distributions uniformes. Comme la distribution normale standard trivariée est sphérique symétrique, sa projection sur la sphère est uniforme. L'obtention de la longitude est essentiellement le même calcul que l'angle dans la méthode Box-Mueller ( qv ), mais la latitude projetée est nouvelle. La projection sur la sphère normalise simplement un triple de coordonnées et à ce point z est la latitude projetée. Ainsi, prenez les variables normales en groupes de trois, X 3 i - 2 , X 3 i - 1 , X 3 i , et calculez(x,y,z)zX3i−2,X3i−1,X3i
X3iX23i−2+X23i−1+X23i−−−−−−−−−−−−−−−−√
pour .i=1,2,3,…
Étant donné que la plupart des systèmes informatiques représentent des nombres en binaire , la génération de nombres uniformes commence généralement par la production d' entiers uniformément répartis entre et 2 32 - 1 (ou une puissance élevée de 2 liée à la longueur des mots de l'ordinateur) et leur redimensionnement selon les besoins. Ces entiers sont représentés en interne sous forme de chaînes de 32 chiffres binaires. Nous pouvons obtenir des bits aléatoires indépendants en comparant une variable normale à sa médiane. Ainsi, il suffit de diviser les variables normales en groupes de taille égale au nombre de bits souhaité, de comparer chacune à sa moyenne et d'assembler les séquences résultantes de résultats vrais / faux en un nombre binaire. Écriture k0232−1232kpour le nombre de bits et pour le signe (c'est-à-dire lorsque et sinon), nous pouvons exprimer la valeur uniforme normalisée résultante dans avec le formuleHx > 0 H ( x ) = 0 [ 0 , 1 )H(x)=1x>0H(x)=0[0,1)
∑j=0k−1H(Xki−j)2−j−1.
Les variables peuvent être tirées de n'importe quelle distribution continue dont la médiane est (comme une normale standard); ils sont traités en groupes de chaque groupe produisant une telle valeur pseudo-uniforme. 0 kXn0k
L'échantillonnage par rejet est un moyen standard, flexible et puissant de tirer des variations aléatoires à partir de distributions arbitraires. Supposons que la distribution cible ait PDF . Une valeur est dessinée selon une autre distribution avec PDF . Dans l'étape de rejet, une valeur uniforme comprise entre et est dessinée indépendamment de et comparée à : si elle est plus petite, est conservée mais sinon le processus est répété. Cette approche semble cependant circulaire: comment générer une variable uniforme avec un processus qui a besoin d'une variable uniforme pour commencer?Y g U 0 g ( Y ) Y f ( Y ) YfYgU0g(Y)Yf(Y)Y
La réponse est que nous n'avons pas réellement besoin d'une variable uniforme pour effectuer l'étape de rejet. Au lieu de cela (en supposant ), nous pouvons lancer une pièce juste pour obtenir un ou au hasard. Cela sera interprété comme le premier bit de la représentation binaire d'une variable uniforme dans l'intervalle . Lorsque le résultat est , cela signifie ; sinon, . La moitié du temps, cela suffit pour décider de l'étape de rejet: si mais la pièce est , doit être accepté; si0 1 U [ 0 , 1 ) 0 0 ≤ U < 1 / 2 1 / 2 ≤ U < 1 f ( Y ) / g ( Y ) ≥ 1 / 2 0 Y f ( Y ) / g ( Y ) < 1 / 2 1 Y U fg(Y)≠001U[0,1)00≤U<1/21/2≤U<1f(Y)/g(Y)≥1/20Yf(Y)/g(Y)<1/2 mais la pièce est , doit être rejeté; sinon, nous avons besoin de retourner la pièce à nouveau afin d'obtenir le bit de . Parce que - quelle que soit la valeur de - il y a chance de s'arrêter après chaque flip, le nombre de flips attendu n'est que de .1YU1 / 2 1 / 2 ( 1 ) + 1 / 4 ( 2 ) + 1 / 8 ( 3 ) + ⋯ + 2 - n ( n ) + ⋯ = 2f(Y)/g(Y)1/21/2(1)+1/4(2)+1/8(3)+⋯+2−n(n)+⋯=2
L'échantillonnage des rejets peut être utile (et efficace) à condition que le nombre attendu de rejets soit faible. Nous pouvons y parvenir en ajustant le plus grand rectangle possible (représentant une distribution uniforme) sous un PDF normal.
En utilisant le calcul pour optimiser la zone du rectangle, vous constaterez que ses extrémités doivent se situer à , où sa hauteur est égale à , ce qui rend sa zone un peu supérieur à . En utilisant cette densité normale standard comme et en rejetant automatiquement toutes les valeurs en dehors de l'intervalle , et en appliquant autrement la procédure de rejet, nous obtiendrons des variations uniformes dans efficacement:exp ( - 1 / 2 ) / √±10,48g[-1,1][-1,1]exp(−1/2)/2π−−√≈0.2419710.48g[−1,1][−1,1]
Dans une fraction fois, la variable normale se situe au-delà de et est immédiatement rejetée. ( est le CDF Normal standard.)[ - 1 , 1 ] Φ2Φ(−1)≈0.317[−1,1]Φ
Dans la fraction restante du temps, la procédure de rejet binaire doit être suivie, nécessitant en moyenne deux autres variations normales.
La procédure globale nécessite en moyenne étapes.1/(2exp(−1/2)/2π−−√)≈2.07
Le nombre attendu de variables normales nécessaires pour produire chaque résultat uniforme correspond à
2eπ−−−√(1−2Φ(−1))≈2.82137.
Bien que cela soit assez efficace, notez que (1) le calcul du PDF normal nécessite le calcul d'une exponentielle et (2) la valeur doit être précalculée une fois pour toutes. C'est encore un peu moins de calcul que la méthode Box-Mueller ( qv ).Φ(−1)
Les statistiques d'ordre d'une distribution uniforme ont des lacunes exponentielles. Puisque la somme des carrés de deux normales (de moyenne nulle) est exponentielle, nous pouvons générer une réalisation de uniformes indépendants en sommant les carrés des paires de ces normales, en calculant la somme cumulée de celles-ci, en redimensionnant les résultats pour qu'ils tombent dans l'intervalle , et en supprimant le dernier (qui sera toujours égal à ). C'est une approche agréable car elle ne nécessite que la quadrature, la sommation et (à la fin) une seule division.[ 0 , 1 ] 1n[0,1]1
Les valeurs seront automatiquement dans l'ordre croissant. Si un tel tri est souhaité, cette méthode est supérieure en calcul à toutes les autres dans la mesure où elle évite le coût d'un tri. Si une séquence d'uniformes indépendants est nécessaire, cependant, le tri aléatoire de ces valeurs fera l'affaire. Puisque (comme on le voit dans la méthode de Box-Mueller, qv ) les ratios de chaque paire de normales sont indépendants de la somme des carrés de chaque paire, nous avons déjà les moyens d'obtenir cette permutation aléatoire: ordonner les sommes cumulées par les ratios correspondants . (Si est très grand, ce processus pourrait être effectué en plus petits groupes deO ( n log ( n ) ) n n k 2 ( k + 1 ) k k O ( n log ( k ) ) O ( n ) 2 n ( 1 + 1 / k ) nnO(nlog(n))nnkavec peu de perte d'efficacité, car chaque groupe n'a besoin que de normales pour créer valeurs uniformes. Pour fixe , le coût de calcul asymptotique est donc = , nécessitant variables normales pour générer valeurs uniformes.)2(k+1)kkO(nlog(k))O(n)2n(1+1/k)n
Pour une superbe approximation, toute variable normale avec un grand écart-type semble uniforme sur des plages de valeurs beaucoup plus petites. En roulant cette distribution dans la plage (en ne prenant que les parties fractionnaires des valeurs), nous obtenons ainsi une distribution qui est uniforme à toutes fins pratiques. Ceci est extrêmement efficace, nécessitant l'une des opérations arithmétiques les plus simples de toutes: arrondissez simplement chaque variable normale à l'entier le plus proche et conservez l'excédent. La simplicité de cette approche devient convaincante lorsque nous examinons une mise en œuvre pratique :[0,1]R
rnorm(n, sd=10) %% 1
produit de manière fiable des n
valeurs uniformes dans l'intervalle au prix de simples variations normales et presque pas de calcul.[0,1]n
(Même lorsque l'écart-type est de , le PDF de cette approximation varie d'un PDF uniforme, comme le montre la figure suivante, de moins d'une partie sur ! Pour le détecter de manière fiable, il faudrait un échantillon de valeurs - c'est déjà au-delà de la capacité de tout test standard d'aléatoire. Avec un écart-type plus grand, la non-uniformité est si petite qu'elle ne peut même pas être calculée. Par exemple, avec un écart-type de comme indiqué dans le code, le maximum l'écart par rapport à un PDF uniforme n'est que de .)10 8 10 16 10 10 - 857110810161010−857
Dans tous les cas, les variables normales "avec des paramètres connus" peuvent facilement être recentrées et redimensionnées dans les normales standard supposées ci-dessus. Ensuite, les valeurs uniformément réparties résultantes peuvent être recentrées et rééchelonnées pour couvrir tout intervalle souhaité. Celles-ci ne nécessitent que des opérations arithmétiques de base.
la source