We consider directed last-passage percolation on the random graph G = (V,E) where V = Z and each edge (i,j), for i < j, is present in E independently with some probability 0 < p <= 1. To every present edge (i,j) we attach i.i.d. random weights v_{i,j} > 0. We are interested in the behaviour of w_{0,n}, which is the maximum weight of all directed paths from 0 to n, as n tends to infinity. We see two very different types of behaviour, depending on whether E[v_{i,j}^2] is finite or infinite. In the case where E[v_{i,j}^2] is finite we show that the process has a certain regenerative structure, and prove a strong law of large numbers and, under an extra assumption, a functional central limit theorem. In the situation where E[v_{i,j}^2] is infinite we obtain scaling laws and asymptotic distributions expressed in terms of a continuous last-passage percolation model on [0,1]; these are related to corresponding results for two-dimensional last-passage percolation with heavy-tailed weights obtained by Hambly and Martin.
Download