How long does it take a random searcher to visit all sites of a given domain? This time, known as the cover time [1] , is a key observable to quantify the efficiency of exhaustive searches, which require a complete exploration of an area and not only the discovery of a single target; examples range from immune system cells chasing pathogens [2] to animals harvesting resources [3, 4] , robotized exploration by e.g. automated cleaners or deminers, or algorithmics [5] . Despite its broad relevance, the cover time has remained elusive and so far explicit results have been scarce and mostly limited to regular random walks [6] [7] [8] [9] . Here we determine the full distribution of the cover time for a broad range of random search processes, which includes the prominent examples of Lévy strategies [10] [11] [12] [13] [14] , intermittent strategies [4, 15, 16] , persistent random walks [17] and random walks on complex networks [18] , and reveal its universal features. We show that for all these examples the mean cover time can be minimized, and that the corresponding optimal strategies also minimize the mean search time for a single target, unambiguously pointing towards their robustness. * benichou@lptmc.jussieu.fr † voiturie@lptmc. Random search processes have proved over the recent years to be involved in a broad range of contexts at various scales, from the search of specific sequences on DNA by proteins to animal foraging [3, 4] . So far, the main tools to quantify the efficiency of such search processes could be expressed in terms of the time needed for the searcher to reach a single target, the so-called first-passage time [18] [19] [20] [21] [22] . However, as soon as several targets need to be found, which is a recurrent situation in chemistry, ecology, or robotics, the relevant observable is rather the time needed to reach a fraction of the domain sites (see Fig. 1 ). The extreme case of such exhaustive searches where all sites of a domain need to be visited defines the so-called cover time, which is of particular interest since it gives the time needed to find all targets of a domain with certainty; its determination is a long standing problem of random walk theory [1, 23] (see [24, 25] for related observables). Nevertheless, analytical results on cover times are scarce. Important steps were achieved in [26] , where the mean cover time of an interval was analytically calculated for onedimensional symmetric nearest-neighbor random walks, both for periodic and reflecting boundary conditions. In dimensions greater or equal to three, Aldous [23] has determined the leading behavior of the mean cover time in the limit of large domain size, which was reproduced by numerical simulations in [27] . In the physics literature, these results have been extended to the two-dimensional case in [6], which has been since then refined in the mathematics literature [7] [8] [9] . Notably, all these results were so far essentially limited to the case of regular random walks, i.e. symmetric nearest-neighbor random walks in Euclidean geometries. However, recently, several classes of more complex random search strategies, including Lévy strategies [10] [11] [12] [13] [14] , intermittent strategies [4, 15, 16] and persistent random walks [17], have emerged and been shown theoretically to be efficient (see Fig. 1 ). In this context, existing theoretical studies have up to now focused mainly on the first-passage time to a single target, and the cover time of these random search processes, required to quantify the efficiency of exhaustive searches, has been left aside. The analytical determination of the entire distribution of cover time type observables for general classes of random walks, including the above, is at the core of this paper. We consider a random walker moving on a network of N sites. The random walk is assumed to be Markovian and non compact (i.e. transient: in infinite space, the probability for the walker to ever reach a given site is strictly smaller than one [28] ). This covers a 2 large class of processes relevant to search problems. We denote by τ (M, N ) the partial cover time, defined as the time needed to visit any M distinct sites of the network. The alternative problem of determining the time needed to visit M given sites (chosen at random), called the random cover time [27], will be addressed below. Note that taking M = N (for both the partial and the random cover time) yields the full cover time, to which most of the literature has been devoted so far. In practice, we will focus on large values of M, N . The  The exact determination of the statistical properties of this random variable can seem out of reach since a priori θ(k, N ) depends on the entire random trajectory until time τ (N − k, N ). The key hypothesis is then to assume that the random variables θ(k, N ) are in fact independent asymptotically in the large N limit. This hypothesis will be verified numerically for all tested non compact random walks, and will furthermore allow to retrieve exact results known so far for regular random walks. In this regime of N large the distribution of θ(k, N ) can be obtained explicitly and enables the determination of the full distribution of the partial cover time, which, as we show in Supplementary Information (SI), finally takes the universal form Here the rescaled variable x ≡ τ / T − ln N involves the mean T of the global first-passage time, defined as the mean first-passage time to a given target site averaged over all starting sites. This constitutes the central result of this paper. Its derivation relies on the fact that the distribution of the global first-passage time T to a given target site is asymptotically an exponential of mean T for non compact random walks [29, 30] . In addition, we assumed that T is independent of the target site, which is exact for domains with periodic boundary conditions, and in practice well satisfied for any domain shape in the case of non compact random walks, as was checked numerically. (2) unambiguously captures the mean, variance, and entire distribution of partial and full cover times (Fig. (2) and (3)), as well as random cover times and cover times for n searchers (Fig. (3) ), as shown by the data collapse of the numerical simulations. We emphasize that the very different nature of these examples demonstrates that the range of applicability of our approach, which mainly relies on the non compact property of the random trajectory of the searcher, is wide. Note that even for 2D persistent random walks, which are in fact marginally compact, both the mean and variance of cover times are quantitatively predicted by our approach in the large domain size limit, provided that the persistence length minimizes the global mean first-passage time for a target T , as analyzed in [17] . In practice, the question of minimizing the cover time in order to optimize the efficiency of the search process is crucial. Our analysis reveals that the mean cover time (either random or partial) is minimized exactly when the global mean first-passage time T for a single target is minimized (see Fig. (4) ). In particular, in the case of persistent random walks and intermittent random walks, which have been shown to minimize T (either by tuning the persistence length of the persistent random walk or the duration of the scanning phase of the intermittent random walk), we find that mean cover times can also be minimized. For Lévy walks, the celebrated optimization of the target encounter rate for a Lévy index α 1 (defined through the jump length distribution p(l) ∝ l −α−1 for l large) has been obtained and discussed only for a distribution of infinitely many so-called revisitable targets (which reappear at the same position after being found) [12] . In contrast, the global mean firstpassage time to a single target in confinement, which by definition involves a non revisitable target, has been left aside. In fact, we find that T (see also [17] ), and therefore the mean cover time, can be minimized by adjusting the persistence length for all α > 1 (see Fig.   (4) ). This optimal strategy, which does not require revisitable targets, is therefore very different from the above mentioned optimal strategy obtained for infinitely many revisitable targets. All together, these results shed new light on the role of persistent, intermittent and Lévy strategies in the optimization of search processes, and clearly points towards their robustness. 5 The definition of random search processes analyzed in the text are as follows (see SI for details): (i) Brownian random walks constitute the most striking example of random search process, which is known to be non compact in dimension D = 3, and marginally compact for D = 2. Here we consider nearest neighbor random walks on a periodic lattice of N sites. (ii) Lévy flights have been shown to play an important role in random search problems [13] . We consider here discrete Lévy flights of index α on 1D, 2D and 3D periodic lattices of size N , characterized by a probability distribution to perform a jump of size l that obeys (iii) Complex networks. Beyond classical Euclidean spaces, many examples of random walks on complex networks, whose relevance to extremely various fields is now unanimously recognized, are non compact. Here we consider the emblematic Erdős-Rényi networks [31] . (iv) Persistent random walks provide a minimal example of search process with memory, which is encoded in the persistence length, defined as the mean number of successive steps performed in a given direction. They have been shown to lead to a minimization of the mean search time for a single target, and therefore play a prominent role in the optimization of search processes [17] . We consider here 2D and 3D discrete persistent random walks on a periodic lattice of N sites. (v) Lévy walks. As opposed to Lévy flights, which can have arbitrary large velocities, Lévy walks [10] have a constant speed, and can be seen as an extension of persistent random walks, for which the distribution of the number of successive steps is not exponential, but power-law distributed. They have been shown to be optimizable and have been extensively invoked in the context of animal behavior [12] . We consider here 2D and 3D discrete Lévy walks on a periodic lattice of N sites. (vi) Intermittent strategies. Last, we consider the case of well hidden targets, for which it can be assumed that moving and searching are incompatible. In this case, the search strategy is intermittent [4] . Technically, we focus here on a continuous time two-state searcher moving on a 1D, 2D or 3D periodic lattice of N sites [32] . In the slow reactive state 1, the searcher performs a regular nearest neighbor random walk with jump rate ρ, and actually visits the corresponding sites. With rate λ 1 ≡ 1/τ 1 , the searcher switches to a fast and non 6 reactive state 2, which enables a uniform relocalization in the domain, but during which no sites are visited. The searcher then switches to state 1 with rate λ 2 ≡ 1/τ 2 .
Very recently, Chupeau et al. REF connected Lévy flights to optimal search strategies and minimization of cover times.
Cover times of random searches
Nature Physics 11, 844-847 (2015)
Mathematics Physics