AMS Short Course on "Random Growth Models"

This two-day course will take place on Monday and Tuesday, January 2 and 3 in Atlanta, GA, before the Joint Meetings actually begin. It is co-organized by Michael Damron, Georgia Institute of Technology, Firas Rassoul-Agha, University of Utah, and Timo Seppäläinen, University of Wisconsin-Madison. The speakers also include Ivan Corwin, Columbia University; Jack Hanson, CUNY; and Philippe Sosoe, Harvard University.

The objective of the course is to give an overview of recent exciting progress in the study of a class of stochastic growth models called first- and last-passage percolation (FPP and LPP). The issues involve limit shapes, geodesics, and fluctuations.

Stochastic growth models have been studied since the 1960s, and have their roots in theoretical physics and biology. Such systems describe the behavior of growing interfaces, the spread of bacterial colonies, traffic and queues in tandem, and random paths in a random potential. Studies of these models have led to exciting new mathematical phenomena. The order of magnitude of stochastic fluctuations and their limit laws differ from those in the classical Gaussian central limit theorem. Instead we find limit laws from random matrix theory, which is becoming the paradigm for describing complex dependencies. Much progress has been made in a few exactly solvable special cases of the random growth models. Out of this effort has arisen a new distinct subject, integrable probability, with a deep algebraic component. However, thus far the tools of integrable probability apply only in the exactly solvable setting where special structures are present. On the broader class of models, researchers have had success with approaches that combine probability with ideas of functional analytic and geometric nature. Examples include the use of concentration of measure and Busemann functions to study geodesics and prove fluctuation bounds, and curvature bounds in the derivation of the Kardar-Parisi-Zhang (KPZ) scaling relation. The goal of the course is to survey these recent breakthroughs. The course is intended for a broad audience: from graduate students and researchers in probability to mathematicians interested in an introduction to the topic. For a light introduction to the subject, the reader is invited to look forward to the article Random Growth Models that will appear in the October Notices.

Introduction to Random Growth Models (2 lectures)

Michael Damron, Georgia Institute of Technology

Random growth models come from physics and biology and describe for instance the motion of interfaces or the spread of infections. Mathematically, they give interesting examples of non-traditional limiting behavior: whereas independent statistical trials follow Gaussian laws, infection times in growth models can be related to eigenvalues of random matrices, and the Tracy-Widom distribution. Two main examples are first-passage percolation (FPP) and directed last-passage percolation (LPP). In these models, an infection is set on a $d$-dimensional lattice and spreads across edges of this lattice according to nonnegative (random) passage times $(t_e)$ on the edges in FPP, and on the vertices in LPP. In the first case, the infection takes a path of minimal passage time, whereas in the second, it takes a directed path of maximal passage time. An infection started at a site $x$ takes time $T(x,y)$ to infect $y$ and at time $t$, an infection started at the origin has occupied a region $B(t)$ of the lattice.

In this course, we will present some of the main areas of study for these percolation models including existence and properties of limiting shapes, fluctuations and second order behavior for infection times, scaling exponents, connections to Busemann functions from geometry, and exactly solvable systems from integrable probability. These two introductory lectures will focus on basic probability needed for the course, and the first topic above, convergence of the rescaled infected region $B(t)/t$ to a limiting shape $\mathcal{B}$ as $t \to \infty$. This limiting shape $\mathcal{B}$ depends on the distribution of the passage times $(t_e)$, but, due to its being defined using the subadditive ergodic theorem (and not the usual ergodic theorem) it is known explicitly only in a handful of solvable cases. Even basic conjectured properties, such as the shape being nonpolygonal (proved however in LPP) and having differentiable boundary, are generally not verified. However, recently advances have been made characterizing these shapes via variational formulas.

After discussing limiting shapes, we will move to the convergence rate to the limit, and its representation in terms of random and nonrandom errors. These errors are connected to the geometry of optimal infection paths, or geodesics. For example, it is believed that the symmetric difference between $B(t)/t$ and $\mathcal{B}$ has width of order $t^{\zeta-1}$ for a dimension-dependent exponent $\zeta$, whereas the geodesic from $x$ to $y$ should deviate from the straight line connecting these points by $\|x-y\|^{\xi}$ for a related exponent $\xi$, related to $\zeta$ by $\zeta=2\xi-1$.

References

[1] A. AUFFINGER, M. DAMRON and J. HANSON, 50 years of first-passage percolation, arXiv: 1511.03262, 2015.

[2] S. CHATTERJEE, The universal relation between scaling exponents in first-passage percolation, Ann. Math.177 (2013), 1-35. MR3010809.

[3] I. CORWIN, The Kardar-Parisi-Zhang equation and universality class, Random Matrices Theory Appl1 (2012), no. 1,1130001, 76 pp. MR2930377.

[4] T. SEPPÄLÄINEN, Lecture notes on the corner growth model, retrieved from math.wisc.edu/~seppalai/cornergrowthbook/ajo.pdf, 2009.

Infinite Geodesics, Asymptotic Directions, and Busemann Functions

Jack Hanson, The City College of New York

In the model of first-passage percolation (FPP) on the $d$-dimensional lattice, a finite geodesic between vertices $x$ and $y$ is a path from $x$ to $y$ of minimal weight; equivalently, it is an optimizing path for the metric $T(x,y)$. Finite geodesics can also be seen as paths through which the infection spreads in the model's growth process. An infinite geodesic is an infinite path whose finite subpaths are finite geodesics. There are many natural questions about the structure of infinite geodesics, including the number of distinct infinite geodesics, whether they are asymptotically confined to sectors or allowed to backtrack significantly, and whether a doubly infinite geodesic ("bigeodesic'') can exist. These questions are closely related to the properties of finite geodesics between distant points.

Much can be said about these questions under an unproven curvature assumption on the model's limiting shape $\mathcal{B}$,  for instance, that every infinite geodesic has an asymptotic direction. Busemann functions were brought to the model as a tool for proving similar statements under minimal assumptions. Busemann functions allowed the first proof that there exist more than two disjoint infinite geodesics without any unverified assumptions. They also shed light on the questions of directedness and bigeodesics mentioned above, as well as coexistence properties of competing infections.

Generally Busemann functions take the form $B(x,y) = \lim_{k\to\infty} [T(x, z_k) - T(y, z_k)]$ for some sequence $(z_k)$ of lattice points — for instance, the sequence of points lying along an infinite geodesic. $B(x,y)$ encodes the relative favorability of the points $x$ and $y$ for infecting $z_k$ for $k$ large, and so the asymptotic behavior of $B$ governs the regions which geodesics to $(z_k)$ prefer to pass through. We will discuss the limiting behavior of Busemann functions and its relationship to the limiting behavior of geodesics to the points $z_k$. We also will discuss the existence of the limit defining $B$ and techniques for handling these existence questions.

References

[1] A. AUFFINGER, M. DAMRON, and J. HANSON, Limiting geodesics for first-passage percolation on subsets of $\mathbb{Z}^2$, Ann. Appl. Probab. 25 (2015), 373–405. MR3297776

[2] M. DAMRON and J. HANSON, Busemann functions and infinite geodesics in two-dimensional first-passage percolation, Commun. Math. Phys. 325 (2014), 917–963. MR3152744

[3] M. DAMRON and J. HANSON. Bigeodesics in first-passage percolation, preprint 2015, arXiv:1512.00804.

[4] O. GARET and R. MARCHAND,  Coexistence in two-type first-passage percolation models, Ann. Appl. Probab 15 (2005), 298–330. MR2115045

[5] O. HÄGGSTRÖM and R. PEMANTLE, First passage percolation and a model for competing spatial growth, J. Appl. Probab35 (1998), 683–692. MR1659548

[6] C. HOFFMAN, Coexistence for Richardson type competing spatial growth models, Ann. Appl. Probab.15 (2005), 739–747. MR2114988

[7] C. HOFFMAN, Geodesics in first passage percolation, Ann. Appl. Probab.18 (2008), 1944–1969. MR2462555

[8] C. LICEA and C. M. NEWMAN, Geodesics in two-dimensional first passage percolation, Ann. Probab24 (1996), 399–410. MR1387641

[9] C. M. NEWMAN, A surface view of first passage percolation, Proceedings of the International Congress of Mathematicians Vol 1, 2 (Zürich, 1994)pp.1017–1023, 1995. MR1404001

[10] C. M. NEWMAN and M. S. T. PIZA, Divergence of shape fluctuations in two dimensions, Ann. Probab 23 (1995), 977–1005. MR1349159

Concentration in First-Passage Percolation

Philippe Sosoe, Harvard University

In first-passage percolation (FPP) the passage time from the origin to vertex $x$ is defined as $T(0,x)=\min_\gamma \sum_{e\in\gamma} t_e$, the minimal passage time of paths $\gamma$ that connect $0$ to $x$. $t_e$ is the random passage time attached to edge $e$ of the lattice. The order of the fluctuations of $T(0,x)$ for $\|x\|_1\gg 1$ has been the subject of intense investigation. It is believed that the variance of the passage time grows as $\|x\|_1^{2\zeta}$, for some $\zeta>0$. In two dimensions, the exponent $\zeta$ is expected to be typical of the Kardar-Parisi-Zhang (KPZ) universality class: $\zeta=1/3$. This relation has been confirmed rigorously for some special models of last passage percolation, but it remains mysterious in the case of first-passage percolation. In general dimension the fluctuations are even less understood. There are no widely accepted conjectures for the value of the exponent $\zeta$ that governs the growth of the variance, or for its behavior as the dimension increases to infinity. In addition, little is known about lower bounds for the variance.

This lecture discusses known bounds on the order of the fluctuations in FPP in $\mathbb{Z}^d$, for general dimension $d$, focusing on variants of two main results: first, exponential concentration on a linear scale for the passage times, as was proved by Kesten. This was later improved to Gaussian concentration by Talagrand using his theory of concentration of measure. After reviewing some basic probabilistic tools, we will explain how Kesten and Talagrand's results now follow from standard methods in concentration inequalities.

Second, we will present an upper bound of order $\|x\|_1/\log \|x\|_1$ for the variance of $T(0,x)$. Such a bound was first derived by Benjamini, Kalai and Schramm (BKS) for Bernoulli edge weights. The BKS result was generalized to other edge weight distributions, first by Benaim-Rossignol, and then by Damron, Hanson, and Sosoe.

Although it is expected to be far from the truth, this sublinear upper bound remains the best known to date. We will explain how it follows by supplementing standard concentration results with the key observation from the original BKS paper that individual edge weight variables have small influence on the overall passage time.

References

[1] H. KESTEN, On the speed of convergence in first-passage percolation, Ann. Appl. Probab. 3 (1993), 296-338. MR1221154

[2] I. BENJAMINI, G. KALAI, and O. SCHRAMM, First passage percolation has sublinear distance variance, Selected Works of Oded Schramm, Springer, New York, 2011. Originally appeared in Ann. Probab.31 (2003) 1970-1978. MR2883392

[3] M. DAMRON, J. HANSON, and P. SOSOE, Sublinear variance in first-passage percolation for general distributions, Probab. Theory Related Fields 163 (2015), 223-258. MR3405617

[4] M. DAMRON, J. HANSON, and P. SOSOE, Subdiffusive concentration in first-passage percolation, Electron. J. Probab. (2014) 19, no. 109, 27 pp. MR3286463

Busemann Functions, Geodesics, and the Competition Interface for Directed Percolation

Firas Rassoul-Agha, University of Utah

In the planar directed last-passage percolation model (LPP) independent and identically distributed random weights $\omega_x$ are put on the vertices of the square lattice. Only paths that take up or right steps are considered. The weight (or passage time) of a path $\gamma$ is the sum of the weights at the sites it traverses: $T(\gamma)=\sum_{x\in\gamma}\omega_x$. The last-passage time $T(x,y)=\max_\gamma T(\gamma)$ from $x$ to $y$ is the maximal passage time of all up-right paths connecting $x$ and $y$. A path between $x$ and $y$ is a geodesic if it has maximal weight. Directed LPP has the advantage over undirected FPP that in the planar case there are exactly solvable cases that provide a window to the deeper properties of the entire class of models.

Several different much-studied stochastic models can be formulated in this last-passage language: (i) the corner growth model which is a randomly growing cluster on the lattice, (ii) queues in series, and (iii) one of the most fundamental interacting particle systems, namely TASEP, or the totally asymmetric simple exclusion process. By letting two infections from different seeds compete for space, the growth model can be turned into a model of competition.

In this talk we show how the Busemann function limit can be proved with the help of results from queueing theory. As it is the case for first-passage percolation, these Busemann functions carry information about the large scale behavior of the system. They provide equations for the limiting shape function $g(x)=\lim_{n\to\infty}n^{-1}T(0,nx)$ and can be used to prove existence, uniqueness, and coalescence of geodesics under mild regularity assumptions on the limiting shape. Busemann functions can also be used to study the interface between the two growing infections.

The special solvable case is the one whose vertex weights are exponentially or geometrically distributed. Then the probability distribution of the Busemann functions becomes fairly explicit. This leads to a number of precise results, such as closed-form expressions for the limit shape function $g$ and for the limiting angle of the competition interface.

References

[1] E. CATOR and L. P. R. PIMENTAL, Busemann functions and equilibrium measures in last passage percolation models, Probab.Theory Relat. Fields154 (2012), no.1-2, 89–125. MR2981418

[2] E. CATOR and L. P. R. PIMENTAL, Busemann functions and the speed of a second class particle in the rarefaction fan, Ann. Probab. 41 (2013), no. 4, 2401–2425. MR3112921

[3] P. A. FERRARI and L. P. R. PIMENTAL, Competition interfaces and second class particles, Ann. Probab 33 (2005)no. 4, 1235–1254. MR2150188 (2006e:60141)

[4] N. GEORGIOU, F. RASSOUL-AGHA, and T. SEPPÄLÄINEN,  Stationary cocycles and Busemann functions for the corner growth model,  Probab. Theory Relat. Fields (2016), 1-46.

[5] N. GEORGIOU, F. RASSOUL-AGHA, and T. SEPPÄLÄINEN, Geodesics and the competition interface for the corner growth model, Probab.Theory Relat. Fields (2016), 1-33.

[6] C. LICEA and C. M. NEWMAN, Geodesics in two-dimensional first-passage percolation, Ann. Probab. 24 (1996), no. 1, 399–410. MR1387641

[7] J. MAIRESSE and B. PRABHAKAR, The existence of fixed points for the ·/GI/1 queue, Ann. Probab. 31 (2003), no. 4, 2216–2236. MR2016617

Stationary Versions and Fluctuation Exponents for Exactly Solvable Models

Timo Seppäläinen, University of Wisconsin-Madison

The planar random growth models discussed in this course are expected to be members of the Kardar-Parisi-Zhang (KPZ) universality class. This means that on large scales the stochastic fluctuations of these systems obey the same laws, regardless of the particular details of the models, as long as the random passage times out of which the models are built do not behave too wildly. At the crudest level we measure the order of magnitude of fluctuations in terms of fluctuation exponents relative to the size of the system. To take a basic example, let $S_n=X_1+\dotsm+X_n$ be a random walk with independent and identically distributed, mean zero increments $X_k$. Then the mean square of $S_n$ satisfies $E(S_n^2)=n\cdot E(X_1^2)$. Thus on average $S_n$ grows at rate $n^{1/2}$, in other words, the fluctuation exponent is 1/2.

The KPZ class has different exponent values: the passage time $T(0, nx)$ is expected to have fluctuations of order $n^{1/3}$, and the distance at which spatial correlations occur is supposed to be of order $n^{2/3}$. At the level of genuine universality this remains a mathematical conjecture. However, among directed growth models in two dimensions there are special exactly solvable ones where fortuitous coincidences of combinatorics and probability permit rigorous derivation of these exponents. The oldest such is the corner growth model with exponentially distributed passage times on the lattice vertices. One manifestation of the exact solvability is the existence of tractable stationary versions of the models. Stationarity means that the probability laws are suitably invariant under lattice translations. Stationarity allows us to capture long-term behavior.

The exponent 2/3 appears when we ask about the fluctuations of the geodesics. Macroscopically, at the level of deterministic law of large numbers limits, the optimal path from $0$ to $x$ is a straight line. At the microscopic level, the optimal random path from $0$ to $nx$ is expected to fluctuate in a band of width of order $n^{2/3}$ around its straight line limit. This also we can partially prove in exactly solvable models.

References

[1] M. BALÁZS, E. CATOR, and T. SEPPÄLÄINEN, Cube root fluctuations for the corner growth model associated to the exclusion process, Electron. J. Probab. 11 (2006), no. 42, 1094–1132 (electronic). MR2268539

[2] A.-L. BARABÁSI and H. E. Stanley, Fractal concepts in surface growth, Cambridge University Press, 1995. MR1600794

[3] E. CATOR and P. GROENEBOOM, Second class particles and cube root asymptotics for Hammersley's process, Ann. Probab. 34 (2006), no. 4, 1273–1295. MR2257647

[4] I. CORWIN,  Kardar-Parisi-Zhang universality, Notices Amer. Math. Soc. 63 (2016), no. 3, 230–239. MR3445162

[5] T. SEPPÄLÄINEN, Scaling for a one-dimensional directed polymer with boundary conditions, Ann. Probab. 40 (2012), no. 1, 19–73. MR2917766.  Corrected version available at http://arxiv.org/abs/0911.2446.

KPZ Fluctuations in Exactly Solvable Models

Ivan Corwin, Columbia University

Some random growth models admit concise and exact formulas describing expectations of various observables of interest. These models and their solvability spring from certain algebraic structures such as representation theory and quantum integrable systems. By studying these examples, we are able to gain predictions for the universal behaviors of a much wider class of random growth models, the so-called Kardar-Parisi-Zhang (KPZ) universality class.

We will touch on some of the models discussed earlier in the short course and on some new ones, such as directed last-passage percolation, positive temperature directed polymers, the (totally) asymmetric simple exclusion process, the KPZ stochastic partial differential equation, and some others. We sketch a proof of the asymptotic fluctuation scaling and statistics for one of these models and indicate how this generalizes to the broader class.

References

[1] A. BORODIN and V. GORIN, Lectures on integrable probability, Probability and Statistical Physics in St. Petersburg, V. Sidoravicius and S. Smirnov, eds.,  AMS Proceedings of Symposia in Pure Mathematics, vol. 91, 2016. arXiv:1212.3351

[2] I. CORWIN, Kardar-Parisi-Zhang universality. Notices Amer. Math. Soc. 63 (2016), no. 3, 230-239. MR3445162

[3] I. CORWIN, Macdonald processes, quantum integrable systems and the Kardar-Parisi-Zhang universality class, Proceedings of the 2014 ICM. arXiv:1403.6877.

[4] I. CORWIN, The Kardar-Parisi-Zhang equation and universality class, Random Matrices Theory and Appl1 (2012), no. 1, 1130001, 76 pp. MR2930377

Registration

There are separate fees to register for this Short Course. Advanced registration fees for members are US\$112; nonmembers are US\$170; and students/unemployed or emeritus members are US\$60. These fees are in effect until December 20, 2016. If you choose to register on-site, the fees for members are US\$146; nonmembers are US\$200, and students/unemployed or emeritus members are US\$81. Advanced registration started on September 12, 2016. On-site registration will take place on Monday, January 2, 2017, at a location to be announced.

Top