Theoretical analysis reveals an exact formula for random walk hitting times in binomial random graphs, highlighting how basic graph structure governs arrival steps across sparse regimes.
Fix k≥ 2, choose log nn(k-1)/k≤ p≤ 1-Ω(log⁴ n/n), and consider G~ G(n,p). For any pair of vertices v,w∈ V(G), we give a simple and precise formula for the expected number of steps that a random walk on G starting at w needs to first arrive at v. The formula only depends on basic structural properties of G. This improves and extends recent results of Ottolini and Steinerberger, as well as Ottolini, who considered this problem for constant as well as for mildly vanishing p.
No takes yet. Share an insight, caveat, or question.
Granet et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: