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



Probability of return at step $n$ of a Random walk to its starting vertex
The simple random walk on the circle graph $\mathbb{Z}/N\mathbb{Z}$ of size $N$ can be realized as the class modulo $N$ of simple random walk on $\mathbb{Z}$, hence
$$
p\_{00}^{(n)}(\mathbb{Z}/N\mathbb{Z})=\sum\_{k\in\mathbb{Z}}p\_{0,kN}^{(n)}(\mathbb{Z}).
$$
Now, for every $k$,
$$
p\_{0,k}^{(n)}(\mathbb{Z})=2^{-n}{n\choose (n+k)/2},
$$
with the convention that ${n\choose i}=0$ for every noninteger $i$ and every integer $i\le -1$ and every integer $i\ge n+1$.


On the other hand, this is also a random walk on a finite graph hence the stationary distribution allows to shortcut these exact computations for large $n$. For every odd $N$,
$$
\lim\_{n\to+\infty}p\_{00}^{(n)}(\mathbb{Z}/N\mathbb{Z})=\frac1N.
$$
For every even $N$, $p\_{00}^{(2n+1)}(\mathbb{Z}/N\mathbb{Z})=0$ for every $n$ and
$$
\lim\_{n\to+\infty}p\_{00}^{(2n)}(\mathbb{Z}/N\mathbb{Z})=\frac2N.
$$


