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

Hi, I am interested in the distribution of return times in simple random walks on finite graphs.

Let $G$ be a connected finite graph with, with two independent random walks. If both random walks start are at time $t_0$ on the same node in the graph, how long does it take until they meet again? I have not found papers on this specific problem, but read that is can be transformed to a single random walk and the question of when the random walk returns to exactly the node where it is at $t_0$.

As such I am interested in the distribution of these return times. Generally I know how to compute the numeric values of the distribution for a given graph. But my question is whether this can be modeled through a given distribution (e.g. exponential).

Besides the PDF I am more interested in the CDF of this return time distribution.

share|improve this question
    
The first time when two independent random walks on $G$ both starting from $x_0$ with transition probabilities $p$ meet is the first return time to the diagonal $\Delta=\{(x,x);x\in G\}\subset G\times G$ by the random walk on $G\times G$ starting from $(x_0,x_0)$ whose transition probabilities $p_2$ are given by $p_2((x,y),(x',y'))=p(x,x')p(y,y')$. –  Did Jan 11 '11 at 8:33
    
More clarifications are needed: are we talking about simple random walks? For a SRW on a regular graph the following is true: the probability of 2 independent SRW starting at the same vertex to be in the same place at some time $t$ is equal to the probability that a single SRW on the same graph returns to the starting vertex at time $2t$. But this does not say anything about the first time 2 SRWs meet. –  Ori Gurel-Gurevich Jan 11 '11 at 18:32
    
@Ori: indeed, and more generally, for every random walk with uniform stationary measure. –  Did Jan 11 '11 at 19:47
    
@Didier: reversible random walk with uniform stationary distribution. –  Ori Gurel-Gurevich Jan 11 '11 at 20:06
    
@Ori: yes, reversible –  Did Jan 12 '11 at 6:28
show 4 more comments

2 Answers

up vote 3 down vote accepted

I assume you mean the distribution of the time of first return, and I assume you're talking about finite graphs.

I'll volunteer the naive answer: let $M$ be the matrix of transition probabilities for your random walk, and let $M_i$ be the matrix obtained by modifyiong $M$ to make the $i$th column all 0's except for $1$ in the $(i,i)$ entry. In other words, it's the matrix for a new random walk that matches the old one, except whenever you get to $i$, you're trapped forever.

The CDF for first return from $j$ to $i$ is the sequence of $(i,j)$ entries of $M_i^{n-1} \cdot M$: you start off with $M$, and afterward use $M_i$, and see if you've gotten from $j$ to $i$.

If you transform $M_i$ into Jordan canonical form, there is a closed formula for all its powers $\cdot M$; the $(i,j)$ entry is a linear functional on those powers.

If you want numerical answers for not-too-huge graphs, this should be easily workable. If you want answers for a totally general directed graph with weighted edges, this corresponds to a totally general matrix $M$, and it's unreasonable to expect any better answer. If you have in mind some particular class of graphs with nice properties and nice random walks, then a lot more can be said, but I'm not an expert so I won't plunge in: perhaps some experts will say something about what's known.

share|improve this answer
    
Bill, thanks for clarification. I have overworked the question to make it more clear. –  Chris Jan 11 '11 at 7:32
add comment

The question you ask is pretty broad, and it's not clear to me what kind of answers you seek. In fact, I suggest you clean up the question a little bit (for example, what does "the return times for every pair in the graph." mean?).

I'm not sure whether this is relevant, but Asaf Nachmias and I have a paper on some properties of the distribution of the first time a simple random walk returns to its starting point on an infinite graph. The results can also be adapted, to some extent, to finite graphs.

share|improve this answer
    
Thanks Ori, the paper you mention goes into an interesting direction. I am looking to determine such a return time distribution for a given graph. –  Chris Jan 11 '11 at 7:34
add comment

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.