Slowdown for the geodesic-biased random walk
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})\).
- A balanced excited random walk
- A survey of random processes with reinforcement
- Excited random walk
- Excited random walk against a wall
- Excited random walks: results, methods, open problems
- Expected hitting times for a random walk on a connected graph
- Extreme slowdowns for one-dimensional excited random walks
- Large deviations and slowdown asymptotics for one-dimensional excited random walks
- Locating a target with an agent guided by unreliable local advice, how to beat the random walk when you have a clock?
- Maximum hitting time for random walks on graphs
- Monotonicity and regularity of the speed for excited random walks in higher dimensions
- Multi-excited random walks on integers
- On strict monotonicity of the speed for excited random walks in one dimension
- Searching a Tree with Permanently Noisy Advice
- The infinite differentiability of the speed for excited random walks
This page was built for publication: Slowdown for the geodesic-biased random walk
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279090)
