Comparison of Mean Hitting Times for a Degree-Biased Random Walk

International audienceConsider the random walk on graphs such that, at each step, the next visited vertex is a neighbor of the current vertex, chosen with probability proportional to the inverse of the square root of its degree. On one hand, for every graph with n vertices, the maximal mean hitting time for this degree-biased random walk is asymptotically dominated by n 2. On the other hand, the maximal mean hitting time for the simple random walk is asymptotically dominated by n 3. Yet, in this article, we exhibit for each positive integer n: • A graph of size n with maximal mean hitting time strictly smaller for the simple random walk than for the degree-biased one. • A graph of size n with mean hitting time of a so called root vertex strictly smaller for the simple random walk than for the degree-biased one