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é en 1974 par A. J. Walker.

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

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 3e et 5e alvéoles ont un alias.

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

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

L'étape de prétraitement, autrement dit, le calcul de $prob$ et $alias$ à 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 :

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

Prétraitement

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

• les cases trop pleines avec $prob[i]>1$
• les cases non pleines avec $prob[i]<1$ et $alias[i]$ non défini
• les cases parfaites avec $prob[i]=1$ ou alors ($prob[i]<1$ et $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 $i$ trop pleine, ainsi qu'une case d'indice $j$ non pleine
2. faire l'assignation $alias[j]:=i$ afin de compléter l'espace libre de la case $j$
3. 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$ :$prob[i]=prob[i]-(1-prob[j])=prob[i]+prob[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

Une répartition non optimale où 3 éléments (le 1er, le 3e et le 5e) 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 3e élément (alias qui est 2) et pour le 5 élément (alias qui 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^{[source insuffisante]}. Mais on peut utiliser un algorithme glouton : voler aux plus riches pour donner aux plus pauvres. Autrement dit, on choisit $i$ avec $prob[i]$ maximal et $j$ avec $prob[j]$ minimal. Cela demande de trier un tableau et on montre que l'on peut implémenter le prétraitement en $O(n\log n)$.