On the mixing time of the flip walk on triangulations of the sphere - 18/04/17
pages | 8 |
Iconographies | 2 |
Vidéos | 0 |
Autres | 0 |
Abstract |
A simple way to sample a uniform triangulation of the sphere with a fixed number n of vertices is the Monte-Carlo method: we start from an arbitrary triangulation and flip repeatedly a uniformly chosen edge. We give a lower bound of order on the mixing time of this Markov chain.
Le texte complet de cet article est disponible en PDF.Résumé |
Un moyen simple de simuler une triangulation uniforme de la sphère avec un nombre fixé n de sommets est d'utiliser une méthode de Monte-Carlo : on démarre avec une triangulation quelconque, puis, de manière répétée, on choisit une arête uniformément et on la « flippe », i.e. on l'efface et on la remplace par l'autre diagonale du quadrilatère qui se forme. Nous montrons que le temps de mélange de la chaîne de Markov obtenue est au moins d'ordre .
Le texte complet de cet article est disponible en PDF.Plan
Vol 355 - N° 4
P. 464-471 - avril 2017 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?