Annales de la Faculté des Sciences de Toulouse

D. Gaitsgory

Eisenstein series and quantum groups

Eric Bedford

Tanya Firsova

Geometric proof of the $\lambda $-Lemma

Gabriel Calsamiglia

Paulo Sad

Extension of germs of holomorphic foliations

Laurent Miclo

ANNALES
DE LA FACULTÉ
DES SCIENCES
Mathématiques
LAURENT MICLO
Préface
Tome XXIV, no 4 (2015), p. i-iv.
<http://afst.cedram.org/item?id=AFST_2015_6_24_4_r1_0>
© Université Paul Sabatier, Toulouse, 2015, tous droits réservés.
L’accès aux articles de la revue « Annales de la faculté des sci-
ences de Toulouse Mathématiques » (http://afst.cedram.org/), implique
l’accord avec les conditions générales d’utilisation (http://afst.cedram.
org/legal/). Toute reproduction en tout ou partie de cet article sous quelque
forme que ce soit pour tout usage autre que l’utilisation à fin strictement
personnelle du copiste est constitutive d’une infraction pénale. Toute copie
ou impression de ce fichier doit contenir la présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Photo: L.A. Cicero
www.math.univ-toulouse.fr/Talking_Across_Fields/index.php
A workshop on the convergence
to equilibrium of Markov chains
around Persi Diaconis
March 24th-28th 2014
Scientific organizer Laurent Miclo
Institut de Mathématiques de Toulouse
Amphithéâtre Schwartz
Pietro Caputo Università Roma Tre
Patrick Cattiaux Université Toulouse III
Djalil Chafaï Université Paris-Dauphine
Thierry Delmotte  Université Toulouse III
Persi Diaconis Stanford University
Randal Douc Telecom SudParis
Martin Dyer University of Leeds
Shayan Oveis Gharan Stanford University
Jim Hobert University of Florida
Mark Jerrum Queen Mary University of London
Wilfrid Kendall University of Warwick
Werner Krauth Ecole Normale Supérieure
Eyal Lubetzky Microsoft Research
Florent Malrieu Université de Tours
Fabio Martinelli Università Roma Tre
Eric Moulines Telecom Paris-Tech
Yann Ollivier Université Paris-Sud
Yuval Peres Microsoft Research
Clément Rau Université Toulouse III
Laurent Saloff-Coste Cornell University
Prasad Tetali Georgia Institute of Technology
Preface
This special volume of the Annales de la Faculté des Sciences de Toulouse
edits the proceedings of the conference Talking Across Fields which took
place in Toulouse from Monday 24th to Friday 28th of March 2014. It
was one of the events organized during the semester invitation of Persi
Diaconis to the Institut de Mathématiques de Toulouse by the Labex Cen-
tre International de Mathématiques et d’Informatique.
The subject of this conference was the convergence to equilibrium of
Markov chains and related fields, the objective being to review its latest
advances as well as various directions followed by its applications. Indeed
one of the characteristic of the meeting was to gather experts with different
scientific backgrounds, as it is emphasized by the name of the conference
and by the presentation written by Persi Diaconis:
A variety of fields study rates of convergence of Markov Chains to their
stationary distribution. This includes probabilists, statisticians, analysts,
computer scientists and physicists. The conference will aim to bring together
people working in these disciplines and try to encourage them to talk to one
another. Each field has its own techniques and by now these have developed
quite separately. For example, they tend not to cite one another! Of course,
the different fields have slightly different problems but this is all grist for the
mill.
The multidisciplinarity aspect of the conference is equally reflected by
the list of its speakers which is to be find in the poster before this preface.
Several of them agreed to submit a paper for the present special edition
of the Annales de la Faculté des Sciences de Toulouse. Let us succinctly
present these contributions and how they are related.
The volume starts with a historical perspective on the concept of entropy
by Djalil Chafäı. Primary emphasis is put on the entropy production by
evolution equations in various fields, since this is strongly related to the
subject of the conference. This leisurely and very inspiring survey begins
with the H-theorem of Boltzmann and the free entropy of Helmholtz. The
entropy reappears in the approach of Shannon to the central limit theorem
and in its free probability analogue due to Voiculescu. The limiting circu-
lar law of the complex Ginibre ensemble enables a transition toward the
recent use of entropy in study of particles in Coulomb or Riesz repulsive
interactions.
– i –
Preface
The following paper of Pietro Caputo, Georg Menz and Prasad
Tetali also deals with entropy, providing its approximate tensorization un-
der some weak dependence assumptions, suitable for the study of the trend
to equilibrium of certain interacting particle systems. The tensorization
properties of entropy are important in statistical physics and in informa-
tion theory. They allow to control the disorder of a compound system with
the partial disorder of its components.
We stay in the realm of dynamical statistical physics with the two next
papers. Paul Chleboun, Alessandra Faggionato and Fabio Martinelli
study the d-dimensional East process, an interacting particle system be-
longing to the class of kinetically constrained spin models. Due to the con-
straints, establishing convergence to equilibrium is a difficult task, in par-
ticular the classical functional inequalities techniques do not apply. A new
approach is developed to prove a local form of convergence to equilibrium
and to deduce the scaling of the mixing time and the logarithmic Sobolev
constant in a box in terms of its size.
In a series of important articles, Eyal Lubetzky and Allan Sly have
recently introduced a new approach, called information percolation, to solve
the cutoff problem for the Glauber dynamics of the Ising model all the way
down to the critical temperature. In the present expository paper, the au-
thors make the most welcome effort to explain how to use this theory in
the setting of very high temperature Ising model on Zd. In this simplified
context, their analysis of the underlying space-time branching process as-
sociated to the graphical representation of the Glauber dynamics is very
illuminating.
The cut-off phenomenon is also at the heart of the paper of Yuval
Peres and Perla Sousa, who give the first example of a lazy random walk
on a tree for which the mixing time is not equivalent to the relaxation
time. These quantities, as well as the window of the corresponding cut-
off phenomenon, are estimated. The model is a good illustration of the
probabilistic techniques used to deduce the cut-off phenomenon on trees.
We keep on in the company of traditional finite Markov chains with
the work of Matthias Erbar, Jan Maas and Prasad Tetali, developing
the discrete notion of Ricci curvature, applicable to stationary distributions
of continuous time Markov chains, based on entropy flows. This approach
was recently introduced by the second author. In particular, they compute
the Ricci curvature lower bound for two very classical examples of random
walks, namely, a chain on a slice of the n-dimensional discrete cube (the
so-called Bernoulli-Laplace model) and the random transposition shuffle of
the symmetric group of permutations on n letters.
– ii –
Preface
Beside Ricci curvature, another tool coming from geometrical analysis
to investigate finite Markov chains is the resort to spectral decompositions
and their links with Cheeger inequalities. Thus Shayan Oveis Gharan
provides an overview of several important and recent advances in spectral
graph theory concerning estimates of higher order eigenvalues, especially
describing their interactions with topics in both pure mathematics and com-
puter sciences. The emphasis is put on the spectral embedding of graphs in
Euclidean spaces via the first eigenvectors, which is the main tool behind
the new bounds.
A different point of view on isoperimetry is proposed by Thierry
Delmotte and Clément Rau, who update their unpublished preprint on
the anchored or rooted isoperimetric inequality (considering sets containing
a fixed point) and its application to random walks. In particular it contains
a new and much simpler proof for a version of a theorem of Virag.
Random walks are also the subject of the article of Laurent
Saloff-Coste and Tianyi Zheng, providing a sharp lower bound for the re-
turn probability on a finitely generated group of polynomial volume growth.
The originality of this work is that the driving symmetric measure has in-
finite moments of all orders. It leads to new results improving the under-
standing of random walks.
A different kind of Markov evolution is presented by Florent Malrieu:
Piecewise Deterministic Markov Processes and their sometimes surprising
long time behavior. These processes have attracted a lot of attention re-
cently and only quite simple examples are considered in this paper, whose
goal is to illustrate the combined use of tools such as coupling methods,
spectral decomposition, PDE techniques and functional inequalities. Some
challenging open questions end this stimulating exposition.
The protean investigation of convergence to equilibrium often feeds on
examples, this is further illustrated by the two following papers, dealing
with particular and instructive examples. Martin Dyer and Haiko Müller
focus on the switch Markov chain for sampling from perfect matchings of
a bipartite graph, where a single step of the Markov chain takes two edges
in a perfect matching and replaces them by pairing the edges’ endpoints
in a different way. Following a previous paper of Diaconis, Graham and
Holmes, they investigate the computational complexity and the mixing time
on certain classes of graphs. It leads to a challenging conjecture concerning
Hamilton cycles in so-called monotone graphs.
James Hobert and Kshitij Khare study the rate of convergence to
equilibrium for a Gibbs sampler Markov chain introduced recently by Jo-
vanovski and Madras. The resulting Wasserstein bound enables to generalize
a result due to Diaconis, Khare and Saloff-Coste.
– iii –
Preface
Sampling computational Markov chains are heavily used in physics. Thus
Michel Caffarel introduces several Monte Carlo algorithms and impor-
tance sampling techniques to improve them, used by the physicists in order
to simulate ground states. When one is considering Fermionic ground states,
the famous sign problem occurs. It is one of the fundamental challenge in
present computational physics.
Finally with Persi Diaconis, we consider the quantitative convergence
to quasi-stationarity for absorbing, finite, irreducible Markov processes. Us-
ing Doob transforms, we come back to the well-studied situation of conver-
gence to equilibrium of ergodic Markov processes, subject of the conference.
Several examples illustrate the obtained explicit estimates.
Before the reader chooses among the articles s/he is more interested in,
it is now time for the acknowledgments. Obviously, they are fully deserved
by all the above-mentioned people and institutions who made possible the
publication of this volume. But the not-mentioned referees should not be
forgotten, two of them were required by each article and the influence of
their reports extended to the writing of this introduction. So let me finish
by warmly thanking all of them again for their generous and constructive
help.
Laurent Miclo
Toulouse, Friday 10th of June 2015
– iv –


Préface

Matthias Erbar

Jan Maas

Prasad Tetali

Discrete Ricci Curvature bounds for Bernoulli-Laplace and Random Transposition models

Karamoko Diarra

Solutions algébriques partielles des équations isomonodromiques sur les courbes de genre $2$

Yuji Odaka

Song Sun

Testing Log K-stability by blowing up formalism

Michel Boileau

Steven Boyer

Radu Cebanu

Genevieve S. Walsh

Knot complements, hidden symmetries and reflection orbifolds

Stefan Friedl

Patrick Orson

Twist spinning of knots and metabolizers of Blanchfield pairings

Yasuhiro Fujita

A supplementary proof of $L^p$–logarithmic Sobolev inequality

Not a member yet

Eisenstein series and quantum groups

Geometric proof of the $\lambda$ -Lemma