2 Grid Paths and Last Passage Percolation
2.1 Basic Definitions
A grid point is an element of \(\mathbb {N}^2\).
An edge is a pair of grid points.
An edge \((p, q)\) where \(p = (x, y)\) and \(q = (x', y')\) is up-right if either:
\(x' = x + 1\) and \(y' = y\) (right step), or
\(x' = x\) and \(y' = y + 1\) (up step).
A grid path is a list of edges.
A path is valid from point \(p\) to point \(q\) if it is a sequence of connected up-right edges starting at \(p\) and ending at \(q\).
For any \(m, n \in \mathbb {N}\), there exists at least one valid path from \((0, 0)\) to \((m, n)\).
Given a weight function \(w : \text{Edge} \to \mathbb {R}\) and endpoints \((m, n)\), the Last Passage Percolation value is:
where the maximum is taken over all valid paths from \((0, 0)\) to \((m, n)\).