Labels
In the six-root wedge configuration used for the summary statistics below, the starting points are \(x_1=(1,1)\), \(x_2=(2,1)\), \(x_3=(1,2)\), \(x_4=(2,2)\), \(x_5=(3,1)\), and \(x_6=(1,3)\).
Competition Interfaces
This page describes a numerical project on competition interfaces in directed last-passage percolation with multiple nearby roots. One motivating question is whether interfaces with the same asymptotic direction coalesce. The page also introduces finite-size directional statistics of nearby interfaces.
Model
Let \(\{\omega_x\}\) be i.i.d. vertex weights on \(\mathbb{Z}^2\). For lattice points \(x\le y\) in the coordinatewise order, the last-passage value from \(x\) to \(y\) is
Last-passage value
The last-passage value G sub x comma y is the maximum, over all up-right paths from x to y, of the sum of the weights along the path. \[ G_{x,y}=\max_{\pi:x\nearrow y}\sum_{z\in \pi}\omega_z. \]Here the maximum runs over all up-right lattice paths from \(x\) to \(y\). A maximizing path is a geodesic.
When the root is the origin, the set of all geodesics from the origin forms a tree. Each path in this tree from the root to a site is the unique geodesic to that site. Since every such path begins with either the step \(e_1\) or the step \(e_2\), the tree separates into two subtrees: the subtree of points whose geodesic begins with \(e_1\), and the subtree of points whose geodesic begins with \(e_2\). The competition interface is the boundary between those two subtrees. Figure 1 shows this basic picture.
Figure 1. A competition interface
If the competition interface is written as a path \(\gamma=(\gamma_n)\) with \(\gamma_n=(i_n,j_n)\), then its asymptotic direction is encoded by the limit
Asymptotic direction
If gamma sub n equals i sub n comma j sub n, then the asymptotic direction is encoded by the limit of gamma sub n divided by i sub n plus j sub n. Equivalently, both coordinates divided by i sub n plus j sub n converge. \[ \frac{\gamma_n}{i_n+j_n} = \left(\frac{i_n}{i_n+j_n},\frac{j_n}{i_n+j_n}\right) \longrightarrow \xi, \]when this limit exists. Under the differentiability hypothesis for the shape function, competition interfaces have asymptotic directions; this is known rigorously in exponential last-passage percolation.
A common heuristic is that competition interfaces should in some ways behave like infinite geodesics. In exponential last-passage percolation, this is exact for infinite geodesics and for a stationary version of the competition interface.
In the geodesic picture, coalescence means that two geodesic rays with the same asymptotic direction eventually merge and then remain together forever. In exponential last-passage percolation, strict concavity of the shape implies that geodesic rays have asymptotic directions. In interior directions of uniqueness, all geodesic rays with a given asymptotic direction coalesce. In the random directions of non-uniqueness, there are instead two coalescing families, the left-most \(\xi^-\) and right-most \(\xi^+\) geodesics.
Question
In the point-to-point model, interfaces from different roots can have the same asymptotic direction, so it is natural to ask whether they coalesce. That was explored numerically on large finite grids and for several weight distributions.
The simulations show a curious qualitative feature: nearby interfaces often intersect repeatedly without ever coalescing on the observed window. If coalescence does occur, these simulations suggest that it happens in a way that is qualitatively different from the usual geodesic picture.
The multi-interface pictures in Figures 2 and 3 were generated in exponential last-passage percolation with roots at all lattice sites \((i,j)\) satisfying \(i\ge 1\), \(j\ge 1\), and \(i+j\le 7\).
Figure 2. Window 100×100
Figure 3. Window 8000×8000
Previous questions
Alongside the coalescence question, it is natural to look at simple joint statistics of nearby competition interfaces and how they depend on direction and on the weight distribution. The goal here was to get some sense of how joint distributions of competition interfaces depend on the weight distribution. For a labeled starting point \(x_i\), let \(E_i^N=(I_i^N,J_i^N)\) be the point where the associated interface exits an \(N\times N\) box. The associated finite-box first coordinate is
Finite-box first coordinate
For the interface started from x sub i in an N by N box, the exit point is E sub i superscript N equals I sub i superscript N comma J sub i superscript N, and the finite-box first coordinate is varphi sub i superscript N equals I sub i superscript N divided by I sub i superscript N plus J sub i superscript N. \[ E_i^N=(I_i^N,J_i^N), \qquad \varphi_i^N=\frac{I_i^N}{I_i^N+J_i^N}. \]Six-root wedge runs
Parameters
The illustrative values below come from 5000×5000 wedge simulations with 10,000 samples per distribution and tolerance \(\varepsilon=0.01\).
For two starting points \(x_i\) and \(x_j\), the finite-box first coordinates can be compared through three ordering probabilities and one close-to-any probability. The letters \(R\), \(C\), and \(L\) record whether the first coordinate from \(x_i\) lies to the right of, is close to, or lies to the left of the first coordinate from \(x_j\), while \(A_i\) records the probability that the first coordinate from \(x_i\) is close to at least one of the others.
Ordering probabilities
R i j superscript N of epsilon is the probability that varphi i superscript N is greater than varphi j superscript N plus epsilon. C i j superscript N of epsilon is the probability that the absolute difference between varphi i superscript N and varphi j superscript N is at most epsilon. L i j superscript N of epsilon is the probability that varphi i superscript N is less than varphi j superscript N minus epsilon. A sub i superscript N of epsilon is the probability that the minimum over j not equal to i of the absolute difference between varphi i superscript N and varphi j superscript N is at most epsilon. \[ R_{i,j}^N(\varepsilon)=\mathbb{P}\!\left(\varphi_i^N>\varphi_j^N+\varepsilon\right), \qquad C_{i,j}^N(\varepsilon)=\mathbb{P}\!\left(\left|\varphi_i^N-\varphi_j^N\right|\le \varepsilon\right), \] \[ L_{i,j}^N(\varepsilon)=\mathbb{P}\!\left(\varphi_i^N<\varphi_j^N-\varepsilon\right), \qquad A_i^N(\varepsilon)=\mathbb{P}\!\left(\min_{j\ne i}\left|\varphi_i^N-\varphi_j^N\right|\le \varepsilon\right). \]| Distribution | \(R_{1,2}^N\) | \(C_{1,2}^N\) | \(L_{1,2}^N\) | \(A_1^N\) |
|---|---|---|---|---|
| Exp(1) | 0.3747 | 0.4008 | 0.2245 | 0.8221 |
| Normal(0,1) | 0.4069 | 0.3447 | 0.2484 | 0.7729 |
| Uniform(0,1) | 0.4064 | 0.3269 | 0.2667 | 0.7645 |
| LogNormal(0,1) | 0.3190 | 0.4688 | 0.2122 | 0.8675 |
Table 1 records only a few illustrative comparisons from an initial run of exploratory simulations.
Next questions
The next goal of this project is going to be to see whether the sampling code can be refactored so that competition-interface paths of order hundreds of thousands or millions can be simulated, making it possible to check whether the same braiding structure persists at those scales.
Another question is to study fluctuations around the asymptotic direction and to look for their order. Interested students at Purdue with a background in GPU simulation should feel free to send me an e-mail if you are interested in working on this.