Cover times of random searches

Abstract

How long must one undertake a random search 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), from robotic exploration for cleaning or demining to the task of improving search algorithms(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-9). Here we determine the full distribution of the cover time for a broad range of random search processes, including Levy strategies(10-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.