A universal feature of random searches

How efficient can an exhaustive search be? The cover time τ can quantifiably answer that question. But despite τ‘s relevance to a broad range of examples, from animals foraging for food to diseases spreading through a city, analytical results for the cover time have been scarce and limited to regular random walks—those involving moves between nearest neighbors in Euclidean geometry. In more complex search strategies, the random walker’s movement among neighbors may follow various other rules. For those strategies, researchers have focused almost entirely on the time required to reach a single target—the so-called first-passage time T. Now CNRS theorists Marie Chupeau, Olivier Bénichou , and Raphaël Voituriez have analytically derived the distribution of τ for several different complex random-walk processes. They exploited the fact that for a large number of sites N, the distribution of T averaged over all targets is an exponential of its mean, ⟨T⟩. Surprisingly, they found that when the distribution of cover times is expressed in terms of τ/⟨T⟩ − ln N , the distribution follows a universal curve. That is, data points obtained from the different search strategies (indicated by different colors) fall along the same curve, as shown here, which indicates the distribution’s insensitivity to the particular rules of an algorithm. (M. Chupeau, O. Bénichou, R. Voituriez, Nat. Phys., in press, doi:10.1038/nphys3413 .)