Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 18 septembre 2018 à 14h00 en B107, Rado Rakotonarivo nous parlera de : Une chaîne de Markov pour les polytopes entiers

Résumé : Nous présenterons une approche pour faire de la génération aléatoire de polytopes entiers en utilisant les chaînes de Markov. Les objets à engendrer sont les polytopes entiers contenus dans l'hypercube ${[0,k]}^d$, notés $(d,k)$-polytopes. On s’intéresse à la distribution uniforme sur nos objets. La construction du générateur aléatoire se fait de la manière suivante : modéliser une chaîne de Markov dont les états seront les $(d,k)$-polytopes, lancer des marches sur la chaîne jusqu'à ce qu'on soit assez proche d'une distribution stationnaire. Notre principal résultat est que cette distribution stationnaire est unique et uniforme. Je présenterai également des résultats sur le temps de mélange de notre chaîne.


Dernière modification : Friday 31 August 2018 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr