Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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: how big can $I/C$ get as a function of the number of vertices $n$? Is it true that $I/C$ is upper bounded by a constant which is independent of $n$ or of the graph? If not, is it true that $$ \frac{I}{C} \leq k \log^l n$$ for some constants $k,l$ independent of $n$ and of the graph?

share|improve this question
2  
Just an observation. Take a graph with two vertices and one edge connecting the two. Start the two walks on either vertex. Then $C=1$ but $I=\infty$ since the two walks never meet. From this it might be advisable to allow for a lazy random walk which has a chance of staying at the current vertex. At the very least these issues of periodicity are likely to muck things up. –  Alex R. May 11 '12 at 2:32
    
Also i'm guessing $I(k,l)$ is the expected time until the two random walks meet? –  Alex R. May 11 '12 at 2:52
    
Let $C_v$ be the expected cover time starting at vertex $v$. Then there is a relatively straightforward result that says $C_v\leq 4nm$, where $n$ is the number of vertices and $m$ the number of edges. This a pretty terrible upper bound but it gives you an idea for how fast $C_v$ can grow. See this link for reference: cs.iastate.edu/~pavan/633/lec7.pdf –  Alex R. May 11 '12 at 3:06
    
Sam, thanks, indeed I forgot to make the random walk lazy. Fixed now. –  robinson May 11 '12 at 23:24
    
answered here: mathoverflow.net/questions/97698/… –  robinson Jan 25 '13 at 21:14

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.