- Box-Muller
-
Méthode de Box-Muller
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
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
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
Comparaison entre les deux formes
La forme cartésienne est une méthode d'échantillonnage à rejet, 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.
Notes
Catégorie : Nombre aléatoire
Wikimedia Foundation. 2010.