Upper Tail Large Deviations in First Passage Percolation

Riddhipratim Basu, Allan Sly, Shirshendu Ganguly

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


For first passage percolation on (Formula presented.) with i.i.d. bounded edge weights, we consider the upper tail large deviation event, i.e., the rare situation where the first passage time between two points at distance n is macroscopically larger than typical. It was shown by Kesten [24] that the probability of this event decays as (Formula presented.). However, the question of existence of the rate function, i.e., whether the log-probability normalized by n2 tends to a limit, remains open. We show that under some additional mild regularity assumption on the passage time distribution, the rate function for upper tail large deviation indeed exists. The key intuition behind the proof is that a limiting metric structure that is atypical causes the upper tail large deviation event. The formal argument then relies on an approximate version of the above which allows us to use independent copies of the large deviation environment at a given scale to form an environment at a larger scale satisfying the large deviation event. Using this, we compare the upper tail probabilities for various values of n.

Original languageEnglish (US)
Pages (from-to)1577-1640
Number of pages64
JournalCommunications on Pure and Applied Mathematics
Issue number8
StatePublished - Aug 2021

All Science Journal Classification (ASJC) codes

  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Upper Tail Large Deviations in First Passage Percolation'. Together they form a unique fingerprint.

Cite this