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 ${\displaystyle X}$ et la distribution de probabilité que ${\displaystyle X}$ vaille ${\displaystyle i}$ est ${\displaystyle p_{i}}$ pour tout entier ${\displaystyle i=1\dots n}$. On souhaite simuler la variable ${\displaystyle 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 ${\displaystyle O(n)}$. Il peut être optimisé en ${\displaystyle O(\log n)}$ à l'aide d'un arbre binaire de recherche. La méthode des alias, elle, donne une simulation en temps constant ${\displaystyle O(1)}$.

Idée générale

Idée générale du prétraitement. On répartit la distribution de probabilités. Ici, nous avons une distribution non uniforme sur 5 éléments que l'on répartit uniformément. Chaque alvéole contient in fine 1 ou 2 éléments. Ici, à la fin, la 3^e et 5^e alvéoles ont un alias.

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

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

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

Un diagramme qui représente la structure de données sous-jacente pour la distribution〈0.25, 0.3, 0.1, 0.2, 0.15〉.

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 ${\displaystyle i=1,2,3,4,5}$. Nous avons deux tableaux ${\displaystyle prob}$ et ${\displaystyle alias}$ : ${\displaystyle prob[i]}$est une valeur de seuil et ${\displaystyle alias[i]}$ est l'alias de ${\displaystyle i}$.

La figure de droite montre une telle structure. On a ${\displaystyle prob=[1,1,0.5,1,0.75]}$ et ${\displaystyle alias=[undefined,undefined,2,undefined,1]}$.

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

1. On génère un nombre réel ${\displaystyle U}$ de manière uniforme entre 1 et ${\displaystyle n}$
2. On considère l'alvéole numéro ${\displaystyle i:=\lfloor U\rfloor }$
3. Dans cette alvéole, on regarde la valeur de ${\displaystyle U-i}$.
4. Si cette valeur est inférieure au seuil ${\displaystyle prob[i]}$ alors on renvoie ${\displaystyle i}$, sinon on renvoie ${\displaystyle alias[i]}$.

Prétraitement

Dans cette section, on décrit comment construire les tableaux ${\displaystyle prob}$ et ${\displaystyle alias}$. On commence avec ${\displaystyle prob[i]=np_{i}}$pour tout ${\displaystyle i=1\dots n}$ et ${\displaystyle alias}$ un tableau vide de ${\displaystyle n}$ cases de valeur indéfinie. On distingue trois types de cases :

• les cases trop pleines avec ${\displaystyle prob[i]>1}$
• les cases non pleines avec ${\displaystyle prob[i]<1}$ et ${\displaystyle alias[i]}$ non défini
• les cases parfaites avec ${\displaystyle prob[i]=1}$ ou alors (${\displaystyle prob[i]<1}$ et ${\displaystyle alias[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 :

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

A la fin de l'itération, la case ${\displaystyle j}$ devient parfaite. La case ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle O(n)}$.

Optimisation

Une répartition non optimale où 3 éléments (le 1^er, le 3^e et le 5^e) finissent par avoir un alias.

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 ${\displaystyle i}$ et ${\displaystyle 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 ${\displaystyle i}$ avec ${\displaystyle prob[i]}$ maximal et ${\displaystyle j}$ avec ${\displaystyle prob[j]}$ minimal. Cela demande de trier un tableau et on montre que l'on peut implémenter le prétraitement de complexité temporelle ${\displaystyle O(n\log n)}$, en utilisant un algorithme d'équilibrage d'arbre binaire au moyen d'un tableau annexe d'indexation de taille ${\displaystyle 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