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
 A: 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.
$$
A: If $P$ is the transition matrix of a well-behaved Markov chain on a finite state space, the probability of going from state $j$ to state $k$ in $n$ steps is just $(P^n)_{jk}$. To see this, consider the forward Chapman-Kolmogorov equation.
Since an earlier version of the question seemed to express an interest in recurrence times (a complementary rather than identical topic), I'll also provide what I hope is a helpful capsule following 6.6 of Bremaud. If $P$ is the transition matrix of a well-behaved Markov chain on a finite state space and $\pi$ is the corresponding invariant distribution satisfying $\pi P = \pi$, then the fundamental matrix is $Z := (I-[P-1\pi])^{-1}$, where $1$ denotes a column vector of ones. The entries of $Z$ can be used to get information about the expected time to go from state $j$ to state $k$, etc.
