Talking Across Fields

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:

Monday, March 24th, 2014
9:30 am - 9:50 am
Coffee and check-in
9:50 am - 10:00 am
Opening remarks by Michel Ledoux
10:00 am - 10:50 am
Rates of convergence to quasi-stationary
Persi Diaconis, Stanford University
11:00 am - 11:20 am
Break
11:20 am - 12:10 pm
The Ornstein-Uhlenbeck 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é Paris-Sud
3:00 pm - 3:10 pm
Break
3:10 pm - 4:00 pm
Zero-Variance techniques for Monte Carlo algorithms
Michel Caffarel, Université Toulouse 3
4:00 pm - 5:30 pm
Problems session: propositions of subjects
Tuesday, March 25th, 2014
9:00 am - 9:50 am
On the uniform ergodicity of the particle Gibbs sampler
Eric Moulines, Télécom Paris-Tech
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
Wednesday, March 26th, 2014
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 Sud-Paris
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
Rejection-free, Irreversible, and Infinitesimal (!) Monte Carlo Algorithms
Werner Krauth, Ecole Normale Supérieure
Thursday, March 27th, 2014
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
Friday, March 28th, 2014
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é Paris-Dauphine
11:00 am - 11:20 am
Break
11:20 am - 12:10 am
Merging of time inhomogeneous Markov Chains
Laurent Saloff-Coste, Cornell University
12:10 pm - 12:20 pm
Closing remarks
List of talks:
Michel Caffarel (Toulouse)
Title: Zero-Variance 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 "zero-variance 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 Ornstein-Uhlenbeck 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 quasi-stationary
Abstract: Absorbing Markov chains have quasi-stationary distributions; these serve as stationary distributions for the chain conditioned on non-absorbtion 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 quasi-stationary). We have found examples showing cut-off phenomena and show that a Doob transformed chain allows the usual tools of Markov chains (eigenvalues, log-Sobolev, 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 lag-one autocovariance. As an important application we use this result for comparing different data-augmentation-type Metropolis-Hastings algorithms. In particular, we compare some pseudo-marginal 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 graph-theoretic 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 two-block Gibbs samplers. I will then introduce the sandwich algorithm, which is a variant of the two-block 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: Rejection-free, 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 rejection-free Markov-chain Monte Carlo algorithms that break detailed balance yet satisfy detailed balance. These algorithms generalize the recent hard-sphere event-chain Monte Carlo method. As an application, I demonstrate considerable speed-up of the event-chain algorithm for hard and soft spheres and for Lennard-Jones 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 1-q 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(1-q) 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 off-the-shelf 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 non-compact 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 n-vertex 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 Saloff-Coste (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 Bernoulli-Laplace and the random transpositions in the symmetric group. Several problems remain open.