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.



Exist closed forms of the distribution of return time in markov chains?
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.


