Search via Parallel Levy Walks on Z2

Motivated by the Levy foraging hypothesis - the premise that various animal species have adapted to follow Levy walks to optimize their search efficiency - we study the parallel hitting time of Levy walks on the infinite two-dimensional grid. We consider k independent discrete-time Levy walks, with the same exponent alpha is an element of(1, infinity), that start from the same node, and analyze the number of steps until the first walk visits a given target at distance l. We show that for any choice of k and l from a large range, there is a unique optimal exponent alpha(k,l) is an element of(2, 3), for which the hitting time is (O) over tilde (l(2)/k) w.h.p., while modifying the exponent by any constant term epsilon > 0 increases the hitting time by a factor polynomial in l, or the walks fail to hit the target almost surely. Based on that, we propose a surprisingly simple and effective parallel search strategy, for the setting where k and l are unknown: The exponent of each Levy walk is just chosen independently and uniformly at random from the interval (2, 3). This strategy achieves optimal search time (modulo polylogarithmic factors) among all possible algorithms (even centralized ones that know k). Our results should be contrasted with a line of previous work showing that the exponent alpha = 2 is optimal for various search problems. In our setting of k parallel walks, we show that the optimal exponent depends on k and l, and that randomizing the choice of the exponents works simultaneously for all k and l.