Return to 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

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

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 $2t$. This is in contrast to the earlier question that was on the probability of return at $2t$. 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 $2t$ is somehow a subset of the probability of return at $2t$, 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 $2t$, and probability of first return at $2t$ always the same? How does it change with $d$ and $k$?

Thanks! Chris

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