2.5 Générateurs pour les lois usuelles

2.5.1 Loi exponentielle

Une variable distribuée selon la loi exponentielle admet . Sa moyenne et son écart-type sont alors tous deux égaux à . Bornons nous au cas et utilisons la fonction de répartition inverse. Avec les notations du § 2.3.2, on a et donc . Il est clair que est uniformément distribué dans dès que l'est. Lorsque ), on aboutit à l'algorithme 28.

2.5.2 Loi normale, méthode des quotients

Considérons maintenant une variable aléatoire distribuée selon la loi normale réduite, c'est à dire ayant pour densité de probabilité la fameuse "courbe en cloche" de la figure 2.9(a). On sait que avec et .

Figure 2.9: loi normale : densité et zone des quotients.

[Densité.][Zone des quotients.]

Considérons, comme au §  2.3.4, la région du plan définie par les conditions et , c'est à dire par et . L'équation polaire de sa frontière est , d'où la figure 2.9(b).

Un peu de calcul montre que la zone des quotients est inscrite dans le rectangle défini par et . On peut alors sélectionner un couple uniformément réparti dans la zone des quotients en sélectionnant un couple uniformément réparti dans le rectangle puis en rejetant ce qui déborde. On obtient l'algorithme 29.

Pour cet algorithme, le facteur de tir est , soit : il y a donc environ appels au générateur uniforme par instanciation fournie. L'efficacité du générateur dépend donc principalement de l'efficacité du calcul des logarithmes sur l'ordinateur considéré. Il est égalament clair que l'on a intérêt à générer les instanciations par lots, de façon à "amortir" les calculs préliminaires de .

2.5.3 Loi normale, algorithme polaire

On obtient une autre méthode de simulation de la loi normale en passant en coordonnées polaires. L'idée utilisée est exactement la même que celle classiquement utilisée pour le calcul de l'intégrale de Gauss . Considérons en effet et deux variables indépendantes, de même loi normale réduite. La densité de probabilité du couple est . La densité de probabilité du couple est donc soit , montrant que les variables et sont indépendantes, la première étant distribuée selon une loi exponentielle, et la seconde selon une loi uniforme.

Il suffit donc d'instancier selon l'algorithme 28, et d'instancier uniformément dans pour obtenir un couple de variables indépendantes et distribuées selon la loi normale, c'est à dire deux instanciations de la variable . D'où l'algorithme 30.

Cet algorithme possède un meilleur facteur de tir que l'algorithme précédent, puisqu'il utilise exactement une fois le générateur uniforme par valeur générée et non pas fois. Mais il nécessite quatre appels de fonctions usuelles (log, racine, sin, cos) au lieu d'un. On est donc dans le cas de deux algorithmes ayant la même complexité, la comparaison dépendant alors des détails de l'implémentation : il ne reste plus qu'à expérimenter les deux possibilités dans chaque environnement de travail.

2.5.4 A propos de la loi gamma

On dit qu'une variable suit une loi gamma de paramètre lorsque les chances de survenue d'une valeur particulière sont proportionnelles à . Les propriétés statistiques d'une telle variable sont étroitement liées aux propriétés de la fonction Gamma d'Euler, définie par . Il est bien connu que cette fonction généralise la factorielle, c'est à dire que : . Par contre, la formule :

est moins connue, et nous allons en rappeler la démonstration. On part de , c'est à dire de :

et l'on procède au changement de variable . Le déterminant jacobien de cette transformation est . On a donc

et on voit que les variables se séparent, conduisant à la formule voulue.

En désignant par la distribution de probabilité de la loi gamma, l'exigence d'avoir une masse totale égle à conduit à . On en déduit , puisque et . La figure 2.10 donne l'allure de la fonction de densité pour et .

Figure 2.10: Densité de probabilité de la loi gamma.

[Le cas .][Le cas .]

L'un des intérêts de cette distribution est que la somme de deux variables aléatoires indépendantes de loi gamma est distribuée à son tour selon une loi gamma, le paramètre étant la somme des paramètres. On a en effet :

En réutilisant l'algorithme 28 (), on en déduit immédiatement l'algorithme 31, mais celui-ci n'est valable que pour des valeurs entières du paramètre. Pour les autres valeurs, la figure 2.10 montre qu'il faut étudier séparément le cas , où la densité de probabilité n'est pas bornée, et le cas où cette densité reste bornée (avec un maximum pour ).

Une remarque de programmation : le code procède effectivement au produit de instanciations successives du générateur uniforme , et non pas au calcul de !

2.5.5 Loi gamma

Pour pouvoir mettre en oeuvre un algorithme de tir, il faut passer par un changement de variable transformant à la fois l'ensemble de définition de , c'est à dire , et l'ensemble des valeurs de , c'est à dire encore en deux intervalles bornés. A cet effet, utilisons en premier lieu qui transforme en et qui fait passer de à , montrant que la densité de probabilité de la nouvelle variable est bornée. En second lieu, utilisons . Pour que les deux segments-images soient adjacents, on impose soit . La probabilité se réécrit alors , montrant que la densité de probabilité est bien restée bornée.

On constate que le choix est particulièrement intéressant. D'une part cette valeur est négative, assurant , c'est à dire le fait que les deux segments sont adjacents et non pas superposés. D'autre part, ce choix fait apparaître le même facteur dans les deux expressions, ce qui va permettre de n'en pas tenir compte : il suffira de considérer que les chances de sélection sont respectivement proportionnelles à et à , quantité qui sont toutes deux bornées par (sur les intervalles correspondants). On aboutit à l'algorithme 32.

Figure 2.11: Loi gamma : m'ethode de tir pour (Ahrens, 1974).

[Le cas .][Facteur de tir pour .]

La figure 2.11(a) donne le graphe de sélection correspondant à et la figure 2.11(b) donne le graphe du facteur de tir en fonction du paramètre . On constate que ce facteur ne dépasse jamais . La figure 2.10 (gauche) a été avec obtenue en engendrant valeurs de du générateur, occasionnant appels du générateur uniforme et aboutissant à un score de .

2.5.6 Loi gamma

Lorsque , on peut utiliser l'algorithme précédent pour instancier une gamma-variable , de paramètre , puis utiliser l'algorithme 31 pour instancier une gamma-variable , de paramètre : la variable aura la distribution voulue. Il est clair que les performances de cet algorithme se dégradent lorsque dépasse quelques unités. Un nouvel algorithme devient nécessaire (également Ahrens, 1974).

Le principe de cet algorithme est le suivant : on part d'une variable uniforme , que l'on transforme par puis , et on accepte ou rejette selon la méthode de tir appropriée. Il est clair que n'est pas acceptable, ce qui impose de rejeter immédiatement tous les avec . Il est clair que l'on obtient un algorithme équivalent en engendrant uniformément et en posant alors .

Il est clair que les obtenus par ont été sélectionnés proportionnellement à et non pas proportionnellement à . Il convient donc d'accepter ou de rejeter les valeurs selon que le verdict rendu par une variable uniforme est inférieur ou supérieur au quotient , en désignant par la quantité et par la valeur maximale de (le fait que soit borné étant évident).

Soit le nombre tel que . L'équation conduit à

et il nous reste à choisir les coefficients et de façon à avoir un bon facteur de tir (et des calculs suffisamment simples). Le fait que soit maximal pour suggère de faire en sorte que soit une racine du polynôme , conduisant à . Pour que l'on ait effectivement , une méthode simple est que n'ait pas d'autres racines réelles. Mais on risque alors d'avoir un graphe "en accent circonflexe", donnant un mauvais facteur de tir. Un compromis est alors que l'autre racine soit une racine double, conduisant à un point d'inflexion à tangente horizontale.

On aboutit à (l'abscisse du méplat étant ). Un examen attentif des calculs montre que le choix est également possible, conduisant à un méplat en et un maximum en . On obtient alors un facteur de tir (légèrement) meilleur pour les grandes valeurs de .

Figure 2.12: Loi gamma : m'ethode de tir pour (Ahrens, 1974).

[Le cas .][Facteur de tir pour .]

La figure 2.12(a) donne le graphe de sélection pour et la figure 2.12(b) donne le facteur de tir en fonction du paramètre. On constate que ce facteur est compris entre (pour ) et (pour ) et est inférieur à pour . La figure 2.10(b) a été avec obtenue en engendrant valeurs, occasionnant appels du générateur uniforme et aboutissant à un score de .

On remarquera que l'algorithme a été programmé de façon à donner directement une liste de valeurs, de façon à "mettre en facteur" les calculs auxiliaires (comme celui de ).