Hi, this is related to [this](https://mathoverflow.net/questions/59661/probability-of-return-at-step-n-of-a-random-walk-to-its-starting-vertex) 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



Probability of first return to starting vertex in Random walk on regular finite graph
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$.


