Résumé | On s'intéresse à la question de la simulation exacte de lois de probabilités continues sur les réels, et plus précisément, à identifier quelles lois sont simulables exactement en n'utilisant qu'une mémoire finie - le modèle naturel étant une variante d'automates probabilistes, mais il est facile de voir que divers modèles sont équivalents (au moins au sens probabiliste de "presque sûrement").
Le premier résultat sur la question est une condition nécessaire dûe à Knuth et Yao, il y a plus de 40 ans: une loi à densité, et dont la densité est donnée par une fonction analytique, n'est pas simulable par automate si sa densité n'est pas en fait donnée par un polynôme. Je présenterai des résultats récents, qui permettent de caractériser les lois simulables parmi celles dont la densité est donnée par une fonction polynomiale par morceaux (de manière semi constructive dans le cas positif); et je discuterai de possibles extensions au cas multidimensionnel. |