|
|
|
Week 4: ProbabilityProbabilistic aspects (June 20 - 24)Mind the boatDeparture from La Rochelle sunday (june 19) at 6.30pm, no boat on monday! Schedule
Afternoons are devoted to talks and free discussions.You can already propose a talk by email. LecturesCédric Boutillier: Limit shapes for dimer modelsDimer models on bipartite planar graphs form a particular class of random height models. Since the work of Cohn, Kenyon, and Propp, heights for dimer models are known to satisfy a variational principle: when the mesh of the graph tends to zero, the rescaled random height converges in probability to a deterministic limit shape, minimizing a certain functional. In several particular cases, it is possible to compute explicitly the limit shape, using algebraic methods, taking advantage of integrability of the planar dimer models. We will review some examples, based on the work of Baryshnikov, Pemantle and Wilson, Okounkov and Reshetikhin, and Kenyon and Okounkov. Alexander Holroyd: Tiling LocallyHow can a team assemble a jigsaw puzzle collaboratively? Each individual works on her own section, making random choices if necessary, and communicating with her neighbours, and perhaps with their neighbours, etc. But all individuals must follow the same procedure, and must decide what to do eventually. We can formalize this as solving a tiling problem (or satisfying a shift of finite type) via a finitary factor of independent random variables. A key quantity of interest is the coding radius of the finitary factor, a random variable that measures how far an individual needs to communicate. How small can we make the coding radius? In one dimension, there is a surprising universal answer: for every non-trivial shift of finite type, the optimal coding radius has tower function tails - the probability that an individual needs to communicate to distance r decays as 1/(exp...exp 1) where the height of the tower is a constant times r. The picture is more complicated in higher dimensions, but answers are available for the key case of proper colouring. The optimal tail is again a tower function for 4 or more colours, but a power law for 3 colours. As a special case of the above results, proper colouring cannot be done with bounded coding radius, i.e. as a local function of independent randomness. We can relax this requirement by asking instead for a random colouring in which colours at distance at least k are independent of each other. Surprisingly, this can be done. It is achieved by a family of beautiful and mysterious random colourings that seemingly have no right to exist. Based in part on joint works with Thomas Hutchcroft, Avi Levy, Thomas M. Liggett, Oded Schramm and David B. Wilson. Dana Randall: Sampling Algorithms for Generating Random TilingsSampling algorithms based on Markov chains arise in many areas of co mputation, engineering and science. The idea is to perform a random walk among the elements in a large state space so that samples chosen from the stationary distribution are useful for the application. In order to get reliable results efficiently, we require the chain to be rapidly mixing, or quickly converging to equilibrium. Often there is a parameter of the system (typically related to temperature or fugacity) so that at low values many natural chains converge rapidly while at high values they converge slowly, requiring exponential time. This dichotomy is often related to phase transitions in the underlying models. In these talks we will explain this phenomenon, giving examples form the natural and social sciences, including many examples involving tilings. In particular, we will focus on various “edge-flipping” Markov chains used to sample domino and lozenge tilings, fortresses, and equitable rectangular dissections, and we will see why some are very efficient while others are prohibitively slow. Afternoon talks
|
| Online user: 1 |
|
