Search via Parallel L\'evy Walks on ${\mathbb{Z}}^2$

Motivated by the L'evy foraging hypothesis – the premise that various animal species have adapted to follow L'evy walks to optimize their search efficiency – we study the parallel hitting time of L'evy walks on the infinite two-dimensional grid. We consider $k$ independent discrete-time L'evy walks, with the same exponent $\alpha \in (1,\mathrm{\infty })$, that start from the same node, and analyze the number of steps until the first walk visits a given target at distance $\mathrm{\ell }$. We show that for any choice of $k$ and $\mathrm{\ell }$ from a large range, there is a unique optimal exponent ${\alpha }_{k,\mathrm{\ell }}\in (2,3)$, for which the hitting time is $\tilde{O}({\mathrm{\ell }}^2\mathrm{/}k)$ w.h.p., while modifying the exponent by an $ϵ$ term increases the hitting time by a polynomial factor, 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 $\mathrm{\ell }$ are unknown: the exponent of each L'evy 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 $\mathrm{\ell }$, and that randomizing the choice of the exponents works simultaneously for all $k$ and $\mathrm{\ell }$.