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

2more comments