Timetable (CSMW02)

Markov-Chain Monte Carlo Methods

Tuesday 25th March 2008 to Friday 28th 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 http://www.maths.qmul.ac.uk/~pjc/preprints/gendesdm.pdf - Preprint of paper on the generalisation 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
 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 http://front.math.ucdavis.edu/0610.5106 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 http://front.math.ucdavis.edu/0707.4042 - arXiv of first of two papers related to talkhttp://front.math.ucdavis.edu/0708.4258 - arXiv of second of two papers related to talk 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 http://www.ravimontenegro.com/research/prho.pdf - Preprint of the paper 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)
 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)