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.

  • $\begingroup$ Interesting question. Can you elaborate on why you think the inequality should hold? And tell us how you attempted to solve the problem and why it failed? $\endgroup$ – Pascal Maillard May 23 '12 at 8:18

In Proposition 5 of Chapter 14 of the unpublished book on Markov chains by Aldous and Fill, they show that for continuous time reversible Markov chains, \[ I \le \max\{ \mathbb{E}_i T_j, i,j \in V\}, \] where $\mathbb{E}_i T_j$ is the expected time, starting from state i, until state j is visited. The preceding maximum is clearly bounded from above by $C$, so it follows that $I \le C$. This includes the case of continuous time simple random walk on a connected graph $G$, and a similar argument can be used to to establish the bound for lazy simple random walk on $G$ (in fact, the martingale argument used in the proof is originally described in Chapter 3 of the same book for the case of discrete time walks).


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.