You are here

Hitting times in Erdös-Rényi random graphs

Andrea Ottolini, University of Washington
Monday, November 27, 2023 - 2:30pm to 3:20pm
SMI 305

Consider a dense Erdös-Rényi random graphs with parameters \$n\$ and \$p\$, with \$p\$ fixed in (0,1). Let \$H_n(p)\$ be the hitting time between two distinct vertices: run simple random walk from a vertex \$w\$, wait until it hits another vertex \$v\$, and average over the random walk. What does the distribution of \$H_n(p)\$ look like? Heuristic from the physics literature suggests \$H_n(p)\$ concentrates around \$n\$. Löwe and Terveer settled the question when the starting point is randomized according to the stationary distribution, showing also a central limit theorem for the fluctuations. In joint work with Steinerberger, we show that \$H_n(p)\$ satisfies, with high probability and up to \$o(1)\$ error, an extremely neat and simple formula. Easy corollaries include a central limit theorem for \$H_n(p)\$ from any starting point (deterministic or random).

Event Type: 
Event Subcalendar: 
Share