Variational formula for the time-constant of first-passage percolation

Abstract

We consider first-passage percolation with positive, stationary-ergodic weights on the square lattice ${\mathbb{Z}}^d$. Let $T(x)$ be the first-passage time from the origin to a point $x$ in ${\mathbb{Z}}^d$. The convergence of the scaled first-passage time $T([nx])/n$ to the time-constant as $n\to \infty$ can be viewed as a problem of homogenization for a discrete Hamilton-Jacobi-Bellman (HJB) equation. We derive an exact variational formula for the time-constant, and construct an explicit iteration that produces a minimizer of the variational formula (under a symmetry assumption). We explicitly identify when the iteration produces correctors.

arXiv comment33 pages, 1 figure. The proof has been updated so that it's completely discrete. The previous version of the proof may be found in https://arxiv.org/abs/1406.1108 . Accepted for publication in Communications in Pure and Applied Mathematics