Student Probability Seminar

The Law of Large Numbers for First-Passage Percolation

Speaker: Arjun Krishnan

Location: Warren Weaver Hall 1314

Date: Thursday, March 28, 2013, 3:30 p.m.


First Passage Percolation is a simple generalization of percolation introduced in the 1960s. The model can be described as follows: let \(\tau\) be a random variable such that \(0 < a \leq \tau \leq b\), and let's attach i.i.d copies of \(\tau\) to the edges of the square-lattice \(\mathbb{Z}^d\). That is, we have a set of random, positive, edge-weights on the lattice. A path from the origin to \(x \in \mathbb{Z}^d\) is a nearest neighbour walk along the lattice, and the time taken to traverse the path is just the sum of edge-weights along the path. Let the first-passage time \(T(x)\) be the least time required to get from \(0\) to \(x\) (it's an inf over all paths). If you know the subadditive ergodic theorem, it's relatively easy to establish that \(\lim_{n \to \infty} T(nx)/n = \mu(x)\) exists. However, it's fairly difficult to say anything quantitative about the limit; solutions are known only in a handful of very special edge-weight distributions. We will use a few simple techniques from optimal control theory and PDEs to establish a formula for \(\mu(x)\). No prior knowledge (other than basic probability) will be assumed, and the talk will be pedagogical.