Skip to main content
MathOverflow

Return to Question

deleted 91 characters in body; edited title
Source Link
Chris
Chris
  • 65
  • 1
  • 6

Distribution/probability Probability of recurrence timesreturn at step $n$ of a Random walk to its starting vertex

Hi,

given a discrete simple Random walk on a symmetric graph, what is known about the probability of the random walker to return to a starting site at step $n$?

  Specifically, I am interested in the probability or returnthat at step $n$ the random walk has returned to aits starting vertex. I know there exists work on the mean value of this recurrence, however I have not found much on the probability distribution.

What I have found is e.g. in the Book "Markov Chains" by Norris that shows for Random walk on a line in $Z^1$ the probability to return at step $2n$ is $p_{00}^{(2n)} = \binom{2n}{n} \left( \frac{1}{2} \right)^{2n}$. Furthermore, Norris shows that for a lattice in $Z^2$ this return probability at step $n$ is $p_{00}^{(2n)} = \left( \binom{2n}{n} \left( \frac{1}{2} \right)^{2n} \right)^2$.

What is known for finite graphs (e.g. finite lines in $Z^1$ and finite regular lattices in $Z^2$ which I guess can easily be extended from the above by including special cases to be at the border) and is there more known for special families of finite graphs? E.g. is there something known for regular graphs given a degree and size of the graph, or for rings etc.

Thanks, Christoph

Distribution/probability of recurrence times of Random walk

Hi,

given a discrete simple Random walk on a symmetric graph, what is known about the probability of the random walker to return to a starting site?

  Specifically, I am interested in the probability or return at step $n$ to a starting vertex. I know there exists work on the mean value of this recurrence, however I have not found much on the probability distribution.

What I have found is e.g. in the Book "Markov Chains" by Norris that shows for Random walk on a line in $Z^1$ the probability to return at step $2n$ is $p_{00}^{(2n)} = \binom{2n}{n} \left( \frac{1}{2} \right)^{2n}$. Furthermore, Norris shows that for a lattice in $Z^2$ this return probability at step $n$ is $p_{00}^{(2n)} = \left( \binom{2n}{n} \left( \frac{1}{2} \right)^{2n} \right)^2$.

What is known for finite graphs (e.g. finite lines in $Z^1$ and finite regular lattices in $Z^2$ which I guess can easily be extended from the above by including special cases to be at the border) and is there more known for special families of finite graphs? E.g. is there something known for regular graphs given a degree and size of the graph, or for rings etc.

Thanks, Christoph

Probability of return at step $n$ of a Random walk to its starting vertex

Hi,

given a discrete simple Random walk on a symmetric graph, what is known about the probability of the random walker to return to a starting site at step $n$? Specifically, I am interested in the probability that at step $n$ the random walk has returned to its starting vertex.

What I have found is e.g. in the Book "Markov Chains" by Norris that shows for Random walk on a line in $Z^1$ the probability to return at step $2n$ is $p_{00}^{(2n)} = \binom{2n}{n} \left( \frac{1}{2} \right)^{2n}$. Furthermore, Norris shows that for a lattice in $Z^2$ this return probability at step $n$ is $p_{00}^{(2n)} = \left( \binom{2n}{n} \left( \frac{1}{2} \right)^{2n} \right)^2$.

What is known for finite graphs (e.g. finite lines in $Z^1$ and finite regular lattices in $Z^2$ which I guess can easily be extended from the above by including special cases to be at the border) and is there more known for special families of finite graphs? E.g. is there something known for regular graphs given a degree and size of the graph, or for rings etc.

Thanks, Christoph

Source Link
Chris
Chris
  • 65
  • 1
  • 6

Distribution/probability of recurrence times of Random walk

Hi,

given a discrete simple Random walk on a symmetric graph, what is known about the probability of the random walker to return to a starting site?

Specifically, I am interested in the probability or return at step $n$ to a starting vertex. I know there exists work on the mean value of this recurrence, however I have not found much on the probability distribution.

What I have found is e.g. in the Book "Markov Chains" by Norris that shows for Random walk on a line in $Z^1$ the probability to return at step $2n$ is $p_{00}^{(2n)} = \binom{2n}{n} \left( \frac{1}{2} \right)^{2n}$. Furthermore, Norris shows that for a lattice in $Z^2$ this return probability at step $n$ is $p_{00}^{(2n)} = \left( \binom{2n}{n} \left( \frac{1}{2} \right)^{2n} \right)^2$.

What is known for finite graphs (e.g. finite lines in $Z^1$ and finite regular lattices in $Z^2$ which I guess can easily be extended from the above by including special cases to be at the border) and is there more known for special families of finite graphs? E.g. is there something known for regular graphs given a degree and size of the graph, or for rings etc.

Thanks, Christoph