9th Cornell Probability Summer School

July 15–26, 2013

Program of Talks and Activities

All talks were held in Malott Hall, room 251 (map). For titles, abstracts, and links associated with each speaker, scroll down or click any of the names in the tables below.

Week 1: July 15–19

Monday Tuesday Wednesday Thursday Friday
9:00-10:15 Borodin Borodin Járai Mossel Járai
10:15-10:45
break
10:45-12:00 Moore Járai Corwin Gorin Mossel
12:00-2:00
lunch
2:00-3:00 Sousi Moore
free
Borodin
free
3:00-3:30
break
break
break
3:30-5:00 tutorials Short talks:
Ben-Ari
Florescu
Hanson
Krishnan
tutorials

Week 2: July 22-26

Monday Tuesday Wednesday Thursday Friday
9:00-10:15 Borodin Borodin Borodin Járai Járai
10:15-10:45
break
10:45-12:00 Mossel Tamuz
Miller
Mossel Miller Mossel
12:00-2:00
lunch
2:00-3:00 Tamuz Járai
free
Mossel end of conference
3:00-3:30
break
break
break
3:30-5:00 tutorials Short talks:
Betea
Cheng
Holmes
Petrov
Short talks:
Candellero
Hu
Racz
Rebeschini

Social Events

Main Lecturers

Alexei Borodin
Borodin

Alexei Borodin, MIT

Borodin’s home page

Integrable Probability

Learn more: Lectures on integrable probability by Borodin and Gorin

The goal of the course is to explain how representation theory helps to discover and analyze integrable structures in probability. The relevant representation theoretic constructions involve representations and characters of symmetric and unitary groups and their infinite-dimensional analogs, Schur and Macdonald symmetric polynomials, and Whittaker eigenfunctions of the quantum Toda lattice. The probabilistic counterparts are random growth models in one and two space dimensions, last passage percolation and directed polymers, solutions of the stochastic heat equation and Kardar-Parisi-Zhang equation and associated quantum many-body systems. No preliminary knowledge of the subject will be assumed.

Antal Jarai
Jarai

Antal Járai, University of Bath

Jarai’s home page

Sandpile Models

Learn more: Mathematical aspects of the abelian sandpile model by F. Redig; Chip-firing and rotor-routing on directed graphs by Holroyd, Levine, et al; Theoretical studies of self-organized criticality by Deepak Dhar

The goal of the course is to present some basic rigorous results on the Abelian sandpile and related models. Motivation comes from statistical physics and various branches of mathematics, including probability and combinatorics. We first study the model on finite graphs, and introduce some of the main open questions. Connections to the uniform spanning tree, the Tutte polynomial, and the rotor-router model will be discussed. Then we move on to questions on infinite graphs. We give determinantal formulas for the limiting probabilities of finite minimal configurations and establish the existence of a limiting sandpile measure under general conditions. We discuss some questions regarding the stabilizibility of infinite configurations.

Elchannan Mossel
Mossel

Elchanan Mossel, University of California at Berkeley

Mossel’s home page

Probability Models of Information Exchange on Networks

Learn more: Social choice and networks

Lecture Notes: Talk #1, Talk #2, Talk #3, Talk #4, Talk #5, Talk #6 (open to all);
Opinion exchange dynamics by Mossel and Tamuz (password required)

We will study a number of models of agents exchanging information on networks. We will begin by surveying classical models including the voter model, repeated averaging (DeGroot model), and repeated majorities. We will then study Bayesian models. Various connections to modern ideas in probability, including to theory of Markov chains, to threshold phenomena and graph limits will play a central role in the course.

Speakers

Ivan Corwin, Clay Mathematics Institute, MIT, and Microsoft Research

Corwin’s home page

ASEP, q-TASEP, and Integrable Quantum Many Body Systems

For the interacting particle systems ASEP and q-TASEP, expectations of a certain class of observables satisfy integrable quantum many body systems which can be solved explicitly. These observables completely determine the particle systems and one-point marginal distributions are expressible in terms of Fredholm determinants, which are useful in proving limit theorems. In my talk I will explain how this all works and also indicate connections to Macdonald processes, Tracy and Widom's work on ASEP, directed polymers, the replica trick, and the Kardar-Parisi-Zhang equation and universality class.

Vadim Gorin, MIT

Gorin’s home page

Random Matrix Corners Processes

Matrix corners processes are probability measures on interlacing arrays of particles, which arise in the study of the joint distributions of eigenvalues of a random matrix and its principal submatrices. I will discuss two aspects of the recent developments in the study of such processes: First is the universal appearance of a distinguished member, GUE-corners process (which is a multilevel version of the familiar Gaussian Unitary Ensemble) as a scaling limits of 2d lattice models, such as random tilings or six-vertex model. Second is the asymptotic behavior of the global fluctuations of eigenvalues as the size of the matrix grows to infinity, which can be described via (2d) Gaussian Free Field. The last fact is now proven for certain general-beta ensembles and suggests a new viewpoint on various Central Limit Theorems in the random matrix theory.

Jason Miller, MIT

Miller’s home page

Imaginary geometry and the Gaussian free field

The Schramm-Loewner evolution (SLE) is the canonical model of a non-crossing conformally invariant random curve, introduced by Oded Schramm in 1999 as a candidate for the scaling limit of loop erased random walk and the interfaces in critical percolation. The development of SLE has been one of the most exciting areas in probability theory over the last decade because Schramm’s curves have now been shown to arise as the scaling limit of the interfaces of a number of different discrete models from statistical physics. In this talk, I will describe how SLE curves can be realized as the flow lines of a random vector field generated by the Gaussian free field, the two-time-dimensional analog of Brownian motion, and how this perspective can be used to study the sample path behavior of SLE. Based on joint works with Scott Sheffield.

Cris Moore, Santa Fe Institute

Moore’s home page

Phase transitions in combinatorial problems

Can we color the vertices of a random graph with three colors, so that the colors of every neighboring pair are different? Can we satisfy a random Boolean formula? Starting in the 1990s, a mixture of experiments and rigorous results showed that many questions like these undergo a sharp jump, from “almost always” to “almost never,” when the density of edges or constraints crosses a critical threshold. This phenomenon has given rise to a lively collaboration between mathematicians, computer scientists, and statistical physicists. I will give an overview of this exciting field, showing how we can analyze search algorithms with differential equations, and locate these transitions with the first and second moment methods.

Epsilon-biased sets, derandomization, and a little number theory

Epsilon-biased sets are subsets of {0,1}n so that every subset of the coordinates has odd or even parity with probability within epsilon of 1/2. For many applications, including estimating the averages of certain functions, we can replace random samples with samples from such a set, and thus “derandomize” an algorithm, making it deterministic. I will describe how we can define such sets explicitly using a little number theory — specifically, the pseudorandom properties of the Legendre symbol, and bounds on exponentials sums. I’ll end by asking how hard it is to construct Ramsey graphs — colorings of the edges of a complete graph so that there are no large monochromatic cliques.

Perla Sousi, University of Cambridge

Sousi’s home page

Hunter, Cauchy rabbit, and optimal Kakeya sets

A planar set that contains a unit segment in every direction is called a Kakeya set. These sets have been studied intensively in geometric measure theory and harmonic analysis since the work of Besicovich (1928); we find a new connection to game theory and probability. A hunter and a rabbit move on the integer points in [0,n) without seeing each other. At each step, the hunter moves to a neighbouring vertex or stays in place, while the rabbit is free to jump to any node. Thus they are engaged in a zero sum game, where the payoff is the capture time. The known optimal randomized strategies for hunter and rabbit achieve expected capture time of order n log n. We show that every rabbit strategy yields a Kakeya set; the optimal rabbit strategy is based on a discretized Cauchy random walk, and it yields a Kakeya set K consisting of 4n triangles, that has minimal area among such sets. (The area of K is of order 1/log(n).) Passing to the scaling limit yields a simple construction of a random Kakeya set with zero area from two Brownian motions. (Joint work with Y. Babichenko, Y. Peres, R. Peretz and P. Winkler.)

Omer Tamuz, Weizmann Institute

Tamuz’s home page

Majority dynamics and the retention of information

Joint work with Ran Tessler

We consider a group of agents connected by a social network who participate in majority dynamics: each agent starts with an opinion in {−1, +1} and repeatedly updates it to match the opinion of the majority of its neighbors.

We assume that one of {−1, +1} is the “correct” opinion S, and consider a setting in which the initial opinions are independent conditioned on S, and biased towards it. They hence contain enough information to reconstruct S with high probability. We ask whether it is still possible to reconstruct S from the agents’ opinions after many rounds of updates.

While this is not the case in general, we show that indeed, for a large family of bounded degree graphs, information on S is retained by the process of majority dynamics.

Our proof technique yields novel combinatorial results on majority dynamics on both finite and infinite graphs.

Short Talks

Iddo Ben-Ari, University of Connecticut

A probabilistic approach to generalized Zeckendorf decompositions

Zeckendorf’s Theorem states that every positive integer can be written uniquely as a sum of non-adjacent Fibonacci numbers, if we start the sequence 1, 2, 3, 5,... This result has been generalized to decompositions arising from other recurrence relations, and to properties of the decompositions, most notabley, Lekkerkerker’s Theorem which gives the mean number of summands. The theorem was originally proved using continued fraction techniques, but recently a more combinatorial approach has had great success in attacking this and related problems, such as the distribution between gaps of summands. We introduce a unified probabilistic framework and show how this machinery allows to reprove and generalize all existing results and obtain new results. The main idea is that the digits appearing in the decomposition are obtained by a simple change of measure for some Markov chain. (Joint with Steven Miller.)

Dan Betea, Université Pierre et Marie Curie, Paris 6

Boxed plane partitions as Schur processes

We discuss how most (all?) natural distributions one looks at on boxed plane partitions (tilings of the hexagon with three types of lozenges) can be viewed as Schur (or Macdonald) Markov processes similar to the Schur process of Okounkov and Reshetikhin for the unboxed case. This is achieved by replacing the (unboxed) Cauchy identity and branching rule for Schur/Macdonald polynomials with boxed instances due to Rains. As a byproduct one obtains an exact random sampling algorithm for such objects by applying the intertwining technique of Borodin and Ferrari. If time permits, parallels with similar results for the Aztec diamond will be drawn.

Elisabetta Candellero, University of Birmingham

Clustering in random geometric graphs on hyperbolic spaces

In this talk we introduce the concept of random geometric graphs on hyperbolic spaces and discuss its applicability as a model for social networks. In particular, we will discuss issues that are related to clustering, which is a phenomenon that often occurs in social networks: two individuals that have a common friend are somehow more likely to be friends of each other. We give a mathematical expression of this phenomenon and explore how this depends on the parameters of our model. (Joint work with Nikolaos Fountoulakis).

Liang Cheng, Purdue University

The long-time behavior of diffusion in tilted periodic potentials

A variety of phenomena in physics and other fields can be modeled as diffusion in heat bath under tilted periodic potentials. We are interested in the long-time average velocity considered as a function of the external force, that is, the tilt of the potential. In many cases, the long-time behavior — pinning and de-pinning phenomenon — has been observed. We use the method of stochastic differential equation to study the Langevin equation describing such diffusion. In the over-damped limit, we show the convergence of the long-time behavior to that of the Smoluchowski-Kramers approximation, and carry out asymptotic analysis based on Risken’s and Reimann et al.’s formula; in the under-damped limit, applying Freidlin et al.’s theory we firstly show the existence of three pinning and de-pinning thresholds of the normalized tilt, corresponding to the bi-stability phenomenon, as noise decays to zero; secondly derive formulas of the mean return time of the pinning or running state.

Laura Florescu, NYU Courant Institute

Escape rates for rotor walk in Zd

Rotor walk is a deterministic analogue of random walk. We study its recurrence and transience properties on Zd for the initial configuration of all rotors aligned. If n particles in turn perform rotor walks starting from the origin, we show that the number that escape (i.e., never return to the origin) is of order n in dimensions d ≥ 3, and of order n/log(n) in dimension 2. (Joint work with Shirshendu Ganguly, Lionel Levine, Yuval Peres.)

Jack Hanson, Indiana University

Sublinear variance in first-passage percolation

I will describe results obtained with M. Damron and P. Sosoe showing that the variance of the passage time from the origin to a point x in first-passage percolation on Zd (d > 1) is bounded above by C x / log x under minimal assumptions on the edge-weight distribution. The proof requires only that the edge weights have 2 + log moments. This extends work of Benjamini-Kalai-Schramm and Benaim-Rossignol.

Irina Holmes, Louisiana State University

An infinite-dimensional Gaussian Radon transform

We develop a Radon transform on Banach spaces using Gaussian measure and prove that if a bounded continuous function on a separable Banach space has zero Gaussian integral over all hyperplanes outside a closed bounded convex set in the Hilbert space corresponding to the Gaussian measure then the function is zero outside this set.

Wenqing Hu, University of Maryland at College Park

On diffusion and wave front propagation in narrow random channels

We consider a solvable model for the motion of molecular motors. Based on the averaging principle, we reduce the problem to a diffusion process on a graph. We then calculate the effective speed of transportation of these motors. We also consider a reaction-diffusion equation in narrow random channels. We approximate the generalized solution to this equation by the corresponding one on a random graph. By making use of large deviation analysis we study the asymptotic wave front propagation.

This talk is based on the following papers: [1] Freidlin, M., Hu, W., On diffusion in narrow random channels, Journal of Statistical Physics 152 (2013), 136–158. [2] Freidlin, M., Hu, W., Wave front propagation for a reaction-diffusion equation in narrow random channels, Nonlinearity (accepted).

Arjun Krishnan, New York University

Variational formula for the limit shape of first-passage percolation

Consider a set of positive edge-weights {τe} that are stationary and ergodic under translation on the square lattice Zd. Let T(x) be the first-passage time from the origin to x in Zd. The convergence of T([nx])/n to the time-constant μ(x) defined by μ(x) := limn→∞ T([nx])/n can be viewed as a problem of homogenization for a discrete Hamilton-Jacobi equation. If the edge weights satisfy 0 < a ≤ τeb almost surely, μ(x) is a norm on Rd. We borrow techniques from stochastic homogenization to prove a variational formula for the dual-norm (on Rd) of μ(x). The variational formula can be used for a variety of purposes. As examples of its use, we solve it exactly for the time-constant when the edge-weights are periodic, and prove bounds in the i.i.d setting. Our results apply to a large class of optimal-control problems on lattices that include directed first-passage percolation and long-range percolation.

Leonid Petrov, Northeastern University

Asymptotics of lozenge tilings of polygons

I will briefly discuss asymptotics of the model of uniformly random tilings of polygons drawn on the triangular lattice by lozenges (= rhombi) of three types. As a particular case, this model includes the most investigated case of random boxed plane partitions (when the polygon is a hexagon). Looking at the asymptotics of the determinantal correlation kernel of the model, we manage to establish the local asymptotics of random tilings in the bulk, and the Airy2 behavior of interfaces between so-called liquid and frozen phases. This also reconstructs limit shapes of random stepped surfaces obtained earlier by Cohn, Propp, Kenyon, and Okounkov, and we present new explicit formulas related to limit shapes. Moreover, our method allows to prove a conjecture of Kenyon (2004) that the large-scale asymptotics of random tilings are asymptotically governed by the Gaussian Free Field.

Miklos Racz, University of California at Berkeley

Coexistence in preferential attachment networks

We introduce a new model of type adoption on a dynamic network. The key property of our model is that type choices evolve simultaneously with the network itself. When a new node joins the network, it chooses neighbors according to preferential attachment, and then chooses its type based on the number of initial neighbors of each type. This can model a new cell-phone user choosing a cell-phone provider, a new student choosing a laptop, or a new athletic team member choosing a gear provider. We are able to provide a detailed analysis of the new model; in particular, we are able to determine the limiting proportions of the various types. The main qualitative feature of our model is that, unlike other current theoretical models, often several competing types will coexist, which matches empirical observations in many current markets. (This is joint work with Tonci Antunovic and Elchanan Mossel.)

Patrick Rebeschini, Princeton University

Filtering in high dimension

A problem that arises in many applications is to compute the conditional distributions of stochastic models given observed data. While exact computations are rarely possible, particle filtering algorithms have proved to be very useful for approximating such conditional distributions. Unfortunately, the approximation error of particle filters grows exponentially with dimension. This phenomenon has rendered particle filters of limited use in complex data assimilation problems that arise, for example, in weather forecasting or oceanography. In this short talk I will argue that it is possible to develop “local” particle filtering algorithms whose approximation error is dimension-free by exploiting conditional decay of correlations properties of high-dimensional models. As a proof of concept, we prove for the simplest possible algorithm of this type an error bound that is uniform both in time and in the model dimension. (Joint work with R. van Handel.)

Acknowledgements

NSF logo IMS logo

This meeting was partially supported by a grant from the National Science Foundation to the probability group at Cornell University and cosponsored by the Institute of Mathematical Statistics.