MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the last passage percolation model on $\mathbb{Z}^2$ with, say, geometric weights on each edge. By a landmark result of Johansson (, we know that if $T_n(\alpha)$ is the passage time (or distance) between the origin and the point of coordinates $(\alpha n, n)$, then $$ \frac{T_n(\alpha) - \omega(\alpha) n}{\sigma(\alpha)n^{1/3}}\to X, $$ where $X$ has the Tracy-Widom distribution. Here $\omega(\alpha), \sigma(\alpha)$ are two constants whose value is known and is not important for this question.

I am interested in the following natural question:

Q1) Given $\alpha, \beta$, and letting $\gamma_n(\alpha)$ denote the geodesic between 0 and $(\alpha n, n)$, how many edges do $\gamma_n(\alpha)$ and $\gamma_n(\beta)$ share?

Intuitively, one possible way to approach this question is to first ask

Q2) How big is the covariance between between $T_n(\alpha)$ and $T_n(\beta)$?

The reason why these two questions seem related is that one would expect $\text{cov}(T_n(\alpha), T_n(\beta)) $ to be roughly proportional to the number of edges on $\gamma_n(\alpha)\cap \gamma_n(\beta)$. (At least this is what happens for deterministic paths).

Presumably, Johannson's result tells us that var$(T_n(\alpha))$ is of order $n^{2/3}$ (though it's not a straightforward consequence of that result), so Cauchy-Schwarz implies that the covariance is at most of order $n^{2/3}$. This would suggest that $|\gamma_n(\alpha)\cap \gamma_n(\beta)|$ is at most of order $n^{2/3}$. However, it is hard to believe that this is sharp!

Does anyone know if these questions have been studied ? And what if we only know that $\text{var} (T_n(\alpha)) = o(n)$ (as in this paper,, by Benjamini Kalai and Schramm), does it follows that $|\gamma_n(\alpha) \cap \gamma_n(\beta)| = o(n)$?

share|cite|improve this question
This is closely related to Gil's question for first-passage percolation:… – Tom LaGatta Dec 18 '11 at 22:57
up vote 7 down vote accepted

EDIT: It was really remiss of me not to mention by Patrik Ferrari and Herbert Spohn, where there are very nice results concerning scalings when the distance between the two directions varies with $n$. The case $\beta=\alpha+O(n^{-1/3})$ is the one where a very nice scaling picture should emerge; maybe (Corwin and Quastel) on the "Airy sheet" is the beginning of this.

Hi Nathanael. The answer to Q1 will be $O(1)$. For concreteness consider the model with i.i.d. exponential weights at each site (the case with geometric weights at each site should also be fine but the geodesics are not unique so it's slightly messier). The path $\gamma_n(\alpha)$ converges almost surely to a path $\gamma(\alpha)$ as $n\to\infty$ (a "semi-infinite geodesic in direction $\alpha$"). So the question reduces to looking at the intersection of $\gamma(\alpha)$ and $\gamma(\beta)$. (The same behaviour should be seen across a wide class of models but showing that rigorously could be a challenge).

Coupier ( ) is a starting point for results and references concerning existence and uniqueness of such semi-infinite geodesics.

Actually one could certainly say some specific things about the law of the intersection of the two semi-infinite geodesics (in an exactly solvable model like the i.i.d. exponential weight case). The joint law of the geodesics in two different directions from the same point is very closely related to the equilibrium of an appropriately defined two-type particle system. In this case the relevant particle system would be a certain type of process like the Hammersley process, but in discrete time and space and with "fluid" rather than discrete particles. Eric Cator and I have done some work relating joint laws of geodesics to two-type equilibria in this way recently - it is not written up yet but I would be delighted to discuss. The closest thing on paper might be Eric's article with Leandro Pimentel at . The kind of calculations one could do concerning the two-type equilibria might resemble those done for the TASEP by Amir, Angel and Valko in (which make use of a queueing-type representation for the multi-type equilibrium of the kind that Pablo Ferrari and I developed in ).

share|cite|improve this answer
Hi James ! Thanks, very helpful. I guess the story about competing interface in FPP (which results in random slope) shows indeed that there is a nonzero probability that the geodesics have no edge in common at all. That is somehow slightly counterintuitive to me, you'd expect the geodesics to go get the same goodies for a while, before they diverge... So is the covariance $O(1)$ as well? – Nathanael Berestycki Dec 19 '11 at 10:21
Absolutely - the probability that the two semi-infinite geodesics do not intersect at all is a number that one could calculate exactly. My guess is that the covariance is indeed $O(1)$ but I don't know to show that. – James Martin Dec 19 '11 at 11:36
btw, if the distribution of the weights has a sufficiently heavy tail (essentially, infinite variance) then the intersection will be $O(n)$: . I wonder if there could be some intermediate case? – James Martin Dec 19 '11 at 11:40

For those who wonder how the geodesics look like, here is a quick simulations (with exponential weights): alt text

share|cite|improve this answer
very cool picture ! what did you use to generate it? – Nathanael Berestycki Dec 19 '11 at 10:12
A quick Python simulation (uploaded here: – Alekk Dec 19 '11 at 13:33

Two things off the top of my head, but not really thought through:

  • there is a paper by Bodineau and (I believe) Martin about the case of the quadrant, going to $(a_n,n)$ where $a_n=o(n)$ rather than linear, then you spend most of your time along the boundary of course but they have asymptotics;

  • there is also a recent paper by Chatterjee here which might also be relevant - it is about first rather than last-passage percolation, but the scaling should be similar.

Not sure any of this helps though ...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.