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 to N independent random walkers. Using this mapping, we compute exactly their probability distributions P_N^d(S,t) and P_N^d(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)/\sqrt{t} \propto 2 \sqrt{\log N} + \widetilde{s}/(2 \sqrt{\log N}) and W_N(t)/\sqrt{t} \propto \widetilde{w}/N where \widetilde{s} and \widetilde{w} are random variables whose probability density functions (pdfs) are computed exactly and are found to be non trivial. We verify our results through direct numerical simulations.

5 pages, 3 figures

References in corpus (5)

• Freezing and extreme value statistics in a Random Energy Model with logarithmically correlated potential
• Collective dynamics of social annotation
• Non-intersecting Brownian walkers and Yang-Mills theory on the sphere
• Exact distribution of the maximal height of p vicious walkers
• Finite-size scaling in extreme statistics

Cited by in corpus (25)

• Extreme value statistics of correlated random variables: a pedagogical review
• Freezing Transitions and Extreme Values: Random Matrix Theory, $\zeta (1/2+it)$, and Disordered Landscapes
• Time between the maximum and the minimum of a stochastic process
• Distribution of the Time Between Maximum and Minimum of Random Walks
• Convex Hulls of Random Walks: Large-Deviation Properties
• Spatial Extent of Branching Brownian Motion
• Number of distinct sites visited by a resetting random walker
• On certain functionals of the maximum of Brownian motion and their applications
• Unfolding Tagged Particle Histories in Single-File Diffusion: Exact Single- and Two-Tag Local Times Beyond Large Deviation Theory
• The average number of distinct sites visited by a random walker on random graphs
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• Exact distributions of cover times for $N$ independent random walkers in one dimension
• Convex Hulls of Multiple Random Walks: A Large-Deviation Study
• Last-passage time for linear diffusions and application to the emptying time of a box
• Records for the number of distinct sites visited by a random walk on the fully-connected lattice
• Maximal distance travelled by N vicious walkers till their survival
• Lattice gases with a point source
• Probability distribution of the number of distinct sites visited by a random walk on the finite-size fully-connected lattice
• Level Set Percolation in Two-Dimensional Gaussian Free Field
• Maxima of log-correlated fields: some recent developments
• Topology-dependent density optima for efficient simultaneous network exploration
• Large deviations of a random walk model with emerging territories
• Overlap of two Brownian trajectories: exact results for scaling functions
• Statistical properties of sites visited by independent random walks
• Mean number of encounters of N random walkers and intersection of strongly anisotropic fractals