Probability of first return to starting vertex in Random walk on regular finite graph

Question

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

Answer 1

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$.

Answer 2

A minor remark is that in general the walk can be at its starting point, not only at even times but possibly at odd times as well. Now, let $v$ denote a given vertex, $s_0=1$ and, for every integer $t\ge1$, $s_t$ the probability that the walk starting from $v$ is at $v$ at time $t$ and $r_t$ the probability that the walk starting from $v$ returns at $v$ for the first time at time $t$. Then, the so-called strong Markov property of the random walk at the time of its first return at $v$ shows that, for every $t\ge1$, $$ s_t=\sum_{u=1}^tr_us_{t-u}. $$ The usual way to exploit this is to consider the generating functions, defined at least for every $|x|\le1$ by $$ s(x)=\sum_{t=0}^{+\infty}s_tx^t,\qquad r(x)=\sum_{t=1}^{+\infty}r_tx^t. $$ The recursion above translates as $s(x)=1+r(x)s(x)$, and finally $$ r(x)=\frac{s(x)-1}{s(x)}. $$ Note finally that $s(x)=(I-xQ)^{-1}(v,v)$ where $Q$ is the transition matrix of the random walk, defined by $Q(u,w)=$ the probability to be at vertex $w$ at time $t+1$ conditionally on being at vertex $u$ at time $t$ (this does not depend on $t$).