On the Markov transition kernels for first-passage percolation on the ladder

Abstract

We consider the first-passage percolation problem on the random graph with vertex set N\times{0,1}, edges joining vertices at Euclidean distance equal to unity and independent exponential edge weights. We provide a central limit theorem for the first-passage times l_n between the vertices (0,0) and (n,0), thus extending earlier results about the almost sure convergence of l_n/n as n goes to infinity. We use generating function techniques to compute the n-step transition kernels of a closely related Markov chain which can be used to calculate explicitly the asymptotic variance in the central limit theorem.

17 pages, one figure, one table

References in corpus (3)

• First Passage Properties of the Erdos-Renyi Random Graph
• First passage percolation on random graphs with finite mean degrees
• First-passage percolation on width-two stretches with exponential link weights