Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2017-03-17  10:45-11:45
TitreSimulation à mémoire finie de lois de probabilités 
Résumé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 donc 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, alors cette densité est en fait polynomiale - ce qui exclut de fait de nombreuses lois usuelles. Je présenterai le modèle et le résultat de Knuth et Yao, 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.  
Lieu076 
OrateurPhilippe Duchon 



Aucun document lié à cet événement.

Retour
Retour à l'index