Skip to main content
1 of 2
Tom LaGatta
  • 8.5k
  • 1
  • 43
  • 82

This should be equivalent to a directed, site first-passage percolation (FPP) model where each site takes a passage time of $2$ or $\sqrt{2}$, each with probability $1/2$. As R W says in another answer, Kingman's subadditive ergodic theorem implies that the passage time $a_n$ between the origin and the point $(n,n)$ should be of the order $\mu n$ for some constant $\mu > 0$. As Ori Gurel-Gurevich says, the Benjamini-Kalai-Schramm estimate should apply so that the variance of the passage times is sublinear:
$$a_n = \mu n + O(n/\log n).$$

Let me now state some conjectures:

  • The variance of the passage time should be $O(n^{2\chi})$, where $\chi = 1/3$.

  • Let $\gamma_n$ denote the minimizing path from the origin to $(n,n)$. Let $d_n$ be the maximum Euclidean distance that $\gamma_n$ reaches away from the straight line path from the origin to $(n,n)$. Then $d_n$ should be $O(n^\xi)$, for $\xi = 2/3$.

  • Similar statements should hold in arbitrary dimension, for different values of the constants $\chi$ and $\xi$. Nonetheless, the constants should always obey the Kardar-Parisi-Zhang (KPZ) equation $$\chi = 2\xi - 1.$$

There has been much work on getting some precise bounds for these constants for FPP, but we are still far from rigorously proving that $\chi = 1/3$ and $\xi = 2/3$. See the excellent survey Models of First-Passage Percolation by Howard (2004) for more on this topic.

Tom LaGatta
  • 8.5k
  • 1
  • 43
  • 82