Hitting times for Random Walks on the stochastic block model

Matthias Löwe, Sara Terveer

Published 2024-01-15Version 1

We analyze hitting times of simple random walk on realizations of the stochastic block model. We show that under some natural assumptions the average starting hitting time as well as the average target hitting time are asymptotically almost surely given by $N(1+o(1))$. We also show a central limit theorem for the average target hitting time. Our main techniques are a spectral decomposition of these hitting times, a spectral analysis of the adjacency matrix and the graph Laplacian, respectively, as well as a form of the Delta method.