5
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ You seem to be talking simultaneously of recurrence time (i.e. the time of the first return to the starting vertex) and of the probability to be at the starting vertex at a given time. These are not the same and you could say which one concerns you. $\endgroup$
    – Did
    Commented Mar 26, 2011 at 16:38
  • $\begingroup$ Didier: thanks, I have tried to make it more clear. I am interested in the probability to be at the starting vertex at a given time. $\endgroup$
    – Chris
    Commented Mar 26, 2011 at 19:03
  • 1
    $\begingroup$ Chris: a vast amount is known about this. See, for example, the book by Woess "Random Walks on Infinite Graphs and Groups", CUP. For finite graphs there's a huge amount of research. Do you have a more specific question? $\endgroup$
    – Ben Green
    Commented Mar 26, 2011 at 19:29
  • $\begingroup$ Ben: I am interested in the CDF that is built out of the probabilities to be at the starting vertex at step $n$ over all vertices of the graph, vertices weighted by their steady state probability to actually start at this vertex. I can calculate this CDF in numerical form out of the random walk probability matrices. Now I am interested if for some families of graphs there exist easier methods. The below answer by Didier is for example exactly such a relation I am interested which is for finite circles. $\endgroup$
    – Chris
    Commented Mar 27, 2011 at 9:48
  • $\begingroup$ Ben: after having a look at the book I agree that is is of great value. Especially right at the beginning it is stated that $p^{(2n)}(0,0) \sim C_d n^{-d/2}$ for graphs in $Z^d$. Having such a relation for finite graphs that takes into account the size of the graph would be great. Is such a relation known? $\endgroup$
    – Chris
    Commented Mar 27, 2011 at 12:18

2 Answers 2

Reset to default
1
$\begingroup$

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. $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Didier: thanks! This is exactly the information I was hoping for. Are there maybe similar formulas for other finite graphs? FYI: As reference for your formula I found Eq.4 in S. Chandrasekhar, "Stochastic Problems in Physics and Astronomy". $\endgroup$
    – Chris
    Commented Mar 27, 2011 at 10:37
  • $\begingroup$ You are welcome. Re your comment to @Ben, omitting aperiodicity conditions, on finite graphs the situation is similar to what I describe for $\mathbb{Z}/N\mathbb{Z}$ with $N$ odd. Namely, $p^{(n)}_{00}(G)\to\pi_G(0)$ where $\pi_G$ denotes the stationary probability distribution of the simple random walk on $G$. Hence, for each vertex $x$ of $G$, $\pi_G(x)$ is the degree of $x$ divided by the sum of the degrees of all the vertices of $G$. $\endgroup$
    – Did
    Commented Mar 27, 2011 at 13:38
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Steve: thanks, I also found this in "Introduction to Probability" by Grinstead and Snell, Chapter 11. This is quite interesting, too, for me. $\endgroup$
    – Chris
    Commented Mar 27, 2011 at 9:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .