Cover time and intersection time of random walks

Question

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.

Answer 1

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