Probability and algorithmics: a focus on some recent developments

Peggy Cenac (1) , Irène Marcovici (2) , Christelle Rovetta (3) , Mathieu Sablik (4) , Rémi Varloot (5)

1 IMB - Institut de Mathématiques de Bourgogne [Dijon]
2 IECL - Institut Élie Cartan de Lorraine
3 DI-ENS - Département d'informatique - ENS Paris
4 IMT - Institut de Mathématiques de Toulouse UMR5219
5 Alcatel-Lucent Bell Labs France [Nozay]

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.

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, échantillonnage 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.

Domaines: Systèmes dynamiques [math.DS]; Probabilités [math.PR]; Combinatoire [math.CO]; Complexité [cs.CC]; Informatique et langage [cs.CL]; Mathématique discrète [cs.DM]; Théorie de l'information [cs.IT]; Système multi-agents [cs.MA]

Peggy Cenac, Irène Marcovici, Christelle Rovetta, Mathieu Sablik, Rémi Varloot. Probability and algorithmics: a focus on some recent developments. ESAIM: Proceedings and Surveys, 2017, 60, pp.203-224. ⟨10.1051/proc/201760203⟩. ⟨hal-01970755⟩