title: Exact distributions of the number of distinct and common sites visited by N independent random walkers.
abstract: We study the number of distinct sites S(N)(t) and common sites W(N)(t) visited by N independent one dimensional random walkers, all starting at the origin, after t time steps. We show that these two random variables can be mapped onto extreme value quantities associated with N independent random walkers. Using this mapping, we compute exactly their probability distributions P(N)(d)(S,t) and P(N)(c)(W,t) for any value of N in the limit of large time t, where the random walkers can be described by Brownian motions. In the large N limit one finds that S(N)(t)/√t∝2√(log N)+s/(2√(log N)) and W(N)(t)/√t∝w/N where s and w are random variables whose probability density functions are computed exactly and are found to be nontrivial. We verify our results through direct numerical simulations.
authors.affiliation: Laboratoire de Physique Théorique et Modèles Statistiques (UMR 8626 du CNRS), Université Paris-Sud, Bâtiment 100, 91405 Orsay Cedex, France.
authors.forename: Anupam
authors.initials: A
authors.lastname: Kundu
authors.forename: Satya N
authors.initials: SN
authors.lastname: Majumdar
authors.forename: Grégory
authors.initials: G
authors.lastname: Schehr