In this chapter, our goal is to extend the technology we used to prove the KKL Theorems on influences and the BKS Theorem on noise sensitivity in a slightly different context: the study of fluctuations in first-passage percolation.

The model of first-passage percolation

Let us first explain what the model is. Let 0 < a < b be two positive numbers. We define a random metric on the graph ℤd, d ≥ 2 as follows. Independently for each edge e ∈ Ed, fix its length τe to be a with probability 1/2 and b with probability 1/2. This is represented by a uniform configuration ω ∈ {−1, 1}Ed.

This procedure induces a well-defined (random) metric distω on ℤd in the usual fashion. For any vertices x, y ∈ ℤd, let

distω(x, y): = inf {Στei(ω)}.

paths γ = {e1, …, ek}

connecting x → y

Remark In greater generality, the lengths of the edges are i.i.d. nonnegative random variables, but here, following (BKS03), we restrict ourselves to the above uniform distribution on {a, b} to simplify the exposition; see (BR08) for an extension to more general laws.

One of the main goals in first-passage percolation is to understand the large-scale properties of this random metric space. For example, for any T ≥ 1, one may consider the (random) ball

Bω(x, T): = {y ∈ ℤd : distω(x, y) ≤ T}.

To understand the name first-passage percolation, one can think of this model as follows. Imagine that water is pumped in at vertex x, and that for each edge e, it takes τe(ω) units of time for the water to travel across the edge e. Then, Bω(x, T) represents the region of space that has been wetted by time T.