skip to content
 

Timetable (CSMW02)

Markov-Chain Monte Carlo Methods

Tuesday 25th March 2008 to Friday 28th March 2008

Tuesday 25th March 2008
08:30 to 09:55 Registration INI 1
10:00 to 11:00 E Vigoda ([Georgia Institute])
Random colorings

I will give a survey of results on the analysis of MCMC algorithms for randomly sampling proper vertex k-colorings of an input graph with maximum degree D. In the first part of the talk I will explain how such a sampling algorithm implies an algorithm to estimate the number of k-colorings. The standard reduction considers the problem at a sequence of temperatures, where the infinite temperature problem corresponds to colorings of the empty graph and the zero temperature problem corresponds to colorings of the input graph. I will present recent work (with Stefankovic and Vempala) that reduces the number of intermediate temperatures in this reduction to O*(\sqrt{n}).

After the briefest introduction to coupling, I'll show Jerrum's proof of fast convergence of the single-site Glauber dynamics for any graph when k>2D. We'll then look at more sophisticated coupling arguments, beginning with the work of Dyer and Frieze, that utilize so-called local uniformity properties, which are local properties of random colorings. I'll then explain more recent work of Hayes that utilizes the spectral radius to get improved results for colorings of planar graphs. Finally, we'll see recent work (with Hayes and Vera) that combines the uniformity and spectral radius ideas to prove poly-time convergence of the Glauber dynamics on planar graphs when k>D/logD.

INI 1
11:10 to 11:40 Coffee
11:40 to 12:30 Y Peres (Microsoft Research)
Can extra updates delay mixing?

We consider Glauber dynamics (starting from an extremal configuration) in a monotone spin system, and show that interjecting extra updates cannot increase the expected Hamming distance and the total variation distance to the stationary distribution. We deduce that for monotone Markov random fields, when block dynamics contracts a weighted Hamming metric, so does single-site dynamics started at extremal configurations. In particular, our result completes work of Kenyon, Mossel and Peres concerning Glauber dynamics for the Ising model on trees. Our approach also shows that on bipartite $n$-vertex graphs, alternating updates systematically between odd and even vertices cannot improve the mixing time by more than a factor of $\log n$ compared to updates at uniform random locations. (Joint work with Peter Winkler).

INI 1
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:30 C Greenhill ([New South Wales])
Asymptotic enumeration of contingency tables

Contingency tables are nonnegative integer matrices with given row and column sums. Such matrices appear in many combinatorial contexts and have applications in statistics. There has been a lot of work on efficient algorithms for approximately counting these matrices using Markov chains or dynamic programming.

Asymptotic formulae for these matrices have recently been obtained for sufficiently sparse matrices (Greenhill & McKay) and for sufficiently dense matrices when all row sums are equal and all column sums are equal (Canfield & McKay). I will discuss these results and ask whether they provide a practical method for approximate counting.

Joint work with Brendan McKay.

INI 1
14:35 to 15:05 PJ Cameron ([London])
A Markov chain for certain triple systems

In 1996, M. T. Jacobson and P. Matthews constructed a Markov chain whose limiting distribution is uniform on Latin squares. This has been a useful tool for exploring the properties of random Latin squares. However, very little is known about the rate of convergence of the Markov chain; more information about this would greatly enhance its value.

A feature of the Jacobson-Matthews Markov chain is that it enlarges the search space by adding "improper" Latin squares which have one "fault"; when we move from an improper Latin square we must fix that fault but may create another one.

The method has been extended to other classes of combinatorial structures (Steiner triple systems and 1-factorizations of complete graphs), and to more general versions of these (corresponding to the generalization from Steiner triple systems to BIBDs with an arbitrary value of lambda. Unfortunately, except in the case of orthogonal arrays (the generalization of Latin squares), the connectedness of the Markov chain is conjectured, but not known to hold. If the conjecture is true, then the limiting distribution in each of these cases will be uniform.

Related Links

INI 1
15:10 to 15:40 Tea
15:40 to 16:10 M Luczak ([LSE])
Glauber dynamics for the Ising Model on the Complete Graph

We study the Glauber dynamics for the Ising model on the complete graph on n vertices, also known as the Curie-Weiss model. For the high-temperature regime (\beta < 1), we prove that the dynamics exhibits a cutoff: the total variation distance to stationarity drops from near 1 to near 0 in a window of order n centred at [2(1-\beta)]^{-1} n \log n. For the critical case (\beta =1), we prove that the mixing time is of the order n^{3/2}. In the low-temperature case (\beta > 1), we study metastability. In particular, we show that the Glauber dynamics restricted to states of non-negative magnetization has mixing time O(n \log n). This is joint work with David Levin and Yuval Peres.

INI 1
16:15 to 16:45 R Kannan ([Microsoft Research Labs., India])
A new probability inequality and some optimal concentration results

The usual Azuma's inequality assumes absolute bounds on the Martingale differences. This is often too pessimistic, but seems inherently required in the usual moment-generating function method. We prove a new general inequality based on bounds on moments of Martingale differences rather than absolute bounds; while the method used is elementary, it is quite different from the m-g f method.

We present two applications - to bin packing and counting the number of triangles in a random graph. In the first, we prove that the number of bins required to pack n i.i.d. items, each with mean a and variance b^2 is concentrated in an interval of length O(a^{3/2} b) which we show is best possible. Then we prove that the number of triangles in a random graph G_{n,p} (with p<n^{-2/3}) is concentrated in an interval of length (np)^{3/2} which is again the best possible, since this is the standard deviation. We also outline applications to counting the number of H in G_{n,p} for any fixed graph H.

INI 1
16:50 to 17:20 D Levin ([Oregon])
Ising Model on Kn: mixing time for Glauber dynamics at critical ϐ

We study the Glauber dynamics for the Ising model on the complete graph on n vertices, in the critical case (\beta =1). We prove that the mixing time is of the order n^{3/2}. This is joint work with Malwina Luczak and Yuval Peres.

INI 1
17:30 to 18:30 Welcome Wine Reception
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Wednesday 26th March 2008
09:30 to 10:30 F Martinelli ([Roma])
The east model: a case study from glassy dynamics

The East model is a prototype of a class of spin models widely used in statistical physics to describe some key aspects of the dynamics of glasses. Here I will review some of its features together with a survey of recent results and techniques from the point of view of MCMC.

Related Links

INI 1
10:35 to 11:05 A Sly ([UC Berkeley])
Rapid mixing of Gibbs sampling on graphs that are sparse on average

We overcome an obstacle of most techniques for analysing the mixing time of the Glauber dynamics, that they are stated in terms of the maximal degree and are therefore insufficient for Erdos Renyi random graphs where the maximum degree grows as order (log n)/(log log n). We show that for most natural models defined on G(n,d/n) if the "temperature" is high enough (as a function of d only) then the mixing time of Glauber dynamics is polynomial. This proves in particular a conjecture of Dyer et.al. proving rapid mixing of random colourings on G(n,d/n) with a constant number of colours.

INI 1
11:10 to 11:40 Coffee
11:40 to 12:10 JA Fill ([Johns Hopkins])
On hitting times and fastest strong stationary times for birth-and-death chains and other skip-free chains

An (upward) skip-free Markov chain with the set of nonnegative integers as state space is a chain for which upward jumps may be only of unit size; there is no restriction on downward jumps. In a 1987 paper generalizing a well-known theorem (usually attributed to Keilson) for birth-and-death chains, Brown and Shao determined, for an irreducible continuous-time skip-free chain and any d, the passage time distribution from state 0 to state d. When the nonzero eigenvalues nu_j of the generator are all real, their result states that the passage time is distributed as the sum of d independent exponential random variables with rates nu_j. We give another proof of their theorem. In the case of birth-and-death chains, our proof leads to an explicit representation of the passage time as a sum of independent exponential random variables. Diaconis and Miclo also recently obtained such a representation, but our construction is much simpler.

We obtain similar (and new) results for a fastest strong stationary time T of an ergodic continuous-time skip-free chain with stochastically monotone time-reversal started in state 0, and we also obtain discrete-time analogs of all our results.

Related Links

INI 1
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:30 E Lubetzky (Microsoft Research)
Cutoff in total variation for birth-and-death chains

We prove that a family of continuous-time or lazy discrete-time birth-and-death chains, exhibits the cutoff phenomenon if and only if the product of the mixing-time and spectral-gap tends to infinity; in this case, the cutoff window of at most the geometric mean between the relaxation-time and mixing-time. An analogous result for convergence in separation was proved earlier by Diaconis and Saloff-Coste (2006) for birth-and-death chains started at an endpoint; we show that for any lazy (or continuous-time) birth-and-death chain with stationary distribution $\pi$, the separation $1 - p^t(x,y)/\pi(y)$ is maximized when $x,y$ are the endpoints. Together with the above results, this implies that total-variation cutoff is equivalent to separation cutoff in any family of such chains. (Joint with J. Ding and Y. Peres).

INI 1
14:35 to 15:05 R Montenegro ([Massachusetts Lowell])
A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm

We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G and find that, if the partition in the algorithm is given by a random oracle, then with high probability a collision occurs in order |G|^0.5 steps. This is the first proof of the correct order bound which does not assume that every step of the algorithm produces an i.i.d. sample from G.

Related Links

INI 1
15:10 to 15:40 Tea
15:40 to 16:10 M Bordewich ([Durham])
Path coupling without contraction

Path coupling is a useful technique for simplifying the analysis of a coupling of a Markov chain. Rather than defining and analysing the coupling on every pair in the state space of the Markov chain, analysis is done on a smaller set S. If the coefficient of contraction b is strictly less than one, no further analysis is needed in order to show rapid mixing. However, if b=1 then analysis (of the variance) is still required for all pairs in the state space. In this paper we present a new approach which shows rapid mixing in the case b=1 with a further condition which only needs to be checked for pairs in S, greatly simplifying the work involved.

INI 1
16:15 to 16:45 M Dyer ([Leeds])
Colouring random graphs randomly
INI 1
16:50 to 17:20 C Cooper ([Kings College London])
Multiple random walks in random regular graphs

It was shown that (whp), for $r\ge 3$ the cover time $C_G$ of a random $r$-regular graph $G_r$ is asymptotic to $\theta_r n \ln n$, where $\theta_r=({r-1})/({r-2})$. In this talk we study problems arising from multiple random walks on random regular graphs, and prove the following (whp) results. The time for $k$ independent walks to cover $G_r$ is asymptotic to $ C_G/k$.

For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/{k\choose 2}$. If the walks can communicate on meeting at a vertex, we show that (for most starting positions) the expected time for $k$ walks to broadcast a single piece of information is asymptotic to $((2 \ln k)/k)\theta_r n$, as $k,n$ tend to infinity.

We also establish properties of walks where particles interact when they meet at a vertex by coalescing or by exploding and destroying each other. As an example, the expected extinction time of $k$ explosive particles ($k$ even) tends to $(2\ln 2) \theta_r n $ as $k$ tends to infinity.

INI 1
19:30 to 23:00 Conference Dinner - Corpus Christi College (The Dining Hall)
Thursday 27th March 2008
09:30 to 10:00 P Tetali ([Georgia Tech])
Parking functions and acyclic orientations

Given an undirected graph $G=(V,E)$, and a designated vertex $q\in V$, the notion of a $ G$-parking function (with respect to $q$) has recently been developed and studied by vari ous authors. This notion generalizes the classical notion of a parking function associated with the complete graph, and has been approached from the point of view of sandpile models, chipfiring games etc. In this talk, I will describe some of these connections and describe a simple bijection between maximum $G$-parking functions and certain acyclic orientations of $G$. Of special interest will be the graph of the discrete cube. (This is joint work with Brian Benson.)

INI 1
10:05 to 10:35 J van den Berg ([CWI])
Rapidly mixing Markov chains and the sharp transition in 2D ising percolation

One of the most well-known classical results for site percolation on the square lattice is that, for all values of the parameter p (except its critical value) the following holds: Either a.s. there is an infinite open cluster or a.s. there is an infinite closed `star' cluster. This result is closely related to the percolation transition being sharp.

The analog of this result has been proved by Higuchi in 1993 for two-dimensional Ising percolation (at fixed temperature T > Tc) with external field h, the parameter of the model.

Using a Markov chain and rapid-mixing results of Martinelli and Olivieri, we show that the Ising model can be `decoded' in terms of i.i.d. random variables in such a way that certain general approximate zero-one laws (sharp-threshold results) can be applied. This leads to an alternative proof of Higuchi's result and puts it in a more general framework.

INI 1
10:40 to 11:10 A Frieze ([Carnegie Mellon])
Log-concave random graphs

We propose the following model of a random graph on n vertices. Let F be a multi-dimensional distribution with a coordinate for every pair ij with i,j in [n]. Then G(F,p) is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X(i,j) < p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine some basic properties such as the connectivity threshold for the case where F is down-monotone and has a log-concave density. We also consider cases where the X(i,j) are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

INI 1
11:10 to 11:40 Coffee
11:40 to 12:10 S Shlosman ([CNRS])
Properties of the interfaces in the multyphase regimes

We review results about the phase diagram of the high entropy systems. They undergo the first order phase transition, and at the transition temperature the phases with different entropy coexist. If the two phases are sharing the same volume, then the interface between them is formed. We will explain the stability property of this random surface. (Joint work with Yvon Vignaud.)

INI 1
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 14:30 D Randall ([Sao Paulo State])
Proving slow mixing with fault lines and fat contours

We show that for several sampling problems, local dynamics require exponential time to converge to equilibrium. In particular, we apply our techniques to the problems of sampling independent sets on the triangular lattice (the hard-core lattice gas model) and the weighted even orientations of the Cartesian lattice (the 8-vertex model). For each problem, there is a single parameter (corresponding to temperature or fugacity) such that local Markov chains are expected to be fast at high temperature and slow at low termpature. However, establishing slow mixing for these models has been a challenge because standard Peierls arguments based on (d-1)-dimensional contours do not seem to work. Here we extend this approach to "fat contours" that have nontrivial d-dimensional volume, and use these to establish slow mixing of the local chains. In addition, we show that restricting the contours to fat contours containing "fault lines" allow us to further simplify these proofs.

INI 1
14:35 to 15:05 A Sokal ([UCL and NYU])
An introduction to dynamic critical phenomena and cluster algorithms

I give an introduction, aimed at mathematicians and computer scientists, to physics lore about dynamic critical phenomena. I then give an introduction to cluster algorithms, notably those of Swendsen--Wang and Chayes--Machta, which can potentially achieve significant reductions in critical slowing-down compared to local algorithms.

INI 1
15:10 to 15:40 Tea
15:40 to 16:10 J Machta ([Massachusetts])
Graphical representations and cluster algorithms

In this talk I discuss developments in graphical representations and associated cluster algorithms. After a review of the Edwards-Sokal spin-bond representation for Potts models and the associated Swendsen-Wang algorithm, I discuss graphical representations and cluster algorithms for other systems including random cluster models for real q>1 and Ising spin systems with external fields and/or frustration.

INI 1
16:15 to 17:00 Open problem session INI 1
17:00 to 17:30 Wine and Cheese Reception
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Friday 28th March 2008
09:30 to 10:00 D Wilson (Microsoft Research)
Card shuffling and Diophantine approximation

The "overlapping-cycles shuffle'' mixes a deck of n cards by moving either the nth card or the (n-k)th card to the top of the deck, with probability half each. We determine the spectral gap for the location of a single card, which, as a function of k and n, has surprising behaviour. For example, suppose k is the closest integer to alpha n for a fixed real alpha in (0,1). Then for rational alpha the spectral gap is Theta(n^{-2}), while for poorly approximable irrational numbers alpha, such as the reciprocal of the golden ratio, the spectral gap is Theta(n^{-3/2}).

Related Links

INI 1
10:05 to 10:35 N Bou-Rabee ([California Institute])
Near Boltzmann-Gibbs measure preserving stochastic variational integrator

This talk presents an explicit, structure-preserving probablistic numerical integrator for Langevin systems, and an efficient, structure-preserving integrator for Langevin systems with holonomic constraints. In a nut-shell, the method does for the Boltzmann-Gibbs measure what symplectic integrators do for energy. More precisely, we prove the method very nearly preserves the Boltzmann-Gibbs measure. As a consequence of its variational design, the algorithm also exactly preserves the symplectic area change associated to Langevin processes. The method with supporting theory enables one to take time-step sizes and friction factors at the limit of stability of the integration scheme (e.g., the time-step size must be smaller than the fastest characteristic frequency in the system).

Related Links

INI 1
10:40 to 11:10 B Scoppola ([Roma])
Randomised algorithms for the maximum clique problem
INI 1
11:10 to 11:40 Coffee
11:40 to 12:10 N Berestycki ([Cambridge])
What happens to a random walk before equilibrium?

Since the pioneering work of Diaconis and Shahshahani, much research has been devoted to the study of the cutoff phenomenon, which describes how a random walk on a finite graph reaches its equilibrium distribution over a dramatically short period of time. However, much less is known about how a random walk behaves before it has reached this equilibrium distribution. The purpose of this talk is to study aspects of this question, with an emphasis on the way a random walk gets away from its starting point. In some interesting cases, the growth of the distance exhibits a phase transition from linear to sublinear behaviour. In other examples, there are different regimes with different scalings but no phase transition. While we do not have a theory at the moment, I will discuss some results which relate this phenomenon to the local geometry of the graph (as perceived by a random walker) and state some conjectures.

Partly joint with Rick Durrett.

INI 1
12:15 to 12:45 A Czumaj ([Warwick])
Testing expansion in bounded degree graphs

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an a-expander is a graph G = (V,E) in which every subset U of V of at most |V|/2 vertices has a neighborhood of size at least a|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately O(n^{1/2}).

We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every a-expander with probability at least 2/3 and rejects every graph that is epsilon-far from an a*-expander with probability at least 2/3, where a* = O(a^2/(d^2 log(n/epsilon))), d is the maximum degree of the graphs, and a graph is called epsilon-far from an a*-expander if one has to modify (add or delete) at least epsilon d n of its edges to obtain an a*-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d^2 n^{1/2} log(n/epsilon)/(a^2 epsilon^3)). We will also briefly discuss the recent improvements due to Kale and Seshadhri, Nachmias and Shapira, who reduced the dependency in the expansion of the rejected graphs from O(a^2/(d^2 log(n/epsilon))) to O(a^2/d^2).

Related Links

INI 1
12:45 to 13:30 Lunch at Wolfson Court
14:00 to 14:30 BC Allanach ([Cambridge])
Bank sampling: a practical proposal for sampling from isolated maxima with the Metropolis algorithm

An easy-to-implement form of the Metropolis Algorithm is described which, unlike most standard techniques, is well suited to sampling from multi-modal distributions on spaces with moderate numbers of dimensions (order ten) in environments typical of investigations into current constraints on Beyond-the-Standard-Model physics. The sampling technique makes use of pre-existing information (which can safely be of low or uncertain quality) relating to the distribution from which it is desired to sample. This information should come in the form of a "bank'' or "cache'' of space points of which {\em at least some} may be expected to be near regions of interest in the desired distribution. In practical circumstances such "banks of clues'' are easy to assemble from earlier work, aborted runs, discarded burn-in samples from failed sampling attempts, or from prior scouting investigations. The technique equilibrates between disconnected parts of the distribution without user input.

Related Links

INI 1
14:35 to 15:05 N Bhatnagar ([UC Berkeley])
Extremality of Gibbs measure for colorings on trees

We consider the problem of extremality of the free boundary Gibbs measure for k-colorings on the tree of branching factor D. Extremality of the measure is equivalent to reconstruction non-solvability, that is, in expectation, over random colorings of the leaves, the conditional probability at the root for any color tends to 1/k as the height of the tree goes to infinity. We show that when k>2D/ln(D), with high probability, conditioned on a random coloring of the leaves, the bias at the root decays exponentially in the height of the tree. This is joint work with Juan Vera and Eric Vigoda.

INI 1
15:05 to 15:35 Tea
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons