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

Let $G(N,p)=(V,E)$ be an Erdös-Rényi random graph and $(X_n)_{n \in \mathbb{N}}$ be a simple random walk on it. We study the the order of magnitude of $\sum_{i \in V} π_ih_{ij}$ where $π_i=d_i / 2|E|$ for $d_i$ the number of neighbors of node $i$ and $h_{ij}$ the hitting time for $(X_n)_{n \in \mathbb{N}}$ between nodes $i$ and $j$, in a regime of $p=p(N)$ such that $G(N,p)$ is almost surely connected as $N\to\infty$. Our main result is that $\sum_{i \in V} π_ih_{ij}$ is almost surely of order $N(1+o(1))$ as $N\to \infty$, 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)$.

No reviews yet.

No comments yet.