Records for the number of distinct sites visited by a random walk on the fully-connected lattice

L. Turban

Published 2015-05-18Version 1

We consider a random walk on the fully-connected lattice with N sites and study the time evolution of the number of distinct sites s visited by the walker on a subset with n sites. A record value v is obtained for s at a record time t when the walker visits a site of the subset for the first time. The record time t is a partial covering time when v<n and a total covering time when v=n. The probability distributions for the number of records s, the record value v and the record (covering) time t, involving r-Stirling numbers, are obtained using generating function techniques. The mean values, variances and skewnesses are deduced from the generating functions. In the scaling limit the probability distributions for s and v lead to the same Gaussian density. The fluctuations of the record time t are also Gaussian at partial covering. They are distributed according to a Gumbel probability distribution at total covering.