10th Cornell Probability Summer School

July 14–25, 2014

Program of Talks and Activities

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

Social Events

• Monday, July 14, 5:00-6:15 p.m. — Reception in the 5th floor lounge of Malott Hall
• Sunday, July 20, 6:00-8:00 p.m. — Barbecue at the Biotech Building, room G10.

Week 1: July 14–18

Monday Tuesday Wednesday Thursday Friday
9:00-10:15 Lubetzky Lubetzky Lubetzky Lubetzky Lubetzky
10:15-10:45 break
10:45-12:00 Ben Arous Ben Arous Ben Arous Ben Arous Ben Arous
12:00-2:00 lunch
2:00-3:15 Chen tutorials free Quastel free
3:15-3:45 break break break
3:45-5:00 Lacoin Asselah Procaccia

Week 2: July 21–25

Monday Tuesday Wednesday Thursday Friday
9:00-10:15 Sun tutorials Komjathy tutorials Hao Wu
10:15-10:45 break
10:45-12:00 Quastel Quastel Quastel Quastel Quastel
12:00-2:00 lunch
2:00-3:30 Short talks:
Gu
Rehle
Sarantsev

Short talks:
Nica
Pymar
Qin
Travers

free Short talks:
Evilsizor
Hulshof
Wei Wu
end of conference

Main Lecturers

Eyal Lubetzky

Time-Space Information Percolation for the Stochastic Ising Model

Recommended reading: Markov chain mixing times by Levin, Peres, Wilmer (chapters 3, 5, 15 in particular)

We will describe a new method of obtaining sharp estimates on mixing for Glauber dynamics for the Ising model, which, in particular, establishes cutoff in three dimensions up to criticality. The new framework, which considers “information percolation” clusters in the space-time slab, shows that total-variation mixing exhibits cutoff with an O(1)-window around the time at which the magnetization is the square-root of the volume. Furthermore, this method opens the door to understanding the effect of the initial state on the mixing time, showing that starting from the uniform (“disordered”) initial distribution asymptotically halves the mixing time, whereas almost every deterministic starting state is asymptotically as bad as starting from the (“ordered”) all-plus state.

Jeremy Quastel

The Kardar-Parisi-Zhang Equation and Universality Class

Recommended reading: Introduction to KPZ

The 1+1 dimensional Kardar-Parisi-Zhang (KPZ) equation is a canonical continuum model belonging to a large universality class including driven lattice gases, randomly growing interfaces, directed polymers, and certain noisy stochastic PDEs. In these lectures we will describe the background on stochastic analysis of the equation, the characteristics of the universality class, and methods through which one is able to obtain exact formulas for one point distributions at finite time.

Speakers

On two deposition models

I discuss properties of two models of stochastic deposition: ballistic and diffusive limited deposition.

Recent progress and open questions in mean field spin glasses

Spin glasses are disordered spin systems originated from the desire of understanding the strange magnetic behaviors of certain alloys in physics. As mathematical objects, they are often cited as examples of complex systems and have provided several fascinating structures and conjectures. This talk will cover the recent progress in the famous Sherrington-Kirkpatrick model. We will focus particularly on the conjectured properties about the functional ordered parameter proposed by G. Parisi thirty years ago and present partial results. In the end, we will introduce the bipartite model and raise open questions along this completely open direction. This talk is mainly based on joint work with A. Auffinger.

Fixed speed competition on the configuration model with infinite variance degrees

We study competition of two spreading colors starting from single sources on the configuration model with i.i.d. degrees following power-law distribution with exponent $\tau\in(2,3)$. In this model two colors spread with a fixed but not necessarily equal speed on the unweighted random graph. We show that if the speeds are not equal, then the faster color paints almost all vertices, while the slower color can paint only a random subpolynomial fraction of the vertices. If the speeds are equal, we believe that there is still no coexistence and the ‘loser’ type paints a polynomial many vertices with a random exponent (less than 1). As a side-result of this case, we obtain the distribution of second-order terms in typical distances in the graph.

This is joint work with Enrico Baroni and Remco van der Hofstad.

Mixing-time and cut-off window for the exclusion process on 1-dimensional graphs

We consider the exclusion process with $k$ particles on the circle or segment of length $N$ (with $k\le N/2$). This is a Markov chain that can be described as follows: $k$ (unlabeled) particles are moving on a graph with the rule that each site can be occupied only by one particle, each particle jump with rate one on each of the neighboring sites, but the jumps are cancelled when a particle tries to jump on a site which is already occupied. The equilibrium state for this dynamics is the uniform measure over all possible particle configuration, and in our talk we want to investigate how much time the system needs to reach equilibrium in terms of total variation distance. We give a sharp answer for both the segment and the circle and discuss the connection with the adjacent transposition shuffle.

Quenched invariance principle for simple random walk on clusters in correlated percolation models

Quenched invariance principle and heat kernel bounds for random walks on infinite percolation clusters and among i.i.d. random conductances in $Z^d$ were proved during the last two decades. The proofs of these results strongly rely on the i.i.d. structure of the models and some stochastic domination with respect to super-critical Bernoulli percolation. Many important models in probability theory and in statistical mechanics, in particular, models which come from real world phenomena, exhibit long range correlations.

In this talk I will present a new quenched invariance principle, for simple random walk on the unique infinite percolation cluster for a general class of percolation models on $Z^d$, $d\ge2$, with long-range correlations. This gives new results for random interlacements in dimension $d\ge3$ at every level, as well as for the vacant set of random interlacements and the level sets of the Gaussian free field in the regime of the so-called local uniqueness (which is believed to coincide with the whole supercritical regime). An essential ingredient of the proof is a new isoperimetric inequality for correlated percolation models.

Maximum independent sets in random $d$-regular graphs

Satisfaction and optimization problems subject to random constraints are a well-studied area in the theory of computation. These problems also arise naturally from investigating the combinatorics of random graphs. While the values of limiting thresholds have been conjectured for many such models, few have been rigorously established. In this context we study the size of maximum independent sets in random $d$-regular graphs. We show that for $d$ exceeding a constant $d_0$, there exist explicit constants $(a,c)$ depending on $d$ such that the maximum size has constant fluctuations around $an - c\log n$, establishing the one-step replica symmetry breaking heuristics developed by statistical physicists. As an application of our method we also prove an explicit satisfiability threshold in random regular $k$-NAE-SAT. This is joint work with Jian Ding and Allan Sly.

Intersection of SLE paths

SLE curves are introduced by Oded Schramm as the candidate of the scaling limit of discrete models. In this talk, we first describe basic properties of SLE curves and their relation with discrete models. Then we summarize the Hausdorff dimension results related to SLE curves, in particular the new results about the dimension of cut points and double points. Third, we introduce imaginary geometry, and from there give the idea of the proof of the dimension results.

Short Talks

Evolutionary games on the lattice: Best-response dynamics

Best-response dynamics is an example of an evolutionary game where players update their strategy in order to maximize their payoff. In this talk, I discuss a stochastic spatial version of this game based on the framework of interacting particle systems in which players are located on an infinite square lattice. In the presence of two strategies, and calling a strategy selfish or altruistic depending on a certain ordering of the coefficients of the underlying payoff matrix, a simple analysis of the nonspatial mean-field approximation of the spatial model shows that a strategy is evolutionarily stable if and only if it is selfish, making the system bistable when both strategies are selfish. The spatial and nonspatial models agree when at least one strategy is altruistic. In contrast, we prove that, in the presence of two selfish strategies, only the most selfish strategy remains evolutionarily stable in one and two dimensions. In higher dimensions, even starting with a high density, the least selfish strategy is unable to completely outcompete the most selfish strategy with again a reduction of the parameter region where both strategies are evolutionarily stable.

Asymptotics of heat equation with large random potentials

A type of heat equations with large, highly oscillatory, random potentials are analyzed by probabilistic approach. Homogenization or convergence to SPDE is derived depending on the correlation properties of the randomness. In the homogenization setting, we further provide a quantitative estimate and prove a central limit result under certain assumptions. The analysis is based on a Feynman-Kac representation, the Kipnis-Varadhan's method, and a quantitative martingale central limit theorem. (Joint work with Guillaume Bal.)

Random walk on the high-dimensional long-range IIC

Critical percolation clusters are known to be finite but large in high dimensions. If we increase the percolation parameter to just above criticality, a single infinite cluster appears. The incipient infinite cluster (IIC) can be thought of as the infinite cluster as it is on the verge of appearing. The IIC locally looks like a critical cluster. In particular, the IIC has a self-similar structure. By studying random walk on a graph, we can study the geometry of that graph. Random walk on the IIC has been studied extensively in recent years. In my talk I will discuss a variant of percolation known as long-range percolation, where edges are present at all length-scales, but the probability of seeing an edge decays as a power-law in the length of the edge. Qualitatively, long-range percolation has all the same features as ordinary percolation, but the presence of very long edges alters the geometry of the percolation graph. In my talk I will discuss the differences and similarities between random walk behaviour and geometry of the long-range percolation IIC and of the ordinary IIC, and I will discuss evidence of a phase transition in the ‘long-range parameter’ that can explain this difference. (Joint work with Remco van der Hofstad and Markus Heydenreich.)

Complete localisation in the parabolic Anderson model

We consider the parabolic Anderson model with Weibull potential field, for all values of the Weibull parameter. We show that the solution is eventually completely localised at a single site with overwhelming probability. This extends the previous best known results in the literature, which only established complete localisation in the parabolic Anderson model in the case where the tail of the potential field was sub-normal. (This is joint work with Artiom Fiodorov.)

Poissonized Robinson-Schensted tableaux

We introduce an object called a decorated Young tableau that slightly extends the notion of a standard Young tableau. This object can equivalently be viewed as a continuous time trajectory of Young diagrams or as a non-intersecting line ensemble. The Robinson-Schensted (RS) correspondence can be extended to a bijection between finite configurations of points in the plane to pairs of decorated Young tableaux of the same shape. By applying this to a Poisson point process in the plane, we get a random pair of decorated Young tableaux, which we called the Poissonized RS Tableaux. By using properties of Young tableaux, we show that the finite dimensional distributions of this random object are a Schur process as introduced by Okounkov and Reshetikhin. We also show that when viewed as a non-intersecting line ensemble, this has the same law as certain Poisson walkers conditioned not to intersect. This allows us to compute asymptotic properties of our model, for example convergence to the Airy 2 process under the correct scaling.

Partial mixing of semi-random transposition shuffles

We show that for any semi-random transposition shuffle on $n$ cards, the mixing time of any given $k$ cards is at most $n\log(k)$, provided $k=o((\frac{n}{\log(n)})^{\frac{1}{2}})$. In the case of the top-to-random transposition shuffle we show that there is cutoff at this time with a window of size $O(n)$, provided further that $k\rightarrow\infty$ as $n\rightarrow\infty$ (and no cutoff otherwise). For the random-to-random transposition shuffle we show cutoff at time $\frac{1}{2}n\log(k)$ for the same conditions on $k$. We prove these results by relating the mixing time of $k$ cards to the mixing of one card. Our results rely heavily on coupling arguments to bound the total variation distance.

Mixing time of the top-swap Markov chain

The top-swap Markov chain was introduced by Durrett as a model for genome rearrangements. It can be viewed as a card-shuffling process with $n$ cards divided into $k$ decks. The cards are ordered within each deck, and the decks are labeled. At each transition we choose a random pair of positions, where a position is a space above or below a card. If the positions are in the same deck we do nothing; otherwise, we cut both decks at the chosen positions and then exchange the tops of the two decks. We obtain a mixing time bound of $O((n+k)\log^8(n+k))$ for the top-swap chain. Previously, the best known bound was $O((n+k)^2\log(n+k))$ which is due to the relaxation time bound proved by Bhatnagar et al (2007). (This is based on joint work in progress with Ben Morris.)

Localization and homogenization in the parabolic Anderson model

The Parabolic Anderson Model is a paradigmatic toy model for motion in disordered media. Concretely, one considers the discrete heat equation with a random potential term representing a disordered environment of sources and sinks. The homogenizing effect of the heat flow competes with the potentially localizing effect of the random environment. This is reflected in the behavior of solutions but also — more abstractly — in the spectrum of the corresponding random Schrödinger operator. A refined picture of this competition can be obtained by considering variants of the problem with rescaled disorder or diffusivity.

Triple collisions of competing Brownian particles

Consider a finite system of particles on the real line. Rank them from bottom to top. Each particle moves as a Brownian motion with drift and diffusion coefficients depending on its current rank. These systems were introduced for financial modeling (Banner, Fernholz, Karatzas, 2005). We find a necessary and sufficient condition to avoid triple collisions.

Inversions and longest increasing subsequence for k-card-minimum random permutations

Begin with a deck of $n$ cards labeled $1,...,n$ and a table with $n$ labeled positions to place cards. Draw a random card from the deck, remove it, and place it in position $1$. Then draw another random card from the remaining set to place in position $2$, another for position  $3$, and so forth. By this procedure one obtains a uniformly random permutation of the integers $1,...,n$: $\sigma = (C_{1},...,C_{n})$ where $C_{t}$ is the random card removed at time $t$. We study a variant of this simple procedure in which $k$ random cards are chosen at each step, and the lowest numbered card is selected. Clearly, the new procedure favors permutations, which are more in order than in the uniform case. That is, closer to the identity permutation $id = (1,2,3,...,n)$. We quantify this effect in terms of two natural measures of order: The number of inversions $I$ and the length of the longest increasing subsequence $L$. For inversions, we establish a weak law of large numbers and central limit theorem, both for fixed and growing $k$. For the longest increasing subsequence, we establish the rate of scaling, in general, and existence of a weak law in the case of growing $k$. We also show that the minimum strategy, of selecting the minimum of the $k$ given choices at each step, is optimal for minimizing the number of inversions in the space of all online $k$-card selection rules.

Uniform spanning tree and bi-Laplacian Gaussian field

We construct a natural discrete random field on a four dimensional ball that converges weakly to the bi-Laplacian Gaussian field in the scaling limit. The construction is based on assigning i.i.d. Bernoulli random variables on each component of the wired spanning forest after removing the boundary vertex, thus defines an associated random function. (Joint work with Greg Lawler and Xin Sun.)