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

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

Abstract: Let

G (N, p) = (V, E)

be an Erd"os-R'enyi random graph and

(X_{n})_{n i n m a t h b b N}

be a simple random walk on it. We study the the order of magnitude of

s u m_{i i n V} p i_{i} h_{i j}

where

p i_{i} = d_{i} / 2 | E |

for

d_{i}

the number of neighbors of node

i

and

h_{i j}

the hitting time for

(X_{n})_{n i n m a t h b b N}

between nodes

i

and

j

, in a regime of

p = p (N)

such that

G (N, p)

is almost surely connected as

N o i n f t y

. Our main result is that

s u m_{i i n V} p i_{i} h_{i j}

is almost surely of order

N (1 + o (1))

as

N o i n f t y

, 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)

.

Recommendations

Cites work

Cited in

(17)

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)