The cost of revisiting in random walks
Abstract
We consider a simple random walk discrete in space and time that gets charged a fee or cost every time it makes a step, but the cost depends on its history such that it becomes lower every time it returns to a previously visited location. In this work we choose a cost function that scales as 1/(n+1) where n is the number of revisits throughout its history. We then examine the behavior of the average cost per step and expected total cost. Exact results are explicitly listed for small times through exhaustion. For large times the expected cost on each step behaves like (ln t)−1 and the cumulative cost has an asymptotic behavior related to the logarithmic integral li(x). Even though this vanishes in the asymptotic limit, the cumulative expected cost is unbounded, suggesting that unless the random walk has an infinite starting budget it will eventually be unable to afford to move.
