Simulation à mémoire finie de lois de probabilités
Time: 11:00 -- Location: Salle Philippe Flajolet du LIX
La question de la simulation exacte de lois de probabilités sur les réels est généralement étudiée sous un modèle «arithmétique» où on calcule de manière exacte sur des réels. Dans cet exposé, on se place au niveau «bit à bit», et on se demande ce qui peut être simulé si on n'a qu'une mémoire finie. On est alors naturellement amené à considérer des automates qui tirent à pile ou face et qui écrivent des mots, qu'on espère infinis, et qu'on interprète comme le développement de réels; la question est alors de savoir quelles distributions sont simulables de la sorte.
Le modèle est essentiellement celui considéré par Knuth et Yao en 1976, et pour lequel ils ont montré un résultat intrigant : si une loi simulable a une densité qui est une fonction analytique sur un intervalle, alors cette densité est en fait polynomiale sur le même intervalle - ce qui exclut de fait de nombreuses lois usuelles. En 2001, Vatan a annoncé (malheureusement sans preuve complète) un résultat qui caractérise les distributions polynomiales simulables sur [0,1] comme étant celles dont la densité ne s'annule pas en un point irrationnel.
Je présenterai le modèle et les résultats antérieurs (y compris un résultat un peu plus général que celui annoncé par Vatan, pour les distributions polynomiales par morceaux), mais aussi un résultat plus nouveau de classification : étant donné un automate, on peut dire s'il simule une loi à atomes, ou à densité, ou une loi plus «méchante». Je montrerai aussi des exemples qui interdisent une généralisation trop forte du résultat de Knuth et Yao.