A.S. : Yep, apparemment le singulier de ‘dé’ est ‘die’. 😉
Une tâche de programmation délicate a circulé sur Internet qui, comme vous l’avez deviné d’après ma tentative de titre pragmatique, peut être formalisée comme suit :
Donné une fonction qui renvoie un nombre uniformément aléatoire entre 1 et 5 (inclus), concevoir une fonction qui renvoie un nombre uniformément aléatoire entre 1 et 7 (inclus).
Si l’intersection des algorithmes et des statistiques est votre genre de chose, n’hésitez pas à vous lancer ! Un défi supplémentaire consiste à rendre votre algorithme borné en temps. J’ai trouvé que c’était un exercice amusant, seulement pour réaliser qu’il y a des limitations fondamentales en jeu ici.
Bien sûr, un dé signifie ici un générateur aléatoire parfaitement uniforme qui n’existe qu’en théorie. Les dés du monde réel sont régis par des lois naturelles et des imperfections environnementales de telle sorte qu’ils ne sont qu’une approximation (bien qu’une bonne) de ce modèle abstrait.
Une solution non bornée
Regardons une famille d’algorithmes non bornés. Afin de créer un générateur aléatoire qui a au moins 7 résultats, nous devrons lancer le dé à 5 faces au moins deux fois. En le lançant deux fois, on obtient 5^2=25 résultats possibles, et bien que ce ne soit pas un facteur 7, on peut attribuer les 21 premiers résultats à 7 groupes de taille égale à 3. Cependant, si nous arrivons à l’un des quatre résultats restants, la procédure doit recommencer. Nous ne pouvons pas simplement attribuer l’un de ces 4 états finaux malchanceux à une sortie, car cela perturberait la propriété de hasard uniforme.
Dans le graphique ci-dessus, les cercles représentent des » états » de notre programme, et le texte à l’intérieur est la valeur la plus récente du dé lancé. Les cases vertes représentent ensuite la sortie que nous attribuons en fonction de l’état final (= après avoir lancé le dé deux fois). Dans 84 % des cas, nous obtenons une sortie après deux lancers et l’algorithme se termine. Comme vous pouvez le constater, une boucle est présente et rend l’algorithme non borné. Cela signifie que pour chaque nombre entier, quelle que soit sa taille, il existe une probabilité faible mais non nulle que le nombre total de lancers soit supérieur à cette valeur pour calculer une valeur de sortie. Les applications en temps réel avec des exigences strictes en matière de temps sont donc hors de question, à moins que vous ne soyez prêt à faire des compromis sur la précision statistique de l’algorithme.
Une variante de cette solution lance initialement jusqu’à trois dés avant de redémarrer : cela crée 5^3=125 états finaux, et nous pouvons affecter au plus 119 d’entre eux à 7 groupes de taille égale 17. Maintenant, il y a une probabilité de 95,2% de finir après un maximum de trois lancers. Notez que nous devons lancer moins de fois en moyenne qu’auparavant (280/119 ≈ 2,35 contre 50/21 ≈ 2,38), car la plupart du temps nous pouvons déjà prendre un raccourci après les deux premiers lancers, et mapper directement ces états intermédiaires à une sortie. Cette quantité moyenne de lancers continue de baisser au fur et à mesure que nous poursuivons la tendance.
Si vous êtes familier avec la théorie de l’information, alors considérez le fait qu’un lancer de dé à 5 faces (= rand5) génère log2(5) ≈ 2,32 bits d’information, et qu’un lancer de dé à 7 faces (= rand7) génère log2(7) ≈ 2,81 bits d’information. Il s’avère que dans le cas limite, nous avons besoin de seulement log(7)/log(5) ≈ 1,21 appel de rand5 pour chaque valeur de rand7 que nous souhaitons obtenir. L’implémentation exacte qui fonctionne arbitrairement proche de cette limite est plutôt compliquée et sort du cadre de cet article. Nous aurions besoin de stocker des informations d’état entre les multiples appels de rand7, et l’algorithme que j’ai en tête est non seulement toujours non limité dans le temps, mais aussi en mémoire. Je vous invite volontiers à m’informer d’une méthode qui résout ce dernier problème !
Une solution bornée
Il n’existe pas d’algorithme borné qui calcule une valeur aléatoire parfaitement uniforme entre 1 et 7, étant donné un générateur aléatoire entre 1 et 5 seulement. Considérons la famille de solutions non bornées ci-dessus. Comme je l’ai laissé entendre, il y aura toujours, à chaque point, un certain nombre d’états « restants » (compris entre 1 et 6) qui obligeront l’algorithme à redémarrer. Ceci est dû au fait que 5 et 7 sont des nombres premiers, et qu’aucune puissance de 5 ne peut jamais être un multiple de 7. Aussi tentant que cela puisse être d’utiliser le petit théorème de Fermat, de telles tentatives aboutiront à des erreurs de type off-by-one, puisque la théorie de base des nombres rend impossible une solution bornée dans cette famille.
Vous pourriez à juste titre faire remarquer que le nombre d’états finaux n’est pas toujours une puissance de 5, par exemple dans le cas de ‘jusqu’à trois rouleaux’ où nous pouvons prendre des raccourcis après deux rouleaux déjà. Peut-être pourrions-nous arranger le tableau d’états de manière à créer un algorithme borné avec des chemins de longueur variable et 7n états finaux ? Cependant, considérez ce qui suit :
- Ces états finaux ne seront pas également probables parce que tous les chemins n’ont pas la même longueur (= quantité d’appels de rand5).
- Nous pouvons très facilement étendre l’arbre pour rendre chaque chemin également long, en appelant inutilement rand5 un nombre approprié de fois chaque fois que nous sommes à un état final prématuré. Maintenant, la quantité d’états finaux redevient une puissance de 5, et tous les états finaux sont également probables.
Bien sûr, ce n’est pas une preuve formelle, mais j’espère vous avoir donné une certaine intuition du problème. Comme nous le voyons, parfois, un problème peut sembler très réaliste, seulement pour tomber sur des faits mathématiques comme ceux-ci. Après cette analyse, pouvez-vous déterminer s’il est possible de simuler un dé à 8 faces à partir d’un dé à 4 faces ?