Methode Ziggourat

Methode Ziggourat

Méthode Ziggourat

La méthode Ziggourat est un algorithme pour engendrer des nombres aléatoires de loi non uniformes. Il s'agit d'une méthode de rejet et pour être choisie pour simuler une variable aléatoire ayant une densité strictement monotone. Cette méthode peut aussi être appliquée à des lois symétriques unimodales telles que la loi normale en choisissant un point sur l'une des moitiés et en choisissant le côté aléatoirement. Cette méthode a été développée par George Marsaglia et Wai Wan Tang.

Comme la plupart des algorithmes de ce type, il suppose que l'on dispose d'un générateur de nombres aléatoires de loi uniforme, en général un générateur pseudo-aléatoire. Dans la plupart des cas, comme la loi normale ou la loi exponentielle, l'algoritme consiste à engendrer un nombre flottant, un index aléatoire de table, faire une recherche dans une table, une multiplication et une comparaison. Cet algorithme est considérablement plus rapide que les autres méthodes pour simuler des variables aléatoires de loi normale, comme la méthode de Box-Muller qui requierent de calculer une racine carrée ou un logarithme. D'un autre côté, cette méthode est plus complexe à implémenter et nécessite des tables précalculées, de sorte qu'il vaut mieux l'utiliser lorsque l'on a besoin de nombres aléatoires en grande quantité.

Le nom de cette méthode provient du fait qu'elle couvre la densité de la loi avec des segments rectangulaires empilés par ordre de taille décroissant, ce qui ressemble donc à une ziggourat.

Sommaire

Théorie

La méthode Ziggourat est une méthode de rejet. La position d'un point est engendrée aléatoirement à l'intérieur d'une courbe délimitant une surface légèrement plus grande que celle délimitée par la densité de la loi considérée. On teste alors si ce point se trouve dans cette dernière surface. Si c'est le cas, on retourne l'abscisse du point. Sinon, on rejette ce point et on en tire un nouveau.

Pour construire la surface qui recouvre la densité, on choisit une surface composée de n régions de tailles égales, dont n − 1 sont des rectangles empilés au dessus d'une région non rectangulaire qui couvre la queue de la densité de la loi.

Si f est la densité de la loi à simuler, la base de la ziggourat se compose donc d'un rectangle allant dont le coin inférieur gauche a pour coordonnées (0,0) et le coin supérieur à pour coordonnées (x0,f(x0)), et de l'ensemble des points situés sous la courbe (x,f(x)) pour x\geq x_0. Cette couche délimite une région d'aire A. On place au dessus une région rectangulaire dont le coin inférieur gauche est (0,x0) et le coin supérieur droit (x1,f(x0)), où x1 est pour que l'aire de ce rectangle soit égale à A. On construit de même un rectangle de coordonnées définies par (0,x1) et (x2,f(x1)) d'aire A On construit ainsi une suite de points x_0,x_1,\ldots,x_n pour un nombre n de couches donné à l'avance (typiquement, n − 256). Les coordonnées des points x_0,x_1,\ldots,x_n dépendent de n.

En ignorant pour l'instant le problème de la première couche qui n'est pas rectangulaire, l'algorithme est le suivant :

  1. On choisit aléatoirement de façon une couche i avec une probabilité 1 / n.
  2. Si i = 0, on utilise alors un algorithme spécifique (voir plus bas)
  3. On se donne une réalisation U0 d'une variable aléatoire uniforme sur [0,1[
  4. On pose xU0xi − 1
  5. Si x\leq x_i, alors on retourne x
  6. Sinon on se donne une réalisation U1 d'une variable aléatoire uniforme sur [0,1[
  7. On calcule y = yi − 1 + U1(yiyi − 1) avec yj = f(xj)
  8. Si f(x) > y, on retourne x
  9. Sinon, on recommence l'algorithme depuis le début.

Pour une loi dont la densité est symétrique, il suffit juste de tester si |x|\leq x_i en utilisant pour U0 une variable aléatoire uniforme sur ] − 1,1[.

Algorithmes pour la queue de la densité

Lorsque la densité à un support non compact (comme c'est la cas pour la loi normale, la loi exponentielle, ...), il est alors nécessaire d'utiliser un algorithme spécifique lorsque la première tranche est sélectionnée. Cet algorithme dépend de la loi.

La première couche peut se diviser en une région centrale rectangulaire, et une région avec une queue infinie. On peut utiliser le même algorithme en ajoutant un point fictif x − 1 = A / y0 et en tirant un point x = U0x − 1U0 une réalisation U0 d'une variable aléatoire uniforme sur [0,1[. Si x\leq x_0, on retourne x. Sinon, on a besoin de tirer une réalisation de cette variable aléatoire sachant qu'elle est plus grande que la valeur x0. Pour la loi exponentielle de paramètre λ, cela se fait très facilement par x = x0 − ln(U)U est la réalisation d'une variable aléatoire uniforme sur [0,1[.

Une autre possibilité consiste à appeler l'algorithme Ziggourat de façon récursive sur la queue de la densité.

Pour la loi normale, G. Marsaglia propose la méthode suivante :

  1. On calcule x = − ln(U1) / x0U1 est la réalisation d'une variable aléatoire uniforme sur [0,1[.
  2. Let y = − ln(U2)U2 est la réalisation d'une variable aléatoire uniforme sur [0,1[.
  3. Si 2y > x2 alors on retourne x + x0,
  4. Sinon, on revient au premier pas.

Comme pour une taille de table typique (n=128), x_0\approx 3.5, le test du pas no 3 est presque toujours vérifié. Puisque − ln(Ui) renvoie une réalisation d'une variable aléatoire exponentielle, si l'on dispose d'une méthode Ziggourat pour l'exponentielle, on peut l'utiliser à cette fin.

Optimisations

L'algorithme peut tourner de façon efficace en utilisant des tables précalculées pour les xi et les yi, mais il existe des astuces pour le rendre encore plus rapide. La principale idée est que rien ne requiert que l'on utilise pour f une fonction d'aire 1. On peut donc utiliser cet algorithme sur des densités non normalisées, ce qui accélère le calcul de f(x) (par exemple, pour la loi normale, on peut utiliser f(x) = exp( − x2 / 2) au lieu de f(x)=\exp(x^2/2)/\sqrt{2\pi}).

Comment engendrer les tables ?

Il est possible de stocker dans l'algorithme la table entière des points xi et f(xi), ou bien juste les valeurs n, A et x0 et de calculer les autres valeurs juste durant la phase d'initialisation des calculs.

Comment trouver x0 et A ?

Étant donné un nombre de niveau n, on a besoin de trouver la valeur de x0 et de A telles que x_0\times f(x_0)+\int_{x_0}^{+\infty} f(t)\mathrm{d}t=A et x_{n-1}\times (f(0)-f(x_{n-1}))=A. Pour la loi exponentielle de paramète λ, on a l'aire \int_{x_0}^{+\infty} f(t)\mathrm{d}t=-\lambda^{-1}\exp(-\lambda x_0). La fonction de répartition de la loi normale est très souvent implémentée dans de nombreuses bibliothèques numériques. Pour d'autres lois, il peut être nécessaire d'utiliser des procédures d'intégration numérique. L'idée est alors d'utiliser un algorithme de recherche de zéro en partant d'une estimation initial de x0 afin de résoudre

x_0\times f(x_0)+\int_{x_0}^{+\infty} f(t)\mathrm{d}t=x_{n-1}\times (f(0)-f(x_{n-1}))

en calculant les xi successivement jusqu'à xn − 1 de sorte que l'aire de chaque tranche soit égale à x_0\times f(x_0)+\int_{x_0}^{+\infty} (t)\mathrm{d}t=A pour une estimation donnée de x0.

Voir aussi

Références

  • (en) George Marsaglia et Wai Wan Tsang, « The Ziggurat Method for Generating Random Variables », dans Journal of Statistical Software, volume 5, no 8, 2000.
  • (en) Jurgen A. Doornik, « An Improved Ziggurat Method to Generate Normal Random Samples », Nuffield College, Oxford [lire en ligne].
  • (en) David B. Thomas, Philip G.W. Leong, Wayne Luk et John D. Villasenor, « Gaussian Random Number Generators », dans ACM Computing Surveys, volume 39, 2007.
Ce document provient de « M%C3%A9thode Ziggourat ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Methode Ziggourat de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Méthode Ziggourat — La méthode Ziggourat est un algorithme pour engendrer des nombres aléatoires de loi non uniforme. Il s agit d une méthode de rejet et peut être choisie pour simuler une variable aléatoire ayant une densité strictement monotone. Cette méthode peut …   Wikipédia en Français

  • Methode de Box-Muller — Méthode de Box Muller Représentation graphique de la transformation : les cercles de départ, répartis uniformément autour de l origine, deviennent un nouvel ensemble de cercles centrés, dont la répartition est proche de l origine puis s… …   Wikipédia en Français

  • Méthode De Box-Muller — Représentation graphique de la transformation : les cercles de départ, répartis uniformément autour de l origine, deviennent un nouvel ensemble de cercles centrés, dont la répartition est proche de l origine puis s étiole rapidement. Les… …   Wikipédia en Français

  • Méthode de box-muller — Représentation graphique de la transformation : les cercles de départ, répartis uniformément autour de l origine, deviennent un nouvel ensemble de cercles centrés, dont la répartition est proche de l origine puis s étiole rapidement. Les… …   Wikipédia en Français

  • Méthode de Box-Muller — Représentation graphique de la transformation : les cercles de départ, répartis uniformément autour de l origine, deviennent un nouvel ensemble de cercles centrés, dont la répartition est proche de l origine puis s étiole rapidement. Les… …   Wikipédia en Français

  • Box-Muller — Méthode de Box Muller Représentation graphique de la transformation : les cercles de départ, répartis uniformément autour de l origine, deviennent un nouvel ensemble de cercles centrés, dont la répartition est proche de l origine puis s… …   Wikipédia en Français

  • Transformation de Box-Muller — Méthode de Box Muller Représentation graphique de la transformation : les cercles de départ, répartis uniformément autour de l origine, deviennent un nouvel ensemble de cercles centrés, dont la répartition est proche de l origine puis s… …   Wikipédia en Français

  • Transformée de Box-Muller — Méthode de Box Muller Représentation graphique de la transformation : les cercles de départ, répartis uniformément autour de l origine, deviennent un nouvel ensemble de cercles centrés, dont la répartition est proche de l origine puis s… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Chogha Zanbil — Chogha Zanbil 1 Patrimoine mondial de l’UNESCO Vue du ziggurat Latitude Longitude …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”