Last Passage Percolation

Last Passage Percolation Skill

Status: ✅ Production Ready Trit: 0 (ERGODIC - coordinator) Color: #20B2AA (Light Sea Green) Principle: Maximum weight paths as discrete KPZ Frame: Tracy-Widom fluctuations, geodesics, RSK correspondence

Overview

Last Passage Percolation (LPP) is the discrete progenitor of KPZ universality:

1. Passage Times: Maximum weight over up-right paths
2. Fluctuations: Tracy-Widom distributed
3. Geodesics: Competition interfaces
4. Exactly Solvable: Via determinantal point processes

The Model

Geometric/Exponential LPP

Grid: ℤ₊² with i.i.d. weights w(i,j)
Path: π from (1,1) to (m,n), up-right steps only
Weight: W(π) = Σ w(i,j) along π
Passage time: G(m,n) = max_π W(π)

struct LPP
    weights::Matrix{Float64}
    distribution::Distribution  # Exponential, Geometric, etc.
end

function passage_time(lpp::LPP, start, finish)
    m, n = finish
    # Dynamic programming
    G = zeros(m, n)
    G[1, 1] = lpp.weights[1, 1]
    
    for i in 2:m
        G[i, 1] = G[i-1, 1] + lpp.weights[i, 1]
    end
    for j in 2:n
        G[1, j] = G[1, j-1] + lpp.weights[1, j]
    end
    for i in 2:m, j in 2:n
        G[i, j] = max(G[i-1, j], G[i, j-1]) + lpp.weights[i, j]
    end
    
    return G[m, n]
end

Tracy-Widom Limit

# Limiting distribution for diagonal direction
function tracy_widom_limit(lpp, n)
    # For exponential weights:
    # G(n,n) ≈ 4n + 2^(4/3) n^(1/3) χ_GUE
    
    G = passage_time(lpp, (1,1), (n,n))
    mean = 4 * n
    std = 2^(4/3) * n^(1/3)
    
    χ = (G - mean) / std
    return χ  # Converges to Tracy-Widom GUE
end

Weight Distributions

# Different weight types
lpp_exp = LPP(rand(Exponential(1), n, n), Exponential(1))
lpp_geo = LPP(rand(Geometric(0.5), n, n), Geometric(0.5))

Geodesics and Competition Interfaces

Geodesic Computation

function geodesic(lpp::LPP, start, finish)
    # Backtrack from finish to start
    path = [finish]
    i, j = finish
    
    while (i, j) != start
        if i == 1
            j -= 1
        elseif j == 1
            i -= 1
        else
            # Choose direction that maintains optimality
            if G[i-1, j] > G[i, j-1]
                i -= 1
            else
                j -= 1
            end
        end
        pushfirst!(path, (i, j))
    end
    
    return path
end

Competition Interface

When two geodesics compete:

function competition_interface(lpp, source1, source2)
    # Interface where optimal paths from two sources meet
    interface = []
    
    for point in lattice_points
        geo1 = passage_time(lpp, source1, point)
        geo2 = passage_time(lpp, source2, point)
        
        if abs(geo1 - geo2) < ε
            push!(interface, point)
        end
    end
    
    return interface  # Converges to Airy₂ process
end

Matrix Product Ansatz

For stationary LPP (boundary conditions matching bulk):

struct MatrixProductLPP
    D::Matrix  # Creation operator
    E::Matrix  # Annihilation operator
    W::Vector  # Left boundary
    V::Vector  # Right boundary
end

function stationary_weight(mpa::MatrixProductLPP, config)
    # Weight = ⟨W| ∏ᵢ Mᵢ |V⟩
    # where Mᵢ = D if occupied, E if empty
    
    result = mpa.W'
    for c in config
        result = result * (c == 1 ? mpa.D : mpa.E)
    end
    result = result * mpa.V
    
    return result[1]
end

# DEHP algebra relations
# DE - qED = D + E
# ⟨W|E = ⟨W|
# D|V⟩ = |V⟩

RSK Correspondence

Robinson-Schensted-Knuth connects LPP to Young tableaux:

# RSK: Matrix → (P, Q) pair of tableaux
function rsk(weight_matrix)
    P, Q = empty_tableau(), empty_tableau()
    
    for (i, j, w) in entries(weight_matrix)
        for _ in 1:w
            row_insert!(P, j)
            record_insert!(Q, i)
        end
    end
    
    return P, Q
end

# Passage time = shape of P-tableau
@test passage_time(lpp, (1,1), (n,n)) == 
      shape(rsk(lpp.weights)[1])[1]

Connection to TASEP

LPP is equivalent to Totally Asymmetric Simple Exclusion Process:

# TASEP: particles hop right, cannot pass
struct TASEP
    positions::Vector{Int}  # Particle positions
    L::Int                  # System size
end

# LPP passage time = TASEP current
@test passage_time(lpp) == integrated_current(tasep)

# Geodesic = second class particle trajectory

Two-Layer Gibbs Structure

Like KPZ stationary measures, LPP has two-layer structure:

# Layer 1: Uncolored non-crossing paths
uncolored = sample_non_crossing_paths(n)

# Layer 2: Color assignment via Pitman
colored = pitman_transform(uncolored)

# Joint measure
μ(colored) = μ_uncolored(paths) × P(coloring | paths)

Pitman Transform

function pitman_transform(paths)
    # Sort paths by endpoint
    # Apply successive Pitman operators
    result = paths
    for i in 1:length(paths)-1
        result[i], result[i+1] = pitman_2(result[i], result[i+1])
    end
    return result
end

function pitman_2(path1, path2)
    # Pitman's 2M-X theorem for Brownian motion
    # Discrete version for random walks
    return (path1 ∨ path2, path1 ∧ path2)  # max/min operations
end

Integration with KPZ Universality

LPP is the discrete model; KPZ is the scaling limit:

using KPZUniversality, LPP

# LPP → Directed Landscape
function lpp_to_landscape(lpp, ε)
    # Rescale by 1:2:3 exponents
    L(x, s, y, t) = ε^(1/2) * passage_time(lpp, 
        round(Int, ε^(-1) * x), round(Int, ε^(-3/2) * s),
        round(Int, ε^(-1) * y), round(Int, ε^(-3/2) * t)
    )
    return L
end

# In limit ε → 0, converges to directed landscape

GF(3) Triad Assignment

Conservation: (-1) + (0) + (+1) = 0 ✓

Commands

# Simulate LPP
just lpp-simulate n=100 weights=exponential

# Compute passage time
just lpp-passage start=1,1 end=100,100

# Find geodesic
just lpp-geodesic

# Check Tracy-Widom
just lpp-verify-tw

# Matrix product ansatz
just lpp-mpa q=0.5

Configuration

# last-passage-percolation.yaml
model:
  grid_size: 100
  weight_distribution: exponential  # or geometric, bernoulli
  
analysis:
  compute_geodesics: true
  tracy_widom_test: true
  competition_interface: false

matrix_product:
  q: 0.5
  boundary: stationary

Related Skills

• kpz-universality (0): Scaling limit
• yang-baxter-integrability (-1): Algebraic structure
• louisville-quantum-gravity (+1): Stationary measures
• colored-vertex-model (+1): Colored particles
• gay-mcp (+1): Deterministic paths

Research References

1. Johansson (2000): "Shape fluctuations and random matrices"
2. Baik-Deift-Johansson (1999): "On the distribution of the length of the longest increasing subsequence"
3. Ferrari-Spohn (2005): "Scaling limit for the space-time covariance of the stationary TASEP"
4. Corwin (2012): "The Kardar-Parisi-Zhang equation and universality class"

Skill Name: last-passage-percolation Type: Discrete KPZ Model Trit: 0 (ERGODIC) Key Property: Tracy-Widom fluctuations, geodesic competition Status: ✅ Production Ready

Cat# Integration

Trit: 0 (ERGODIC)
Home: DiscreteProb
Poly Op: ⊗
Kan Role: Adj
Color: #20B2AA

Passage Time as Profunctor

G: ℤ₊² ↛ ℝ
G(start, end) = max path weight

Satisfies semi-group property:

G(a, c) = max_b [G(a, b) + G(b, c)]

GF(3) Naturality

(-1) + (0) + (+1) ≡ 0 (mod 3)

Autopoietic Marginalia

Paths compete. Weights accumulate. The maximum emerges.

Every use of this skill is an opportunity for worlding:

• MEMORY (-1): Record geodesic patterns
• REMEMBERING (0): Connect to TASEP dynamics
• WORLDING (+1): Discover new limit shapes

Add Interaction Exemplars here as the skill is used.