Exact Distributions of the Number of Distinct and Common Sites Visited by N Independent Random Walkers

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) /root t proportional to 2 root log N + (s) over tilde/(2 root log N) and W-N(t)/root t proportional to (w) over tilde /N where (s) over tilde and (w) over tilde are random variables whose probability density functions are computed exactly and are found to be nontrivial. We verify our results through direct numerical simulations.