Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
You need to be more specific about which graphs you want. The first return could happen at an odd step. The graph can be regular but have different statistics for each possible starting vertex. –  Aaron Meyerowitz Aug 25 '11 at 16:59
    
Aaron Meyerowitz: thanks for the comment. I am interested in probability of first return at $t$. Only for $d=2$ this is only non-zero for $2t$, you are right, fixed it. The graphs I want are finite of size $k$, wrapped borders, and $d-regular$ with small $d$. Does this make it clear? –  Chris Aug 26 '11 at 8:23

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Your description of w(x) makes unclear (at least, to me) whether you mean the generating function of all the walks (in which case the result is false) or the generating functions of the loops only. For example, re your last paragraph, only the diagonals of the powers of the adjacency matrix are required. –  Did Aug 26 '11 at 0:58
    
I mistyped. Of course I meant the powers of the eigenvalues. I'll edit it, thanks. –  Brendan McKay Aug 26 '11 at 1:12
    
Sorry but the coefficient of $x^j$ in your $w(x)$ is NOT the sum of the $j$-th powers of the eigenvalues of the adjacency matrix. –  Did Aug 26 '11 at 1:30
    
You are correct, that is for all starting points taken together. I should wake up first and type second, rather than the other way around. I'll remove that part of my answer. One thing to note is that the originator seems to be interested in a vertex transitive graph, in which case the trace divided by $n$ is what is needed. –  Brendan McKay Aug 26 '11 at 3:44
    
Brendan, Didier: Thanks for the insight and both your answers. Do you have any references for me where the topic is discussed and maybe closed forms are derived for finite graphs? I have found quite a lot about probability of return now, but very few on probability of first return. –  Chris Aug 26 '11 at 19:13

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.