Méthode des alias

En informatique, la méthode des alias permet de simuler des variables aléatoires à support fini, en temps constant. Elle a été publiée en 1974 par A. J. Walker^[1]^,^[2].

Contexte

On considère une variable aléatoire $X$ et la distribution de probabilité que $X$ vaille $i$ est $p_{i}$ pour tout entier $i = 1 \dots n$ . On souhaite simuler la variable $X$ . Une méthode classique pour la simulation est la méthode de la transformée inverse. Malheureusement, elle se reformule comme un algorithme en $O (n)$ . Il peut être optimisé en $O (\log n)$ à l'aide d'un arbre binaire de recherche. La méthode des alias, elle, donne une simulation en temps constant $O (1)$ .

Idée générale

La méthode commence par un prétraitement en $O (n)$ ou $O (n \log n)$ selon l'algorithme utilisé. L'idée du prétraitement est de répartir la distribution de probabilités dans $n$ alvéoles, une pour chaque élément $i = 1 \dots n$ . Une fois la répartition faite, l'alvéole numéro $i$ , contient soit un unique élément $i$ , soit l'élément initial $i$ ainsi qu'un autre élément, que l'on appelle l'alias, et que l'on note ici $a l i a s [i]$ . En d'autres termes, ce prétraitement construit une structure de données.

Ensuite, on peut générer des valeurs pour $X$ selon la distribution données par les $p_{i}$ en temps constant $O (1)$ de la façon suivante. On tire de manière uniforme un nombre réel entre 1 et $n$ . Ce dernier donne une certaine alvéole $i$ . On renvoie $i$ ou $a l i a s [i]$ selon que l'on dépasse un seuil.

Génération d'un élément

Avant de décrire le prétraitement pour construire la structure de données, décrivons la génération à partir de cette structure. On considère les entiers $i = 1, 2, 3, 4, 5$ . Nous avons deux tableaux $p r o b$ et $a l i a s$ : $p r o b [i]$ est une valeur de seuil et $a l i a s [i]$ est l'alias de $i$ .

La figure de droite montre une telle structure. On a $p r o b = [1, 1, 0.5, 1, 0.75]$ et $a l i a s = [u n d e f i n e d, u n d e f i n e d, 2, u n d e f i n e d, 1]$ .

L'étape de prétraitement, autrement dit, le calcul de $p r o b$ et $a l i a s$ à partir de $p_{1}, \dots, p_{n}$ est donnée dans la section suivante. Décrivons en premier lieu comment simuler une variable aléatoire $X$ . Pour cela, on procède comme suit :

On génère un nombre réel $U$ de manière uniforme entre 1 et $n$
On considère l'alvéole numéro $i := ⌊ U ⌋$
Dans cette alvéole, on regarde la valeur de $U - i$ .
Si cette valeur est inférieure au seuil $p r o b [i]$ alors on renvoie $i$ , sinon on renvoie $a l i a s [i]$ .

Prétraitement

Dans cette section, on décrit comment construire les tableaux $p r o b$ et $a l i a s$ . On commence avec $p r o b [i] = n p_{i}$ pour tout $i = 1 \dots n$ et $a l i a s$ un tableau vide de $n$ cases de valeur indéfinie. On distingue trois types de cases :

les cases trop pleines avec $p r o b [i] > 1$
les cases non pleines avec $p r o b [i] < 1$ et $a l i a s [i]$ non défini
les cases parfaites avec $p r o b [i] = 1$ ou alors ( $p r o b [i] < 1$ et $a l i a s [i]$ défini)

L'algorithme de prétraitement fonctionne comme suit. On exécute les étapes suivantes tant que les cases ne sont pas toutes parfaites :

choisir arbitrairement une case d'indice $i$ trop pleine, ainsi qu'une case d'indice $j$ non pleine
faire l'assignation $a l i a s [j] := i$ afin de compléter l'espace libre de la case $j$
L'idée est que la proportion de $i$ a été déplacée vers la case $j$ en tant qu'alias, il faut corriger la case $i$ : $p r o b [i] = p r o b [i] - (1 - p r o b [j]) = p r o b [i] + p r o b [j] - 1$

A la fin de l'itération, la case $j$ devient parfaite. La case $i$ , elle, qui était trop pleine peut soit rester trop pleine, soit devenir parfaite, soit devenir non pleine. En tout cas, le nombre de cases parfaites croit strictement au cours de l'algorithme. Donc, il y a au plus $n$ itérations des étapes 1, 2, 3. Chaque itération peut être implémentée en temps constant. Donc le prétraitement peut être implémenté en temps $O (n)$ .

Optimisation

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Comme dit précédemment, il n'y a pas unicité de la structure de données. Par exemple, l'animation ci-dessus et la structure données donné en exemple donne un alias pour le 3^e élément (dont l'alias est 2) et pour le 5^e élément (dont l'alias est 1). Nous avons donc deux éléments qui possèdent un alias. Mais il existe d'autres répartitions comme le montre l'animation ci-contre. L'algorithme de prétraitement donné dans la section précédente peut donner plusieurs structures, selon les choix de $i$ et $j$ .

Ainsi, on peut chercher à minimiser le nombre d'éléments possédant un alias. Ainsi, la génération est encore plus rapide (même si c'était déjà en temps constant !) car on évite la comparaison au seuil et la lecture dans la table des alias. Malheureusement, le problème de décision associé à ce problème d'optimisation est NP-difficile^[3]^{[source insuffisante]}.

Mais on peut utiliser un algorithme glouton : voler aux plus riches pour donner aux plus pauvres. Autrement dit, on choisit $i$ avec $p r o b [i]$ maximal et $j$ avec $p r o b [j]$ minimal. Cela demande de trier un tableau et on montre que l'on peut implémenter le prétraitement de complexité temporelle $O (n \log n)$ , en utilisant un algorithme d'équilibrage d'arbre binaire au moyen d'un tableau annexe d'indexation de taille $O (n)$ (algorithme utile également en prétraitement pour la génération des tables de transcodage pour la compression entropique de données avec un codage de Huffman ou arithmétique, selon une loi de distribution prédéterminée ou obtenue depuis un échantillon suffisant de ces données).

Algorithmes

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Voir aussi

Notes et références

↑ A. J. Walker, « New fast method for generating discrete random numbers with arbitrary frequency distributions », Electronics Letters, vol. 10, n^o 8,‎ avril 1974, p. 127 (DOI 10.1049/el:19740097, Bibcode 1974ElL....10..127W)
↑ A. J. Walker, « An Efficient Method for Generating Discrete Random Variables with General Distributions », ACM Transactions on Mathematical Software, vol. 3, n^o 3,‎ septembre 1977, p. 253–256 (DOI 10.1145/355744.355749 , S2CID 4522588)
↑ (en) George Marsaglia, Wai Wan Tsang et Jingbo Wang, « Fast Generation of Discrete Random Variables », Journal of Statistical Software, vol. 11,‎ 12 juillet 2004, p. 1–11 (ISSN 1548-7660, DOI 10.18637/jss.v011.i03, lire en ligne, consulté le 8 mars 2024)

Articles connexes

Portail de l’informatique

Portail des probabilités et de la statistique

[Walker1974-1] A. J. Walker, « New fast method for generating discrete random numbers with arbitrary frequency distributions », Electronics Letters, vol. 10, n^o 8,‎ avril 1974, p. 127 (DOI 10.1049/el:19740097, Bibcode 1974ElL....10..127W)

[Walker1977-2] A. J. Walker, « An Efficient Method for Generating Discrete Random Variables with General Distributions », ACM Transactions on Mathematical Software, vol. 3, n^o 3,‎ septembre 1977, p. 253–256 (DOI 10.1145/355744.355749 , S2CID 4522588)

[3] (en) George Marsaglia, Wai Wan Tsang et Jingbo Wang, « Fast Generation of Discrete Random Variables », Journal of Statistical Software, vol. 11,‎ 12 juillet 2004, p. 1–11 (ISSN 1548-7660, DOI 10.18637/jss.v011.i03, lire en ligne, consulté le 8 mars 2024)

[1]

[2]

[3]