Méthode de Box-Muller
Un article de Wikipédia, l'encyclopédie libre.
La méthode de Box-Muller (George Edward Pelham Box et Mervin Edgar Muller, 1958) consiste à générer des paires de nombres aléatoires à distribution normale centrée réduite, à partir d'une source de nombres aléatoires de loi uniforme.
La transformation prend communément deux formes.
- La forme simple transforme des coordonnées cartésiennes uniformément distribuées dans le cercle unité en des coordonnées normalement distribuées.
- La forme polaire transforme des coordonnées polaires uniformément distribuées en des coordonnées cartésiennes normalement distribuées.
On peut également utiliser la méthode de la transformée inverse pour générer des nombres normalement distribués; la méthode de Box-Muller a été mise au point pour être algorithmiquement plus efficiente[1]. On peut également envisager la Méthode Ziggourat qui est aussi très efficiente.
Sommaire |
[modifier] Forme cartésienne
Soient x et y choisis indépendamment et uniformément dans [−1,1], et s = x2 + y2. Si s > 1, rejetons-le et choisissons à nouveau un couple (x, y), jusqu'à ce que s appartienne à ]0,1]. Pour ces points "filtrés", calculons ensuite:
et
[modifier] Forme polaire
Soient U1 et U2 deux variables aléatoires indépendantes uniformément distribuées dans ]0,1].
Soient
et
Alors Z0 et Z1 sont des variables aléatoires indépendantes suivant une loi normale de variance 1.
Cette transformation [2] vient du fait que, dans un système cartésien à deux dimensions où les coordonnées X et Y suivent deux variables aléatoires indépendantes normales, les variables aléatoires R2 et Θ (ci-dessus) sont également indépendantes et peuvent s'écrire
et
[modifier] Comparaison entre les deux formes
La forme cartésienne est une méthode d'échantillonnage à rejet[3], qui n'utilise qu'une partie des nombres générés par la source aléatoire, mais elle est en pratique plus rapide que la forme polaire car elle est plus simple à calculer:
- la forme cartésienne n'utilise pas de fonctions trigonométriques, coûteuses en temps de calcul
- la génération de nombres aléatoires est plutôt rapide, il n'est donc pas gênant d'en gaspiller une partie. En moyenne la part de points rejetés est (1-π/4) ≈ 21.46%. On génère donc 4/π ≈ 1.2732 nombres aléatoires uniformes pour obtenir chaque nombre aléatoire normal.
[modifier] Notes
- ↑ Kloeden and Platen, Numerical Solutions of Stochastic Differential Equations, p. 11-12
- ↑ Sheldon Ross, A First Course in Probability, (2002), p.279-81
- ↑ (en) rejection sampling