Résumé | On s'intéresse ici à la question de savoir quelles lois de probabilités à densité (sur [0,1]) peuvent être simulées en n'utilisant qu'une mémoire bornée. Assez naturellement, on se ramène à considérer des automates probabilistes qui écrivent le développement (binaire, ou plus généralement, D-aire) d'un réel aléatoire.
Dans ce modèle, on dispose de deux résultats : Knuth et Yao ont prouvé en 1976 que les seules distribution à densité analytique qui peuvent être simulées, sont en fait à densité polynomiale ; et Vatan a caractérisé en 2001 les densités polynomiales qui sont simulables. Je propose une nouvelle preuve du résultat de Vatan, qui a l'avantage d'être constructive (on a un algorithme qui, partant de la densité, construit un automate qui la simule), mais aussi de caractériser les densités simulables parmi celles qui sont seulement polynomiales par morceaux. |