  Search patterns of randomly oriented steps of different lengths have been
observed on all scales of the biological world, ranging from the microscopic to
the ecological, including in protein motors, bacteria, T-cells, honeybees,
marine predators, and more. Through different models, it has been demonstrated
that adopting a variety in the magnitude of the step lengths can greatly
improve the search efficiency. However, the precise connection between the
search efficiency and the number of step lengths in the repertoire of the
searcher has not been identified. Motivated by biological examples in
one-dimensional terrains, a recent paper studied the best cover time on an
n-node cycle that can be achieved by a random walk process that uses k step
lengths. By tuning the lengths and corresponding probabilities the authors
therein showed that the best cover time is roughly n 1+$\Theta$(1/k). While
this bound is useful for large values of k, it is hardly informative for small
k values, which are of interest in biology. In this paper, we provide a tight
bound for the cover time of such a walk, for every integer k > 1. Specifically,
up to lower order polylogarithmic factors, the upper bound on the cover time is
a polynomial in n of exponent 1+ 1/(2k--1). For k = 2, 3, 4 and 5 the exponent
is thus 4/3 , 6/5 , 8/7 , and 10/9 , respectively. Informally, our result
implies that, as long as the number of step lengths k is not too large,
incorporating an additional step length to the repertoire of the process
enables to improve the cover time by a polynomial factor, but the extent of the
improvement gradually decreases with k.

Quantitative Methods;Discrete Mathematics