Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Pascal Maillard May 23 '12 at 8:18

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
Thank you!$~~~~~$ –  user21162 May 23 '12 at 20:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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