论文标题
随机步行的覆盖时间的紧密界限，具有异质步长的长度
Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths
论文作者
论文摘要
在生物世界的所有尺度上都观察到了不同长度的随机取向步骤的搜索模式，从微观到生态学，包括蛋白质电动机，细菌，T细胞，T细胞，蜜蜂，海洋捕食者等。通过不同的模型，已经证明，在步长的大小上采用各种各样可以大大提高搜索效率。但是，尚未确定搜索效率与搜索者曲目中的步长数之间的精确连接。由一维地形的生物学示例激励，最近的一篇论文研究了N节点周期中最佳的覆盖时间，可以通过使用K步长的随机步行过程来实现。通过调整作者的长度和相应的概率，最佳的覆盖时间大约为n 1+$θ$（1/k）。尽管该界限对于k的大值很有用，但对于在生物学中引起的小k值而言，它几乎没有信息。在本文中，我们为每一个整数k> 1提供了一个紧密的结合。对于k = 2、3、4和5，指数分别为4/3、6/5、8/7和10/9。非正式的结果，我们的结果意味着，只要k的步长数不太大，将过程的额外长度纳入了过程，从而可以通过多项式因素来改善覆盖时间，但是随着k的改进程度逐渐降低。
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+$Θ$(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.
