First-passage times in multiscale random walks: The impact of movement scales on search efficiency

© 2015 American Physical Society. An efficient searcher needs to balance properly the trade-off between the exploration of new spatial areas and the exploitation of nearby resources, an idea which is at the core of scale-free Lévy search strategies. Here we study multiscale random walks as an approximation to the scale-free case and derive the exact expressions for their mean-first-passage times in a one-dimensional finite domain. This allows us to provide a complete analytical description of the dynamics driving the situation in which both nearby and faraway targets are available to the searcher, so the exploration-exploitation trade-off does not have a trivial solution. For this situation, we prove that the combination of only two movement scales is able to outperform both ballistic and Lévy strategies. This two-scale strategy involves an optimal discrimination between the nearby and faraway targets which is only possible by adjusting the range of values of the two movement scales to the typical distances between encounters. So, this optimization necessarily requires some prior information (albeit crude) about target distances or distributions. Furthermore, we found that the incorporation of additional (three, four, ...) movement scales and its adjustment to target distances does not improve further the search efficiency. This allows us to claim that optimal random search strategies arise through the informed combination of only two walk scales (related to the exploitative and the explorative scales, respectively), expanding on the well-known result that optimal strategies in strictly uninformed scenarios are achieved through Lévy paths (or, equivalently, through a hierarchical combination of multiple scales).