Average search time bounds in cue-based searches.

Abstract

In this work we consider search problems that evaluate the probability distribution of finding the source at each step in the search. We start with a sample strategy where the movement at each time step is in the immediate neighborhood. The jump probability is taken to be proportional to the normalized difference between the probability of finding the source at the jump location with the probability of finding the source at the present location. We evaluate a lower bound on the average search time for a searcher using this strategy. We next consider the problem of evaluating the lower bound on the search time for a generic strategy which would utilize the source probability distribution to figure out the position of the source. We derive an expression for the lower bound on the search time. We present an analytic expression for this lower bound in a case in which the particles emitted by the source diffuse in a homogeneous manner. For a general probability distribution with entropy E, we find that the lower bound goes as e^{E/2}.