2020/02/13 by Brieuc Guinard, Amos Korman, Guinard, Brieuc +1
Biochemistry, Genetics and Molecular Biology · Mathematics · #Diffusion and Search Dynamics #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #Point processes and geometric inequalities #Quantitative Methods (q-bio.QM) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2002.05443
openalex publication_date 2020/02/13 · openalex created_date 2020/04/03 · openalex updated_date 2026/07/28
Search patterns of randomly oriented steps of different lengths have been\nobserved on all scales of the biological world, ranging from the microscopic to\nthe ecological, including in protein motors, bacteria, T-cells, honeybees,\nmarine predators, and more. Through different models, it has been demonstrated\nthat adopting a variety in the magnitude of the step lengths can greatly\nimprove the search efficiency. However, the precise connection between the\nsearch efficiency and the number of step lengths in the repertoire of the\nsearcher has not been identified. Motivated by biological examples in\none-dimensional terrains, a recent paper studied the best cover time on an\nn-node cycle that can be achieved by a random walk process that uses k step\nlengths. By tuning the lengths and corresponding probabilities the authors\ntherein showed that the best cover time is roughly n 1+\Θ(1/k). While\nthis bound is useful for large values of k, it is hardly informative for small\nk values, which are of interest in biology. In this paper, we provide a tight\nbound for the cover time of such a walk, for every integer k > 1. Specifically,\nup to lower order polylogarithmic factors, the upper bound on the cover time is\na polynomial in n of exponent 1+ 1/(2k--1). For k = 2, 3, 4 and 5 the exponent\nis thus 4/3 , 6/5 , 8/7 , and 10/9 , respectively. Informally, our result\nimplies that, as long as the number of step lengths k is not too large,\nincorporating an additional step length to the repertoire of the process\nenables to improve the cover time by a polynomial factor, but the extent of the\nimprovement gradually decreases with k.\n