MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Start a random walk from each vertex of a graph $G$. Let the walkers evolve independently, except that when two of the walkers meet (ie. occupy the same vertex at the same time), they coalesce into one single walker. (Alternatively, one may label the walkers with numbers $1,\dots,n$ and say that walker $i$ is killed at the first time it meets a walker with smaller index.)

It is not hard to show that, if $G$ is connected and finite, there will be a first time $C$ when all walks will have coalesced into one ($C$ is the first time when only one alive particle remains in the "killing description"). The following is Open Problem $13$ in Chapter $14$ of Aldous and Fill's manuscript:

Problem: Prove that there exists a universal constant such that: $$E(C)\leq K\max_{v,w\in V(G)}E_v(H_w)$$ where $V(G)$ is the vertex set of $G$ and $H_w$ is the hitting time of vertex $w$.

My question is: does anyone know of any work on this problem? I know there is a paper by Cox which studies the distributional limit of $C$ over $Z_n^d$ for $n\gg 1$ and $d$ fixed; a solution for the Problem follows from this in this specific family of graphs. What else is out there? Has the problem actually been solved by someone?

share|cite|improve this question
I know some people who work on this (like, say, Yuval Peres). I haven't heard of any improvement over the "trivial" bound with $K\log n$ instead of $K$. So, if you have some good idea for this problem, by all means, go ahead and solve it. Another funny open problem is to show that the typical self-intersection time for non-backtracking random walk on a graph with all vertex degrees greater than 2 is not more than $K\sqrt n$. If you remove the non-backtracking condition, it is true and not too hard. – fedja Sep 1 '10 at 1:36
Thanks for the feedback. Do you have any references on the self-intersection question? – Roberto Imbuzeiro Oliveira Sep 1 '10 at 15:48

fedja was right to guess that I had an idea to solve the problem. Reading that Yuval Peres is working on it scared me into writing something down as quickly as possible. Any comments on my manuscript (below) are very welcome.

share|cite|improve this answer
Question: why are you using a continuous time random walk on a graph instead of a discrete time random walk? What distribution do you use for the distance which a walker will travel during each of its steps? I can see how to define a continuous time random walk on $\mathbb{R}^n$ where you can have it move a distance $d$ taken from a normal distribution $\overbar(x)+\sigma$ for each time step, or have it move 1−unit distance for a normal−distributed timestep $\overbar(t)+\sigma_{t}$. Thank you for putting the pdf file on your server. (I have only read the first 2 pages -> my 1st question) – sleepless in beantown Sep 4 '10 at 3:55
A continuous-time Markov chain over a finite set $S$ is a process such that, for all distinct $x,y\in S$, the chance of being at $y$ at time $t+\epsilon$, given that the state at time $t$ is $x$, $q(x,y)\epsilon + o(\epsilon)$, where $q(x,y)$ are the so-called transition rates. This moves by "jumps" only. – Roberto Imbuzeiro Oliveira Sep 22 '10 at 11:52
Comment: very nice. Just what I was looking for. =) – petrelharp Oct 21 '13 at 17:14

Your Answer


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.