On hitting times for a simple random walk on dense Erdös-Rényi random graphs

DOI10.1016/J.SPL.2014.02.017zbMATH Open1295.05214arXiv1310.1792OpenAlexW2963626708MaRDI QIDQ2453906FDOQ2453906

Authors: Felipe Torres, M. Löwe 

Publication date: 11 June 2014

Published in: Statistics \& Probability Letters (Search for Journal in Brave)

Abstract: Let $G(N,p)=(V,E)$ be an Erd"os-R'enyi random graph and $(X_n{)}_{ninmathbbN}$ be a simple random walk on it. We study the the order of magnitude of $su{m}_{iinV}p{i}_i{h}_{ij}$ where $p{i}_i=d_i/2|E|$ for $d_i$ the number of neighbors of node $i$ and $h_{ij}$ the hitting time for $(X_n{)}_{ninmathbbN}$ between nodes $i$ and $j$, in a regime of $p=p(N)$ such that $G(N,p)$ is almost surely connected as $Noinfty$. Our main result is that $su{m}_{iinV}p{i}_i{h}_{ij}$ is almost surely of order $N(1+o(1))$ as $Noinfty$, which coincides with previous results in the physics literature cite{sood}, though our techniques are based on large deviations bounds on the number of neighbors of a typical node and the number of edges in $G(N,p)$ together with recent work on bounds on the spectrum of the (random) adjacency matrix of $G(N,p)$.

Full work available at URL: https://arxiv.org/abs/1310.1792

Recommendations

• A central limit theorem for the mean starting hitting time for a random walk on a random graph
• Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs
• Return probabilities and hitting times of random walks on sparse Erdös-Rényi graphs
• Random walks on the random graph
• Bounds on expected hitting times for a random walk on a connected graph

zbMATH Keywords

hitting timespectral decompositionrandom walks on random graphsspectrum of random graphsErdös-Rényi random graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Random walks on graphs (05C81)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Random graphs and complex networks. Volume 1
• Title not available (Why is that?)
• Probability on graphs. Random processes on graphs and lattices.
• Random Walks on Infinite Graphs and Groups
• Random graphs.
• Probability on trees and networks
• Title not available (Why is that?)
• Complex graphs and networks
• Title not available (Why is that?)
• First-passage properties of the Erdos–Renyi random graph

Cited In (17)

• The hitting time of random walk on unicyclic graphs
• Hitting and commute times in large random neighborhood graphs
• Random walks and diffusion on networks
• First hitting times of simple random walks on graphs with congestion points
• The resistance perturbation distance: a metric for the analysis of dynamic networks
• Expected hitting times for random walks on the \(k\)-triangle graph and their applications
• The hitting times of random walks on bicyclic graphs
• Concentration of hitting times in Erdős-Rényi graphs
• Return probabilities and hitting times of random walks on sparse Erdös-Rényi graphs
• Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs
• Decomposing hitting times of walks on graphs into simpler ones
• The distribution of first hitting times of random walks on directed Erdős–Rényi networks
• Hitting times, commute times, and cover times for random walks on random hypergraphs
• The mixing time of the giant component of a random graph
• Expected hitting times for a random walk on a connected graph
• Hitting times for random walks on subdivision and triangulation graphs
• A central limit theorem for the mean starting hitting time for a random walk on a random graph

This page was built for publication: On hitting times for a simple random walk on dense Erdös-Rényi random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453906)