Publication at Faculty of Mathematics and Physics |
2019
Abstract
Given a connected graph G with some subset of its vertices excited and a fixed target vertex, in the geodesic-biased random walk on G, a random walker moves as follows: from an unexcited vertex, she moves to a uniformly random neighbour, whereas from an excited vertex, she takes one step along some fixed shortest path towards the target vertex. We show, perhaps counterintuitively, that the geodesic-bias can slow the random walker down exponentially: there exist connected, bounded-degree n-vertex graphs with excitations where the expected hitting time of a fixed target is at least exp(4 root n/100).