Timeline for self-avoidance time of random walk
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Dec 19, 2014 at 2:49 | history | suggested | Tadashi |
Added relevant tag
|
|
| Dec 19, 2014 at 2:21 | review | Suggested edits | |||
| S Dec 19, 2014 at 2:49 | |||||
| Dec 19, 2014 at 1:55 | comment | added | JRN | Could you give more detail on how you got this value? | |
| Dec 19, 2014 at 0:59 | comment | added | user64129 | The value is about 4.586079098899, all digits exclude last one should be accurate. | |
| May 7, 2010 at 6:33 | vote | accept | James Propp | ||
| May 6, 2010 at 3:43 | comment | added | James Propp | I think I sowed the seeds for this off-by-one error in my original post, since "self-avoidance time" suggests the smaller number while "how many steps ... before it visits a vertex it's visited before?" suggests the larger number. | |
| May 5, 2010 at 17:36 | comment | added | Yvan Velenik | I've updated my answer below. The answer was indeed off by 1 (stupid mistake). I've also an upper bound... | |
| May 5, 2010 at 16:12 | comment | added | David E Speyer | So, switching my notation to match everyone else's, an obvious upper bound is $5$. | |
| May 5, 2010 at 16:11 | comment | added | David E Speyer | Ah ha! I just tried adding up the numbers for Yvan's link and I get 3.58608. It looks like we are just off by 1, so this is probably a question of whether the length of a walk is the number of vertices visited, or the number of edges traversed | |
| May 5, 2010 at 16:09 | comment | added | JBL | Okay, now I'm also very confused (and have deleted my previous, wrong, comment). | |
| May 5, 2010 at 16:04 | comment | added | David E Speyer | Thanks, but I don't think that's the error. I am using the formula $\sum c_k 4^{-k}$ as in Yvan's post, and claiming that $c_k \leq 4 \cdot 3^{k-1}$. Think about the one dimensional case. The expected number of steps before backtracking is the sum, over $k$, of the probability that you get to take the $k$-th step, namely $1/2^{k-1}$. It is not $\sum k/2^{k-1}$. | |
| May 5, 2010 at 15:57 | comment | added | David E Speyer | I am missing something dumb here. It seems to me the number of self-avoiding walks of length $k$ is $\leq 4 \cdot 3^{k-1}$, since we must never backtrack. But this gives me an upper bound of $1+(3/4) +(3/4)^2 + \cdots = 4$. This is contrary to the numerical value of about 4.59 that Gabriel and Yvan are getting. What's going on? | |
| May 5, 2010 at 15:48 | answer | added | JBL | timeline score: 1 | |
| May 5, 2010 at 15:21 | answer | added | Yvan Velenik | timeline score: 12 | |
| May 5, 2010 at 14:40 | comment | added | Gabriel Benamy | I'm unfamiliar with this subject, but a quick wiki on random walks gave me enough to write a simple program. Assuming that the walk can simply go back on itself (which would cause it to intersect itself), and that, say, {0,0}, {0,1}, {0,0} would constitute 2 steps, then assuming a normal distribution for the number of steps, there is about a 95% chance that the average number of steps is between 4.5652 and 4.59948, using a sample size of 100,000 random walks. Sorry it's not an analytic approach, though; I have a class in a few minutes and I didn't want to miss it working on this neat problem. | |
| May 5, 2010 at 13:24 | history | asked | James Propp | CC BY-SA 2.5 |