2
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ 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')$. $\endgroup$
    – Did
    Commented Jan 11, 2011 at 8:33
  • $\begingroup$ 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. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jan 11, 2011 at 18:32
  • $\begingroup$ @Ori: indeed, and more generally, for every random walk with uniform stationary measure. $\endgroup$
    – Did
    Commented Jan 11, 2011 at 19:47
  • $\begingroup$ @Didier: reversible random walk with uniform stationary distribution. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jan 11, 2011 at 20:06
  • $\begingroup$ @Ori: yes, reversible $\endgroup$
    – Did
    Commented Jan 12, 2011 at 6:28

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Bill, thanks for clarification. I have overworked the question to make it more clear. $\endgroup$
    – Chris
    Commented Jan 11, 2011 at 7:32
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Chris
    Commented Jan 11, 2011 at 7:34

You must log in to answer this question.

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