| Issue |
ESAIM: Procs
Volume 60, 2017
Journées MAS 2016 de la SMAI – Phénomènes complexes et hétérogènes
|
|
|---|---|---|
| Page(s) | 203 - 224 | |
| DOI | https://doi.org/10.1051/proc/201760203 | |
| Published online | 14 December 2017 | |
Probability and algorithmics: a focus on some recent developments
1 Institut de Mathématiques de Bourgogne, UMR 5584, Université de Bourgogne, CNRS, F-21078 Dijon Cedex, France
2 Institut Élie Cartan de Lorraine, UMR 7502, Université de Lorraine, CNRS, F-54506 Vandoeuvre-lès-Nancy Cedex, France
3 Inria Paris and LIP6, UMR 7606, Université Pierre et Marie Curie, CNRS, F-75252 Paris Cedex 05, France
4 Institut de Mathématiques de Toulouse, UMR 5219, Université de Toulouse, CNRS, Université Paul Sabatier, F-31062 Toulouse Cedex 9, France
5 Microsoft Research - Inria Joint Centre, F-91120 Palaiseau, France
This article presents different recent theoretical results illustrating the interactions between probability and algorithmics. These contributions deal with various topics: cellular automata and calculability, variable length Markov chains and persistent random walks, perfect sampling via coupling from the past. All of them involve discrete dynamics on complex random structures.
Résumé
Cet article présente différents résultats récents de nature théorique illustrant les interactions entre probabilités et algorithmique. Ces contributions traitent de sujets variés : automates cellulaires et calculabilité, chaînes de Markov à mémoire variable et marches aléatoires persistantes, échantillonage parfait par la méthode de couplage par le passé. Leur point commun est de faire intervenir des dynamiques discrètes sur des structures aléatoires complexes.
© EDP Sciences, SMAI 2017
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.