Hi, this is related to this earlier question.
Given Random walk on a regular graph $G=(V,E)$. The Random walk is simple so that transition probabilities are $1/\text{deg}(v_i)$, and time is in discrete steps $t_1, t_2, \ldots$.
I am interested in the probability of first return to the starting vertex at time $t$. This is in contrast to the earlier question that was on the probability of return at $t$. I.g. I only want to take into account the first return for the probability distribution, and start a new sample on every return.
The graphs I am interested in are $d$-regular, with small $d$ i.e. $d=2,3,4$, and finite with wrapper borders. I.e. for $d=2$ the graph of size $k$ is a ring with $k$ vertices, for $d=3$ the graph is a lattice with wrapper borders. This allows to model the Random walk with modulo jumps at the borders.
I know that the probability of first return at $t$ is somehow a subset of the probability of return at $t$, and found in the book of Grinstead and Snell Theorem 12.3 the relation between the two for infinite graphs with $d=2$, i.e. Random Walk on infinite line of integers. There, the probability of first return at time $2t$ for an infinite line is $\frac{\binom{2t}{t}}{(2t-1)2^{2t}}$, in contrast to the probability of return at time $2t$ which is $\frac{\binom{2t}{t}}{2^{2t}}$.
Questions:
-Is there a closed form for the probability of first return to the starting vertex for finite regular graphs for arbitrary $d$ and $k$? Or for arbitrary $k$ for some small $d$?
-Is the relation between probability of return at $t$, and probability of first return at $t$ always the same? How does it change with $d$ and $k$?
Thanks!
Chris
Best Answer
For a regular graph, each walk of a given length has the same probability, so let's just consider the number of walks.
A walk starting and ending at a given vertex is comprised of zero or more pieces that consist of non-trivial walks that return to the start only on their last step. So if $w(x)$ is the ordinary generating function of all walks that end at the starting vertex, and $r(x)$ is the ordinary generating function of the non-trivial walks that first return to the start on the last step, then $$ w(x) = 1 + r(x) + r(x)^2 + \cdots = \frac{1}{1-r(x)},$$ or equivalently $$ r(x) = \frac{w(x)-1}{w(x)}.$$ If you know the coefficients of $w(x)$, this lets you get the coefficients of $r(x)$.
Since these generating functions are rational functions (see Didier's answer for a proof), the asymptotics of the probability you want are determined by the smallest (complex) solution of $w(x)=0$.