Random Walks with Multiple Step Lengths Conference Paper uri icon

abstract

  • In nature, search processes that use randomly oriented steps of different lengths have been observed at both the microscopic and the macroscopic scales. Physicists have analyzed in depth two such processes on grid topologies: Intermittent Search, which uses two step lengths, and Lévy Walk, which uses many. Taking a computational perspective, this paper considers the number of distinct step lengths k as a complexity measure of the considered process. Our goal is to understand what is the optimal achievable time needed to cover the whole terrain, for any given value of k. Attention is restricted to dimension one, since on higher dimensions, the simple random walk already displays a quasi linear cover time. We say X is ak-intermittent search on the one dimensional n-node cycle if there exists a probability distribution p=(p_i) _ i= 1^ kp=(pi) i= 1 k, and integers L_1, L_2, ..., L_k L 1, L 2 …

publication date

  • January 1, 2018