Timeline for Probability of first return to starting vertex in Random walk on regular finite graph
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2011 at 7:05 | vote | accept | Chris | ||
| Aug 27, 2011 at 0:06 | comment | added | Did | Hmmmm... This is a standard topic of first courses on finite Markov chains. A classic reference is Finite Markov chains by Kemeny and Snell. More recent and very stimulating is the book Markov chains by Norris. (Please use the @ thing if you want your comment to be notified to somebody else than the author of the post you are commenting on. I read yours by chance.) | |
| Aug 26, 2011 at 19:13 | comment | added | Chris | Brendan, Didier: Thanks for the insight and both your answers. Do you have any references for me where the topic is discussed and maybe closed forms are derived for finite graphs? I have found quite a lot about probability of return now, but very few on probability of first return. | |
| Aug 26, 2011 at 3:46 | history | edited | Brendan McKay | CC BY-SA 3.0 |
correct silly error
|
| Aug 26, 2011 at 3:44 | comment | added | Brendan McKay | You are correct, that is for all starting points taken together. I should wake up first and type second, rather than the other way around. I'll remove that part of my answer. One thing to note is that the originator seems to be interested in a vertex transitive graph, in which case the trace divided by $n$ is what is needed. | |
| Aug 26, 2011 at 1:30 | comment | added | Did | Sorry but the coefficient of $x^j$ in your $w(x)$ is NOT the sum of the $j$-th powers of the eigenvalues of the adjacency matrix. | |
| Aug 26, 2011 at 1:27 | history | edited | Brendan McKay | CC BY-SA 3.0 |
make corrections, add note on asymptotics
|
| Aug 26, 2011 at 1:12 | comment | added | Brendan McKay | I mistyped. Of course I meant the powers of the eigenvalues. I'll edit it, thanks. | |
| Aug 26, 2011 at 0:58 | comment | added | Did | Your description of w(x) makes unclear (at least, to me) whether you mean the generating function of all the walks (in which case the result is false) or the generating functions of the loops only. For example, re your last paragraph, only the diagonals of the powers of the adjacency matrix are required. | |
| Aug 25, 2011 at 23:38 | history | answered | Brendan McKay | CC BY-SA 3.0 |