Salut à tous,
En voyant le dernier article sur les tirages aléatoires, ça m’a refait penser à un problème que j’ai plusieurs fois essayé de résoudre sans y arriver: comment récupérer efficacement un nombre non entier de bits d’entropie.
Par exemple, le choix d’un élément parmi 3 de manière uniforme équivaut à $\log_2(3) \approx 1.585$ bits d’entropie (valeur obtenu à partir de la formule de Shannon). Il semble donc logique que 2 bits d’entropie soit suffisant pour faire ce choix. Cependant, la méthode naïve de générer un nombre entre 0 et 3 (inclus) et d’appliquer un modulo 3 ne fonctionne pas puisqu’elle génère un biais: la valeur 0 à une probabilité de 0.5 d’arriver alors que les deux autres ont une probabilité 0.25.
La solution habituelle est de générer un nombre entre 0 et 3 (inclus), de prendre la valeur généré si elle est égale à 0, 1 ou 2 et de recommencer l’opération si elle est égale à 3. En pseudo C, ça donne quelque chose comme:
1 2 3 4 | int random3() { int r = random4(); return r < 3 ? r : random3(); } |
En notant $E_3$ la consommation moyenne d’entropie de cette méthode, on a $E_3 = 3/4\times 2 + 1/4\times (2+E_3)$. Au final, $E_3 = 8/3 \approx 2.667$. On a donc une méthode qui consomme en moyenne beaucoup plus d’entropie qu’elle n’en génère.
Cependant, en groupant un peu les choses, on peut utiliser 5 bits d’entropie (une valeur entre 0 et 31 inclus) pour générer potentiellement 3 sorties de random3 (pour les valeurs de 0 à 26 inclus). On a alors $3*E = 27/32\times 5 + 5/32 \times (5 + 3*E)$ qui donne $E = 160/81 \approx 1.975$ par sortie de random3. En utilisant $2^8$ et $3^5$, on arrive même à faire tomber le coût à environ $1.686$. Il est donc tout à fait possible d’optimiser la quantité d’entropie utilisé pour faire notre choix uniforme entre 3 éléments. Cependant, cela ne se généralise pas très bien. Par exemple, si je veux
J’ai essayé d’imaginer un moyen qui permettrait de récupérer cette entropie "manquante" en imaginant un processus qui va en quelques sortes générer deux "flux" d’entropie: un premier flux qui donne 0 ou 1 avec une probabilité respectives 3/4 et 1/4 et un deuxième flux qui donne 0, 1 ou 2 de manière uniforme. Toujours en pseudo C:
1 2 3 4 5 6 7 8 9 | void random_flux(flux* f1, flux* f2) { int r = random4(); if (r < 3) { f1.send(0); f2.send(r); } else { f1.send(1); } } |
En moyenne, cette fonction génère bien en moyenne 2 bits d’entropie: le premier flux en reçoit environ $0.811$ par appel de random_flux et le deuxième en reçoit $1.585*3/4 = 1.189$ par appel de random_flux. Cependant, je ne vois pas trop comment convertir le premier flux en un flux binaire aléatoire uniforme ou un flux ternaire aléatoire uniforme (équivalent au deuxième flux) sans perte d’entropie.
D’un point de vue théorique, le problème initial revient à prendre un nombre réel aléatoire choisi uniformément entre 0 et 1 en écriture binaire et à le convertir en écriture ternaire. Cependant, cette méthode pose quelques soucis. Premièrement, il n’est pas possible de borner le nombre de "décimale" binaire nécessaire pour sortir une "décimale" ternaire. Deuxièmement, j’ai l’intuition que même sans être dans un cas dégénéré où il faut un temps fini pour sortir la prochaine décimale, la quantité de mémoire nécessaire à ce calcul va croître de manière non bornée au fur et à mesure que l’on consomme des "décimales" binaires.
Finalement, est-ce qu’il existe un algorithme qui fonctionne en temps fini qui permet de convertir un flux binaire aléatoire uniforme en un flux ternaire aléatoire uniforme. Si oui, en existe-il un qui n’a pas de perte d’entropie (ou dont la perte d’entropie tend vers 0)?
. Voici le détail des calculs, si quelqu’un veux vérifier: