MarkovChain 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 
Random colorings I will give a survey of results on the analysis of MCMC algorithms for randomly sampling proper vertex kcolorings 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 kcolorings. 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 singlesite 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 socalled 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 polytime 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 
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 singlesite 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 
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 
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 JacobsonMatthews 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 1factorizations 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 CurieWeiss model. For the hightemperature 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 lowtemperature case (\beta > 1), we study metastability. In particular, we show that the Glauber dynamics restricted to states of nonnegative 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 
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 momentgenerating 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 mg 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) 
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 
On hitting times and fastest strong stationary times for birthanddeath chains and other skipfree chains An (upward) skipfree 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 wellknown theorem (usually attributed to Keilson) for birthanddeath chains, Brown and Shao determined, for an irreducible continuoustime skipfree 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 birthanddeath 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 continuoustime skipfree chain with stochastically monotone timereversal started in state 0, and we also obtain discretetime analogs of all our results. Related Links

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
14:00 to 14:30 
Cutoff in total variation for birthanddeath chains We prove that a family of continuoustime or lazy discretetime birthanddeath chains, exhibits the cutoff phenomenon if and only if the product of the mixingtime and spectralgap tends to infinity; in this case, the cutoff window of at most the geometric mean between the relaxationtime and mixingtime. An analogous result for convergence in separation was proved earlier by Diaconis and SaloffCoste (2006) for birthanddeath chains started at an endpoint; we show that for any lazy (or continuoustime) birthanddeath 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 totalvariation 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 selfintersections 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 
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  Colouring random graphs randomly  INI 1  
16:50 to 17:20 
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=({r1})/({r2})$. 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 
Rapidly mixing Markov chains and the sharp transition in 2D ising percolation One of the most wellknown 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 twodimensional Ising percolation (at fixed temperature T > Tc) with external field h, the parameter of the model. Using a Markov chain and rapidmixing 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 zeroone laws (sharpthreshold 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]) Logconcave random graphs We propose the following model of a random graph on n vertices. Let F be a multidimensional 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 ErdosRenyi model is the special case when F is uniform on the 01 unit cube. We determine some basic properties such as the connectivity threshold for the case where F is downmonotone and has a logconcave 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 trianglefree 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 hardcore lattice gas model) and the weighted even orientations of the Cartesian lattice (the 8vertex 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 (d1)dimensional contours do not seem to work. Here we extend this approach to "fat contours" that have nontrivial ddimensional 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 SwendsenWang and ChayesMachta, which can potentially achieve significant reductions in critical slowingdown 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 EdwardsSokal spinbond representation for Potts models and the associated SwendsenWang 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) 
09:30 to 10:00 
D Wilson (Microsoft Research) Card shuffling and Diophantine approximation The "overlappingcycles shuffle'' mixes a deck of n cards by moving either the nth card or the (nk)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 
Near BoltzmannGibbs measure preserving stochastic variational integrator This talk presents an explicit, structurepreserving probablistic numerical integrator for Langevin systems, and an efficient, structurepreserving integrator for Langevin systems with holonomic constraints. In a nutshell, the method does for the BoltzmannGibbs measure what symplectic integrators do for energy. More precisely, we prove the method very nearly preserves the BoltzmannGibbs 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 timestep sizes and friction factors at the limit of stability of the integration scheme (e.g., the timestep 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 
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 vertexexpansion: an aexpander 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 aU. 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 aexpander with probability at least 2/3 and rejects every graph that is epsilonfar 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 epsilonfar 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 boundeddegree 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 
Bank sampling: a practical proposal for sampling from isolated maxima with the Metropolis algorithm An easytoimplement form of the Metropolis Algorithm is described which, unlike most standard techniques, is well suited to sampling from multimodal distributions on spaces with moderate numbers of dimensions (order ten) in environments typical of investigations into current constraints on BeyondtheStandardModel physics. The sampling technique makes use of preexisting 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 burnin 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 
Extremality of Gibbs measure for colorings on trees We consider the problem of extremality of the free boundary Gibbs measure for kcolorings on the tree of branching factor D. Extremality of the measure is equivalent to reconstruction nonsolvability, 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) 