9
$\begingroup$

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: http://www.stat.berkeley.edu/~aldous/RWG/book.html.

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?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – fedja
    Commented Sep 1, 2010 at 1:36
  • $\begingroup$ Thanks for the feedback. Do you have any references on the self-intersection question? $\endgroup$
    – Roberto Imbuzeiro Oliveira
    Commented Sep 1, 2010 at 15:48

1 Answer 1

Reset to default
2
$\begingroup$

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.

http://arxiv.org/abs/1009.0664

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$
    – sleepless in beantown
    Commented Sep 4, 2010 at 3:55
  • $\begingroup$ 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. $\endgroup$
    – Roberto Imbuzeiro Oliveira
    Commented Sep 22, 2010 at 11:52
  • $\begingroup$ Comment: very nice. Just what I was looking for. =) $\endgroup$
    – petrelharp
    Commented Oct 21, 2013 at 17:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .