Intentions:
Outside the talks given by the following invited speakers and following a proposition of Yuval Peres, the participants will have the possibility at the end of the opening day to shortly present open problems (limited to 10 minutes per presentation). Thursday afternoon will be dedicated to a brainstorming session on one or two of these open problems, chosen democratically by the participants.
Schedule:
9:30 am  9:50 am 
Coffee and checkin


9:50 am  10:00 am 
Opening remarks by Michel Ledoux


10:00 am  10:50 am 
Rates of convergence to quasistationary
Persi Diaconis, Stanford University 

11:00 am  11:20 am 
Break


11:20 am  12:10 pm 
The OrnsteinUhlenbeck pinball
Patrick Cattiaux, Université Toulouse 3 

12:20 pm  2:00 pm 
Lunch break


2:00 pm  2:50 pm 
The
limits of Markovian models
Yann Ollivier, Université ParisSud 

3:00 pm  3:10 pm 
Break


3:10 pm  4:00 pm 
ZeroVariance techniques for Monte Carlo algorithms
Michel Caffarel, Université Toulouse 3 

4:00 pm  5:30 pm 
Problems session: propositions of subjects 
9:00 am  9:50 am 
On the uniform ergodicity of the particle Gibbs sampler
Eric Moulines, Télécom ParisTech 

10:00 am  10:50 am 
Phase transitions, mixing and computational tractability
Mark Jerrum, Queen Mary University of London 

11:00 am  11:20 am 
Break


11:20 am  12:10 am 
An update on displacement convexity in Markov chains
Prasad Tetali, Georgia Institute of Technology 

12:10 pm  2:00 pm 
Lunch Break


2:00 pm  2:50 pm 
The Sandwich Algorithm: Examples, Spectral Results and Open Problems
Jim Hobert, University of Florida 

3:00 pm  3:20 pm 
Break


3:20 pm  4:10 pm 
A Markov chain of Diaconis, Graham and Holmes
Martin Dyer, University of Leeds 
9:00 am  9:50 am 
On the ergodicity of Piecewise Deterministic Markov Processes
Florent Malrieu, Université de Tours 

10:00 am  10:50 am 
Comparison of asymptotic variances of inhomogeneous Markov chains with application to Markov Chain Monte Carlo methods
Randal Douc, Télécom SudParis 

11:00 am  11:20 am 
Break


11:20 am  12:10 am 
Google maps and improper Poisson line processes
Wilfrid Kendall, University of Warwick 

12:10 pm  2:00 pm 
Lunch Break


2:00 pm  2:50 pm 
East model: mixing time, cutoff and dynamical heterogeneities
Fabio Martinelli, Università Roma Tre 

3:00 pm  3:20 pm 
Break


3:20 pm  4:10 pm 
Rejectionfree, Irreversible, and Infinitesimal (!) Monte Carlo Algorithms
Werner Krauth, Ecole Normale Supérieure 
9:00 am  9:50 am 
Information percolation for the stochastic Ising model
Eyal Lubetzky, Microsoft Research 

10:00 am  10:50 am 
Spectral Embedding of Graphs and its Applications
Shayan Oveis Gharan, Stanford University 

11:00 am  11:20 am 
Break


11:20 am  12:10 am 
Random lattice triangulations: structure and dynamics
Pietro Caputo, Università Roma Tre 

12:10 pm  2:00 pm 
Lunch Break


2:00 pm  2:50 am 
Mixing, covering and exploration for random walks on directed and dynamical graphs
Yuval Peres, Microsoft Research 

3:00 pm  3:20 pm 
Break


3:20 pm  6:30 pm 
Problems session: proposition of solutions (with a break inside)


6:30 pm  7:30 pm 
Reception

9:00 am  9:50 am 
Exit time for anchored expansion
Thierry Delmotte/Clément Rau, Université Toulouse 3 

10:00 am  10:50 am 
About confined particles with singular pair repulsion
Djalil Chafaï, Université ParisDauphine 

11:00 am  11:20 am 
Break


11:20 am  12:10 am 
Merging of time inhomogeneous Markov Chains
Laurent SaloffCoste, Cornell University 

12:10 pm  12:20 pm 
Closing remarks

Michel Caffarel (Toulouse)
Title: ZeroVariance techniques for Monte Carlo algorithms
Abstract:
In this talk, I shall present some work done during these last years regarding the construction and
use of improved estimators (or control variates in mathematical literature) for Monte Carlo simulations.
Although developped in the context of statistical and quantum physics, such estimators are of very broad
applicability and can be virtually used with any Monte Carlo sampler. Finding efficient control variates
(i.e., with important variance reduction) is known to be difficult, particularly when the dimension of
the sampled space becomes large. Here, an important point is that the efficiency of our control variates
takes its origin in the definition of a "zerovariance equation" (or "Poisson equation" in mathematical
literature) based on physical considerations and thus potentially efficient in large dimensions.
Pietro Caputo (Roma)
Title: Random lattice triangulations: structure and dynamics
Abstract:
We consider lattice triangulations, i.e., triangulations of the integer points
in a polygon in Euclidean plane, whose vertices are also integer points.
Our focus is on random triangulations in which
a triangulation \sigma has weight \lambda^{\sigma}, where \lambda is a
positive real parameter and \sigma is the total length of the edges in \sigma.
Empirically, this model exhibits a ''phase transition" at \lambda=1 (corresponding
to the uniform distribution): for \lambda<1 distant edges behave essentially independently, while for \lambda>1 very large regions of aligned edges appear. We substantiate this picture as follows. For \lambda<1 sufficiently small, we show that correlations between edges decay exponentially with distance (suitably defined), and also that the Glauber dynamics (the local Markov chain based on flipping edges) is rapidly mixing (in time polynomial in the number of edges in the triangulation). This dynamics has been proposed by several authors as an algorithm for generating random triangulations. By contrast, for \lambda>1 we show that the mixing time is exponential. This is joint work with F. Martinelli, A. Sinclair and A. Stauffer
Patrick Cattiaux (Toulouse)
Title: The OrnsteinUhlenbeck pinball
Djalil Chafaï (Paris)
Title: About confined particles with singular pair repulsion
Thierry Delmotte/Clément Rau (Toulouse)
Title: Exit time for anchored expansion
Abstract:
Let (Xn) be a reversible random walk on a graph G satisfying
an anchored isoperimetric inequality. We give upper bounds for exit time (and
occupation time in transient case) by X of any set which contains the root. As
an application, we consider random environments of Zd.
Persi Diaconis (Palo Alto)
Title: Rates of convergence to quasistationary
Abstract:
Absorbing Markov chains have quasistationary distributions; these serve as stationary distributions for the chain conditioned on nonabsorbtion up to time $t$. Laurent Miclo and I have begun the job of studying quantitative rates of convergence (how large does $t$ have to be so that the law of the chain at time $t$ is close to quasistationary). We have found examples showing cutoff phenomena and show that a Doob transformed chain allows the usual tools of Markov chains (eigenvalues, logSobolev, coupling) to be applied.
Randal Douc (Evry)
Title: Comparison of asymptotic variances of inhomogeneous Markov chains with application to Markov Chain Monte Carlo methods
Abstract: In this talk we study the asymptotic variance of sample path
averages for inhomogeneous Markov chains that evolve alternatively
according to two different πreversible Markov transition kernels P
and Q. More specifically, our main result allows us to compare directly
the asymptotic variances of two inhomogeneous Markov chains associated
with different kernels Pi and Qi, i being 0 or 1, as soon as the kernels
of each pair (P0, P1) and (Q0,Q1) can be ordered in the sense of lagone
autocovariance. As an important application we use this result
for comparing different dataaugmentationtype MetropolisHastings
algorithms. In particular, we compare some pseudomarginal algorithms
and propose a novel exact algorithm, referred to as the random
refreshment algorithm, which is more efficient, in terms of asymptotic
variance, than the Grouped Independence Metropolis Hastings algorithm
and has a computational complexity that does not exceed that
of the Monte Carlo Within Metropolis algorithm.
Martin Dyer (Leeds)
Title: A Markov chain of Diaconis, Graham and Holmes
Abstract:
In "Statistical problems involving permutations with restricted position", Diaconis, Graham and Holmes (1999) proposed a Markov chain
for generating a random perfect matching in a bipartite graph. They conjectured that this chain converges rapidly to the uniform distribution for
certain classes of graphs. We will describe the problem and its graphtheoretic context, review some recent work, and examine an approach to
bounding the mixing time of the chain.
Shayan Oveis Gharan (Palo Alto)
Title: Spectral Embedding of Graphs and its Applications
Abstract:
Spectral embedding of graphs uses the top k eigenvectors of the normalized Laplacian matrix to embed the graph into R^k. The primary use of this embedding has been for practical spectral clustering algorithms.
I use spectral embedding as a theoretical tool to study several generalizations of the discrete Cheeger’s inequality based on higher order eigenvalues of the normalized Laplacian matrix. In addition, I will show that spectral embedding can be used as a unifying framework for bounding eigenvalues and analyzing random walks on various families of graphs.
Jim Hobert (Gainesville)
Title: The Sandwich Algorithm: Examples, Spectral Results and Open Problems
Abstract:
I will start by describing two real examples of MCMC algorithms from
statistics and how they are used in statistical inference. Both MCMC
algorithms are twoblock Gibbs samplers. I will then introduce the
sandwich algorithm, which is a variant of the twoblock Gibbs sampler
that requires one (computationally inexpensive) extra step at each
iteration. Some spectral results for the sandwich algorithm will be
presented, and I will conclude with some open problems.
Mark Jerrum (London)
Title: Phase transitions, mixing and computational tractability
Abstract:
Phase transition is a term that formally applies to infinite systems.
But the effects of a phase transition can be felt in computations on finite
problem instances. It is widely appreciated that phase transitions are
a barrier to the effective application of certain algorithmic techniques,
such as Markov chain Monte Carlo. But in fact one can sometimes exploit
the existence of a phase transition to rule out an efficient approximation
algorithm of any kind. Occasionally, the point at which a phase transition
occurs can be rigorously linked to the exact boundary between tractability
and intractability for a computational problem.
I'll draw on material from a number of sources, including joint work with
Leslie Ann Goldberg (Oxford) and Colin McQuillan (Liverpool).
Wilfrid Kendall (Coventry)
Title: Google maps and improper Poisson line processes
Werner Krauth (Paris)
Title: Rejectionfree, Irreversible, and Infinitesimal (!) Monte Carlo Algorithms
Abstract: I show how the lifting principle and a new pairwise decomposition of the Metropolis filter allows one to design a class of powerful rejectionfree Markovchain Monte Carlo algorithms that break detailed balance yet satisfy detailed balance. These algorithms generalize the recent hardsphere eventchain Monte Carlo method. As an application, I demonstrate considerable speedup of the eventchain algorithm for hard and soft spheres and for LennardJones systems, using a decomposition for the positive and negative parts of the potential. I sketch extensions of the algorithm to the simulation of quantum systems and to general problems in computer science, as the sampling problem in a polytope.
Eyal Lubetzky (Seattle)
Title: Information percolation for the stochastic Ising model
Florent Malrieu (Tours)
Title: On the ergodicity of Piecewise Deterministic Markov Processes
Abstract:
The evolution of a PDMP is very intuitive: a deterministic motion
punctuated by random jumps. Despite this simplicity, the long
time behavior of these processes is sometimes surprising. With
several basic examples, I will present some ideas to tackle
this question and also several open questions about the regularity
of the invariant measure or about efficient coupling strategies.
Fabio Martinelli (Roma)
Title: East model: mixing time, cutoff and dynamical heterogeneities
Abstract:
The East model is a linear chain of spins, each labeled either 0 or 1, evolving according to a very simple rule:
i) with rate one and independently for each vertex, a new value 1/0 is proposed with probability 1q and q respectively;
ii) the proposed value is accepted iff the spin immediately to the left is labeled "0".
The above is just an example of a general class of interacting particle systems in which the local update of a spin occurs only in the presence of a special ("facilitating") configuration at neighboring vertices. Although the i.i.d. Bernoulli(1q) distribution remains a reversible stationary measure, the relaxation to equilibrium of these chains can be extremely complex, featuring dynamical phase transitions, metastability, dynamical heterogeneities and universal behavior. The East model and its generalizations play an important role as models for the dynamics of real glasses, where small values of q correspond to low temperatures.
After the pioneering work by Aldous and Diaconis in 2001 on the relaxation time of the process, several further mathematical progresses have been achieved which improved and sometimes correct quite basic assumptions made by the physicists. In this talk I will survey some of the most relevant ones.
Eric Moulines (Paris)
Title: On the uniform ergodicity of the particle Gibbs sampler (joint work with R.Douc [Telecom SudParis] and F. Lindsten [Linkoping Univ.])
Abstract:
The particle Gibbs sampler is a systematic way of using a particle filter within Markov chain Monte Carlo (MCMC).
This results in an offtheshelf Markov kernel on the space of state trajectories, which can be used to simulate from the
full joint smoothing distribution for a state space model in an MCMC scheme.
We show that the PG Markov kernel is uniformly ergodic under rather general assumptions, that we will carefully review and discuss.
In particular, we provide an explicit rate of convergence which reveals that:
(i) for fixed number of data points, the convergence rate can be made arbitrarily good by increasing the number of particles, and
(ii) under general mixing assumptions, the convergence rate can be kept constant by increasing the number of particles superlinearly with the number of observations. We illustrate the applicability of our result by studying in detail two common state space models with noncompact state spaces.
(i) for fixed number of data points, the convergence rate can be made arbitrarily good by increasing the number of particles, and
(ii) under general mixing assumptions, the convergence rate can be kept constant by increasing the number of particles superlinearly with the number of observations. We illustrate the applicability of our result by studying in detail two common state space models with noncompact state spaces.
Yann Ollivier (Orsay)
Title: The
limits of Markovian models
Yuval Peres (Seattle)
Title: Mixing, covering and exploration for random walks on directed and dynamical graphs
Abstract:
Eigenvalues and electrical resistances are key tools for analyzing random walks on undirected graphs.
Settings that need different tools are directed graphs and graphs that change in time. We show that lazy simple RW on any Eulerian regular nvertex directed graph
has cover and mixing time at most O(n^2), and the time to visit k distinct vertices is O(k^2); the bounds are O(n^3) and O(k^3) without regularity (joint with Lucas Boczkowski).
For rate 1 random walk on dynamical percolation that evolves at rate r, we give a bound of O(L^2/r) for the mixing time in a torus of side L, which is sharp for the subcritical case
(joint with Alexandre Stauffer and Jeff Steif).
Laurent SaloffCoste (Ithaca)
Title: Merging of time inhomogeneous Markov Chains
Abstract:
This talk report on joint work with J. Zuniga. I will report on some examples of "polynomial time merging" for time inhomogeneous Markov Chains, in search for a theory that is escaping us so far.
Prasad Tetali (Atlanta)
Title: An update on displacement convexity in Markov chains
Abstract:
I will begin with a review of two recent independent approaches for developing notions of displacement convexity, its consequences and related inequalities in discrete spaces. Then I will report on recent progress on some classical Markov chain models such as the BernoulliLaplace and the random transpositions in the symmetric group. Several problems remain open.