Research

Summary of interests

1. The limit shape of first-passage percolation, and stochastic homogenization of Hamilton-Jacobi equations.
2. Directed polymers, KPZ universality and limiting fluctuations.
3. Geodesic dynamics. An ergodic theoretic approach to analyzing geodesic behavior.
4. Properties of Busemann functions in first- and last-passage percolation
5. The concentration of measure phenomenon.
6. The combinatorics involved in the last-passage percolation model.

Longer description of my research

My research centers around a classical problem in probability called first-passage percolation, which is a simple model that has deep connections to several areas of mathematics including number theory, representation theory, and combinatorics. It was originally inspired by the following physical problem:

Consider a fluid exploring a porous medium like a slab of pumice or sandstone. The rock has little tunnels of various sizes through which a liquid like water can seep through. The speed at which water can percolate depends on the size of the tunnel: the larger it is, the faster it can flow. Assuming that tunnels and sizes are randomly distributed throughout the medium, how long does it take for water to go from one end of the slab to the other? More generally, how does the water explore the random medium? What does the interface between the explored and unexplored tunnels look like? Could such a problem have anything to do with the zeros of the Riemann zeta function?

I study various aspects of this problem using techniques from analysis and partial differential equations, ergodic theory and combinatorics. These aspects can broadly be divided into three parts:

1. The variational formula and the limit shape.
2. Universal limiting fluctuations
3. Geodesic Dynamics

A discrete mathematical idealization of this “fluid percolation in a random medium” problem was introduced by Hammersley and Welsh (1965). I will describe a version of the model on the square lattice $\mathbb{Z}^d$. The random porous medium is described by a set of nonnegative weights attached to the nearest-neighbor edges of the lattice. The edges of the lattice represent the tunnels the fluid can flow through, and the weights represent the size of the tunnel. The weights can be chosen independently for each edge from a common distribution, or more generally, the medium can be assumed to be stationary and ergodic. Suppose a fluid goes from point $x$ to point $y$ on the lattice along a path $\gamma$. This path can be described by a sequence of nearest-neighbor vertices, and the total time that the fluid takes to traverse this path is the sum of the edge-weights it encounters. Suppose fluid is released at the origin in a constant stream. The way the fluid explores the medium as a function of time is illustrated in the following figure.

If the fluid is released from $x$ at time $0$, the first time that the fluid reaches point $y$, is the time taken by the fluid to traverse the best path; i.e., the path with the smallest weight. Precisely, the first-passage time $T(x,y)$ is defined as the infimum over all paths from $x$ to $y$ of the time for each path. It is not so hard to see that $T(x,y)$ satisfies the triangle inequality, and therefore, is a random metric on the lattice. The way in which the fluid explores the medium can be completely described by this function $T(x,y)$. Let $B_t = \{ x \in \mathbb{Z}^2 \colon T(0,x) \leq t \}.$ This random set of lattice sites are those that have been reached by the fluid by time $t$. Clearly $B_t$ is growing; it is not so difficult to see that the rate of growth in all directions is approximately linear. Then the first question that one asks is the following:

Is there a subset $B_0 \subset \mathbb{R}^2$, such that for any $\epsilon> 0$, we have for large enough time $t$ $(1 - \epsilon) B_0 \subset \frac{B_t}{t} \subset (1 + \epsilon) B_0 \, ?$

In other words, is there a deterministic, convex set $B_0$ that describes the asymptotic rate of growth of the set of explored sites? This is the first major question that was asked about the model, and the existence of such a set $B_0$ was established by Kingman (1968) nearly 50 years ago. For each $x \in \mathbb{R}^d$, Kingman established the existence of the deterministic limit

called the limit shape of first-passage percolation. However, where $[x]$ is a nearest lattice point to $x$. The function $g(x)$ is a norm on $\mathbb{R}^d$, and one can show that its level set (a deterministic curve) $\{ x \colon g(x) = 1 \}$ is the limit shape $B_0$. $B_0$ is therefore Kingman’s theorem is not constructive and therefore very little is known about the limit shape: establishing any nontrivial qualitative formula is pretty mysterious, and understanding its various properties properties of $B_0$ has remained an almost completely open problem this past 50 years. In my PhD thesis on the limit shape of first-passage percolation, I derived a new formula for the limit shape $B_0$. The is a major part of my research.

Related papers

1. Krishnan (2014), PhD Thesis.
2. Krishnan (2016), in Comm. Pure. Appl. Math.

To read an earlier post about the variational formula, click here

Universal Fluctuations

The following figure shows the microscale fluctuations of the random shape of occupied sites around the limit shape. The second natural question to ask is the following: How does one describe the random fluctuations of the shape around the limit shape?

Describing the random fluctuations of a shape is quite a hard problem in probability, and so it is easier to consider the directional fluctuations of the shape. In terms of the first-passage time, for fixed $x \in \mathbb{R}^2$, we wish to determine the properties of the second order asymptotic: $T(0,[nx]) \approx n g(x) + X n^{\chi}$ where $\chi$ describes the scale of the fluctuations, and the random variable $X$ describes the probability distribution of the fluctuation.

Typically one sees Gaussian fluctuations in the second order behavior of many, many, different kinds of random processes. Suppose $\{X_i\}_{i=0}^{\infty}$ are independent identically distributed (iid) random variables with mean $\mu$ and variance $\sigma^2$, and let $S_n = \sum_{i=1}^n X_i$. Then the central limit theorem states that

where $X$ is a standard Gaussian random variable. The appearance of the Gaussian distribution is independent of the random variables $X_i$, and so is the scale of fluctuations $\sqrt{n}$. In other words, both the scale and distribution of the random second order behavior of $S_n$ are universal. We will call both the scale and distribution “Gaussian” for short, although one usually calls the scaling diffusive.

So it is natural to ask if the scale and probabilistic properties of the second-order behavior of $T(0,[nx])$ is also Gaussian, and if it is, is it universal? However, neither the scale nor distribution of the fluctuations here are Gaussian. In fact, the following is expected to be true in great generality:

where $F_2$ is the cumulative distribution function of the Tracy-Widom GUE distribution (Tracy and Widom 1994). $F_2(t)$ is usually written in terms of a solution $u(x)$ of the Painlevé II differential equation as follows:

This distribution appears in several seemingly unrelated areas, the most famous of which include: 1) random matrices and 2) zeros of the Riemann zeta function.

Random Matrices: Take complex valued iid Gaussian random variables $\{X_{ij}\}_{1 \leq i \leq j \leq N}$ in the top half of an $N \times N$ matrix and Hermitize it; i.e., set $X^*_{j i} = X_{ij}$ for $j > i$, where $x^*$ represents the complex conjugate of $x$. This ensemble (or probability measure) on random matrices is called the Gaussian Unitary Ensemble (GUE) since the measure is invariant under conjugation by unitary matrices. Hermitian matrices under this measure have distinct real eigenvalues $\lambda_1 < \ldots < \lambda_N$ with probability $1$. Tracy and Widom’s famous theorem (Tracy and Widom 1994) says that the largest eigenvalue has the following second-order asymptotic fluctuations:

This was the context in which $F_2(t)$ was originally discovered. The distribution is universal in the sense that it is independent of the distribution of the $X_{ij}$: they can be Uniform, Gaussian, Gamma, etc., and as long as the random variables are properly centered and scaled, \eqref{eq:convergence of largest eigenvalue to tracy widom law} holds. One can also consider the limiting two-point correlation function:

where the eigenvalues have been scaled and centered ($\widetilde{\lambda_i} = c (\lambda_i - \mu)$) so that $\mathbb{E}[ \# \{ \widetilde{\lambda_i} \text{ per unit interval} \} ] = 1$. It turns out that $R(a,b)$ exists and is universal as well:

Wigner originally introduced random matrix theory to model neutron scattering spectra of heavy atoms. Indeed, all heavy enough atoms have neutron scattering spectra that have statistics that are nearly identical to those of a GUE random matrix (Mehta 2004). This is a real, physical manifestation of the universality of random matrices.

There is a famous story about the two-point correlation function in Random Matrix Theory. In the early 70’s, H. Montgomery assumed the Riemann hypothesis and rescaled the imaginary parts of the nontrivial zeros $\{\frac12 + i \gamma_j\}$ as $\gamma_j \to \widetilde{\gamma_j} = \dfrac{ \gamma_j \log \gamma_j }{2 \pi}$ such that they have mean spacing $1$; i.e.,

Montgomery showed (modulo certain restrictions) that the analog of \eqref{eq:two point correlation function for GUE matrix} for the $\widetilde{\gamma_j}$ exists, and computed its form (Montgomery 1973). Since he was a number theorist, he was unaware of the developments in random matrix theory at the time. Montgomery was advised to show his result to Freeman Dyson (one of the early pioneers of random matrix theory) at the Institute for Advanced Study. Before Montgomery could describe result, Dyson guessed its correct form, and it turned out to be exactly the same as the pair correlation function in GUE random matrices $\eqref{eq:two point correlation function}$.

In random matrix models, a lot of progress has been made in the direction of universality (Tao and Vu 2011; Erdős, Schlein, and Yau 2011), and it is essentially considered to be a solved problem. However, in growth models like first-passage percolation, little progress has been made towards describing even the scale of fluctuations in any generality. Here, there are a handful of peculiar examples —the so-called solvable or integrable models– where it can be shown that the Tracy-Widom GUE distribution describes the limiting fluctuations. One famous example is the problem of longest increasing subsequences in the symmetric group, and another is last-passage percolation with exponential or geometric weights. In last-passage percolation, one defines a last-passage time $G(x,y)$ which is the direct analog of the first-passage time $T(x,y)$: It is the maximal weight or time of lattice paths between $x$ and $y$ that are restricted to only go “up and right” on $\mathbb{Z}^2$.

J. Quastel and I considered a “positive temperature” version of last-passage percolation called the random polymer model. Here, instead of looking for the maximal time between two points $x$ and $y$, one puts a measure on paths between $x$ and $y$ that are weighted towards the paths that have maximal time. Precisely, if a path $\gamma$ has weight $W(\gamma)$, then it has measure proportional to $\exp( \beta W(\gamma) )$. The partition function is defined as $Z(x,y) = \sum_{\gamma_{x,y}} \exp( \beta W(\gamma_{x,y}) )$. Here $\beta$ plays the role of a quantity called the “inverse temperature”. As $\beta \to \infty$, $\beta^{-1} \log Z(0,[n x])$ converges to the last passage time $T(0,[nx])$, and this is the reason the polymer model is considered to be a regularized version of last-passage percolation. We showed that the fluctuations of $\log Z(0,[n x])$ converge to the Tracy-Widom GUE law $\eqref{eq:form of tracy widom gue distribution}$ in a special range of parameters for $\beta$, and that this convergence happened for a large class of weights (universality).

Read an earlier post about this problem here

Related Papers

1. Krishnan and Quastel ( 2016), Ann. Appl. Prob.

Geodesics Dynamics

Since $T(x,y)$ is a random metric on the lattice, one can study the behavior of its geodesics. A geodesic is a path that minimizes the passage-time between every pair of points on the path. Newman (1995) asked the following question:

Let us suppose we have iid weights in first-passage percolation, and let us suppose the weights have continuous distribution. Then, one can consider the tree of semi-infinite geodesics passing through the origin since loops cannot be formed by geodesics (this would contradict the assumption of continuous distribution). How many “ends” does this infinite tree have?

It turns out that this question is closely related to regularity properties of the time-constant $g(x)$. Recent progress on this question has shown that each differentiable segment of the limiting ball $B_0$ is associated with an “end” of this geodesic tree (Damron and Hanson 2014; Georgiou, Rassoul-Agha, and Seppäläinen 2015; Ahlberg and Hoffman 2016).

It is quite easy to show that there is at least one semi-infinite geodesic from the origin. However, it is not quite clear that if doubly-infinite (backwards and forwards) geodesics exist (see (Kesten 1986)). Newman (1995) showed a remarkable correspondence between the existence of bigeodesics in first-passage percolation and the existence of infinite non-constant ground states in the disordered ferromagnetic Ising model. The existence of nonconstant ground states is an important open question in this field. Some progress has been made appropriately differentiable in a given direction $\xi$, several groups have shown that there are no bigeodesics in the direction $\xi$ (Damron towards this question: Assuming that the limit-shape $B_0$ is and Hanson 2014; Ahlberg and Hoffman 2016). However, all of these results depend strongly on the weights being independent and on assuming that the time-constant is differentiable.

J. Chaika and I took an abstract, ergodic theoretic approach to this problem. We considered general stationary measures on path trees on the lattice (modeling geodesics), and asked about their overall collective behavior: Do paths coalesce? Can bigeodesics exist? Can there be a forest consisting of trees of coalescing geodesics?

Here is a simple version of the model: Consider a field of arrows $\{e_1,e_2\}^{\mathbb{Z}^2}$ on the two-dimensional lattice chosen from a translation covariant (stationary) measure $\mathbb{P}$. We can form semi-infinite walks from each point $z \in \mathbb{Z}^2$ by “following the arrows”. In other words, we have a discrete stationary vector field on $\mathbb{Z}^2$, and we consider its integral curves. This induces a stationary measure on semi-infinite walks $\{\mathscr{X}_{z}\}_{z \in \mathbb{Z}^2}$. We call this a stationary family of compatible walks because once walks meet, they coalesce.

Suppose $\mathbb{P}$ is the product measure on $\{e_1,e_2\}$. Consider any two random walks starting at $x \textrm{ and }y$ on an anti-diagonal of the form $\{ z \colon z_1 + z_2 = c\}$. The projection of the difference $\left(\mathscr{X}_{x}(\omega,k) - \mathscr{X}_{y}(\omega,k)\right)\cdot(-1,1)$ is a one-dimensional simple random walk where time proceeds along the main diagonal in $\mathbb{Z}^2$. The $k^{th}$ step of the walk involves arrows on the line $\{ z \colon z_1 + z_2 = c + k-1\}$. Unless the two walks have coalesced previously, the $k$^th^ step is independent of the previous steps, takes the values $\pm2$ with equal probability $p(1-p)$, and is $0$ otherwise. Hence $\left( \mathscr{X}_{x} - \mathscr{X}_{y} \right)\cdot(-1,1)$ is almost surely recurrent to $0$, and the walks must coalesce. Thus, every pair of walks from points $x,y \in \mathbb{Z}^2$ must coalesce almost surely. In contrast, the periodic system in the following figure (also a measure-preserving ergodic $\mathbb{Z}^2$ system) has bi-infinite trajectories.

We proved the following theorem about stationary families of compatible walks:

In $\mathbb{Z}^2$, suppose we have a positive density of walks (satisfying mild conditions in the general case when all four arrows $\{\pm e_1, \pm e_2\}$ are possible). Then, there are only two possible behaviors:

1. the walks from all $x,y \in \mathbb{Z}^2$ coalesce, and no bi-infinite trajectories exist, or

2. a positive fraction of the walks in a configuration form bi-infinite trajectories that are themselves measure-preserving dynamical systems. Thus, all the walks have the same asymptotic direction, and no two bi-infinite trajectories coalesce. In fact, all other trajectories must eventually coalesce with bi-infinite trajectories.

This abstract theorem classifies all possible behaviors of families of compatible geodesics in $d=2$, for both first- and last-passage percolation. Such compatible families of geodesics are closely related to Busemann functions in first- and last-passage percolation. We will say a tiny bit more about Busemann functions in a later section. At this stage, it is enough to say that they are important objects that can be used to describe the regularity of the time-constant and aspects of the fluctuations of $T(0,[nx])$.

In addition to this theorem, we provide examples of compatible walks where we have almost sure coalescence but no asymptotic direction. This example has been taken up with enthusiasm by the “continuum homogenization” community, and is used as a source of counterexamples for commonly used hypotheses there (Bakhtin and Li 2018).

J. Chaika and I are studying various entropic properties of these systems in this (2019 preprint).

Related Papers

1. Krishnan and Chaika (2016), Prob. Theor. Rel. Fields
2. Krishnan and Chaika (2019), arxiv preprint.

Ongoing Projects

1. Representation Theory and the Corner Growth Model (with S. Mkrtchyan)
2. Geodesic Lengths and the Steele-Zhang conjecture (with F. Rassoul-Agha and T. Seppalainen)
3. Busemann functions and their correlations (with Ian Alevy)
4. Kostka numbers, longest increasing subsequences and noncrossing matchings (with Scott Neville)
5. Bigeodesics in first- and last-passage percolation. (with Jack Hanson)

References

Ahlberg, D., and C. Hoffman. 2016. "Random coalescing geodesics in first-passage percolation." *ArXiv E-Prints*, September.

Aldous, D., and P. Diaconis. 1995. "Hammersley's Interacting Particle Process and Longest Increasing Subsequences." *Probability Theory and Related Fields* 103 (2): 199--213. <https://doi.org/10.1007/BF01204214>.

Baik, Jinho, Percy Deift, and Kurt Johansson. 1999. "On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations." *J. Amer. Math. Soc.* 12 (4): 1119--78. <https://doi.org/10.1090/S0894-0347-99-00307-0>.

Bakhtin, Yuri, and Liying Li. 2018. "Weakly Mixing Smooth Planar Vector Field Without Asymptotic Directions." *arXiv:1808.05544 [Math]*, August. <http://arxiv.org/abs/1808.05544>.

Chaika, Jon, and Arjun Krishnan. 2018. "Stationary Coalescing Walks on the Lattice." *Probability Theory and Related Fields*. <https://doi.org/https://doi.org/10.1007/s00440-018-0893-2>.

---------. 2019. "Stationary Coalescing Walks on the Lattice II: Entropy." *arXiv:1909.04816 [Math]*, September. <http://arxiv.org/abs/1909.04816>.

Damron, Michael, and Jack Hanson. 2014. "Busemann Functions and Infinite Geodesics in Two-Dimensional First-Passage Percolation." *Comm. Math. Phys.* 325 (3): 917--63. <https://doi.org/10.1007/s00220-013-1875-y>.

Erdős, László, Benjamin Schlein, and Horng-Tzer Yau. 2011. "Universality of Random Matrices and Local Relaxation Flow." *Invent. Math.* 185 (1): 75--119. <https://doi.org/10.1007/s00222-010-0302-7>.

Georgiou, Nicos, Firas Rassoul-Agha, and Timo Seppäläinen. 2015. "Geodesics and the Competition Interface for the Corner Growth Model." *arXiv:1510.00860 [Math]*, October. <http://arxiv.org/abs/1510.00860>.

Hammersley, J. M., and D. J. A. Welsh. 1965. "First-Passage Percolation, Subadditive Processes, Stochastic Networks, and Generalized Renewal Theory." In *Proc. Internat. Res. Semin., Statist. Lab., Univ. California, Berkeley, Calif*, 61--110. New York: Springer-Verlag. <http://www.ams.org/mathscinet-getitem?mr=0198576>.

Johansson, Kurt. 1998. "The Longest Increasing Subsequence in a Random Permutation and a Unitary Random Matrix Model." *Math. Res. Lett.* 5 (1-2): 63--82. <https://doi.org/10.4310/MRL.1998.v5.n1.a6>.

Kesten, Harry. 1986. "Aspects of First Passage Percolation." In *École d'été de Probabilités de Saint-Flour, XIV---1984*, 1180:125--264. Lecture Notes in Math. Springer, Berlin. <http://www.ams.org/mathscinet-getitem?mr=876084>.

Kingman, J. F. C. 1968. "The Ergodic Theory of Subadditive Stochastic Processes." *Journal of the Royal Statistical Society. Series B. Methodological* 30: 499--510. <http://www.ams.org/mathscinet-getitem?mr=0254907>.

Krishnan, Arjun. 2014. *Variational Formula for the Time-Constant of First-Passage Percolation*. ProQuest LLC, Ann Arbor, MI. <http://arxiv.org/abs/1406.1108>.

---------. 2016. "Variational Formula for the Time Constant of First-Passage Percolation." *Comm. Pure. Appl. Math.* 69 (10). Wiley-Blackwell: 1984--2012. <https://doi.org/10.1002/cpa.21648>.

Krishnan, Arjun, and Jeremy Quastel. 2018. "Tracy--Widom Fluctuations for Perturbations of the Log-Gamma Polymer in Intermediate Disorder." *Ann. Appl. Probab.* 28 (6): 3736--64. <https://doi.org/10.1214/18-AAP1404>.

Licea, Cristina, and Charles M. Newman. 1996. "Geodesics in Two-Dimensional First-Passage Percolation." *Ann. Probab.* 24 (1): 399--410. <https://doi.org/10.1214/aop/1042644722>.

Logan, B. F., and L. A. Shepp. 1977. "A Variational Problem for Random Young Tableaux." *Advances in Math.* 26 (2): 206--22. <https://doi.org/10.1016/0001-8708(77)90030-5>.

Mehta, Madan Lal. 2004. *Random Matrices*. Third. Vol. 142. Pure and Applied Mathematics (Amsterdam). Elsevier/Academic Press, Amsterdam.

Montgomery, H. L. 1973. "The Pair Correlation of Zeros of the Zeta Function." In *Analytic Number Theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972)*, 181--93.

Newman, Charles M. 1995. "A Surface View of First-Passage Percolation." In *Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994)*, 1017--23. Basel: Birkhäuser. <http://www.ams.org/mathscinet-getitem?mr=1404001>.

Okounkov, Andrei, and Anatoly Vershik. 1996. "A New Approach to Representation Theory of Symmetric Groups." *Selecta Math. (N.S.)* 2 (4): 581--605. <https://doi.org/10.1007/PL00001384>.

Seppäläinen, Timo. 1996. "A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences." *Electron. J. Probab.* 1: no. 5, approx.51 pp. <https://doi.org/10.1214/EJP.v1-5>.

Soshnikov, Alexander. 1999. "Universality at the Edge of the Spectrum in Wigner Random Matrices." *Comm. Math. Phys.* 207 (3): 697--733. <https://doi.org/10.1007/s002200050743>.

Tao, Terence, and Van Vu. 2011. "Random Matrices: Universality of Local Eigenvalue Statistics." *Acta Math.* 206 (1): 127--204. <https://doi.org/10.1007/s11511-011-0061-3>.

Tracy, Craig A., and Harold Widom. 1994. "Level-Spacing Distributions and the Airy Kernel." *Comm. Math. Phys.* 159 (1): 151--74. <http://projecteuclid.org/euclid.cmp/1104254495>.

Veršik, A. M., and S. V. Kerov. 1977. "Asymptotic Behavior of the Plancherel Measure of the Symmetric Group and the Limit Form of Young Tableaux." *Dokl. Akad. Nauk SSSR* 233 (6): 1024--7.