Skip to main content
1 of 2
user21162
  • 571
  • 3
  • 10

Cover time and intersection time of random walks

Consider a simple lazy random walk on an $n$-vertex undirected, connected graph: this is the Markov chain which transitions from $i$ to $j$ with probability $p_{ij}=1/(2d(i))$ where $d(i)$ is the degree of node $i$. Note that $p_{ii}=1/2$ for all $i$. Define $C(i)$ be the expected time until a walk starting from node $i$ visits every vertex and let $C = \max_i C(i)$. Let $I(k,l)$ be the expected time until two random walks, starting at vertices $k$ and $l$, intersect (i.e., until they visit the same vertex at the same time). Let $I = \max_{k,l} I(k,l)$.

My question is: can we bound $I$ in terms of $C$? Specifically, is it true that $$ \frac{I}{C} \leq k \log^l n$$ for some constants $k,l$ independent of $n$ and of the graph?

I asked this question on math.stackexchange a week ago without receiving an answer.

user21162
  • 571
  • 3
  • 10