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


Date 2017-11-24  10:45-11:45
TitreSimulation à mémoire finie de lois de probabilités continues 
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.  
Lieu076 
OrateurPhilippe Duchon 



Aucun document lié à cet événement.

Retour
Retour à l'index