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× {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 ln between the vertices (0,0) and (n,0), thus extending earlier results about the almost sure convergence of ln/n as n → ∞. 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. 1