Chance and strategy in search processes

We consider a searcher in quest of a target in two situations: in the presence of an infinite number of identical, Poisson distributed targets, and in the presence of a unique target in a finite territory. The searcher alternates intensive search phases, during which it scans the neighbouring territory but does not move, and displacement phases with no target detection. We study the problem of determining the best strategy of displacement for minimizing the mean search time: either a deterministic or a stochastic trajectory. With a reasonable simplifying hypothesis, we show that for Poisson distributed targets, deterministic, self-avoiding trajectories are more efficient than stochastic ones if the detection process involves no memory skills and can be modelled by a Markov process. In contrast, if the detection process is not Markovian, it can be better for the searcher to follow a stochastic trajectory rather than a self-avoiding trajectory, and we give an explicit example of such a memory law. In the case of a unique target, self-avoiding trajectories are always better if an infinite time is available for the search, whereas stochastic trajectories can be more efficient if the searcher has to find the target before a given deadline. Moreover, we show that the gain due to a deterministic trajectory, compared to a stochastic one, is not significant in the case of a large network containing a unique target. Additionally, for various examples of displacement trajectories, we compute the overall mean search time and study its minimization as a function of the mean duration of the detection process.