Slowdown for the geodesic-biased random walk (Q2279090)

Let \(G\) be a connected graph with \(n\) vertices. The \emph{geodesic-biased random walk on \(G\)} is a Markov process on the vertices of \(G\) constructed as follows. A target vertex \(b\) is defined, as well as a set \(\mathcal{X}\) of vertices of \(G\) which are considered exited. When at a non-exited vertex, the geodesic-biased random walk jumps to a neighbour chosen uniformly at random, whereas on an exited vertex, the walker jumps to a neighbour on a geodesic path towards the target vertex. The aim of this article is to show that, perhaps counter-intuitively, the expected hitting time of the target vertex \(b\) by the geodesic-biased random walker can be significantly larger than in a regular random walk. Recall that in a graph of \(n\) vertices with bounded degree, the expected hitting time of a target vertex is at most of order \(n^2\). In this article, the authors construct explicitly a sequence of graphs with \(n\) vertices and only one excited vertex such that the expected hitting time of the target vertex is of order \(\exp(\frac{n^{1/4} \log n}{100})\) as \(n \to \infty\). They also construct a sequence of graphs with \(n\) vertices and degree bounded by \(3\), among which \(O(n^{1/2})\) are exited vertices, such that the expected hitting time of the target vertex is of order \(\exp(\frac{n^{1/4}}{100})\).