Fun with Self-Avoiding Walks - Comments

[klotza]

klotza submitted a new PF Insights post

Fun with Self-Avoiding Walks

Continue reading the Original PF Insights Post.

 

[Hornbein]

klotza submitted a new PF Insights post

Fun with Self-Avoiding Walks

Continue reading the Original PF Insights Post.

"The size of a random walk, being random, has a Gaussian distribution" I would think it would be a Poisson distribution. In this circumstance it would approximate a Gaussian though.

 

[Greg Bernhardt]

Great article! Useful animations!

 

[mfb]

Nice article.

The probability estimate for multiple elements at the same point seems to assume that the positions are completely uncorrelated. That is certainly not true for a random walk, you have strong correlations between neighbor steps. Is there some justification that those correlations don't change the result.

 

[Jimster41]

In the growth of a real polymer can the "walk" take its next step from more than one location on the existing molecule or is it always a literal chain?

Is there evidence of Self Organizing Criticality and Scale-Invariance in a SARW or in real polymers? The picture of Sauron made me wonder.

I am struck (and confused by) the similarity between a SARW and an Abelian Sandpile with a few rule changes - but then I guess there are lots of variations on such games.

 

[klotza]

Hi Jimster41 I just saw your questions now, several months after you asked them.

The self-avoiding walk only grows from the end, it has linear topology in its basic form. Other versions are bottle-brush polymers or comb polymers, hyperbranched polymers, dendritics, etc, which have branchings.

I don't know much about self organizing criticality and scale-invariance, but I do know that regular brownian diffusion can be described by a fractal wiener process. The mathematical literature on the critical behaviour of SAWs is quite extensive but a bit beyond me.

 

[Jimster41]

Hi Jimster41 I just saw your questions now, several months after you asked them.

The self-avoiding walk only grows from the end, it has linear topology in its basic form. Other versions are bottle-brush polymers or comb polymers, hyperbranched polymers, dendritics, etc, which have branchings.

I don't know much about self organizing criticality and scale-invariance, but I do know that regular brownian diffusion can be described by a fractal wiener process. The mathematical literature on the critical behaviour of SAWs is quite extensive but a bit beyond me.

Thank you sir. I know approximately 100% more about pink, white and brown noise, Weirstrauss, Sierpinski, SARW, fractals, self similarity, Lorenz sytems, and the zoo of such things now, having slogged through Manfred Schroeder's book on them (which by the way reads like a walk across the islands of Galapagos).

Your article was one of the things that prompted me to actually try hard to read that... Unfortunately, as you know, 100% of almost nothing is still... next to nothing.

Not that I'm complaining. It's great to feel completely baffled.

 

[herb helbig]

I've written julia code (happy to share) to simulate self avoiding random walks on a square grid, and collected data on the distribution of walk lengths (number of walks of length L). The distribution shows an average walk length of 70.66 steps in good agreement with Hemmer and Hemmer (J. Chem. Phys. 81, 584 (1984); http://scitation.aip.org/content/aip/journal/jcp/81/1/10.1063/1.447349). What surprised me was that adjacent columns of the frequency histogram were staggered in height, the odd columns being larger than the even from the shortest walk (7) at least up to walks of length 50 steps. Over this range, the odd walk numbers are at least 3% higher than the next larger walk number, with channel counts from ~2500 to ~11,000 (so the statistics are sound). For example, the 7-step walk channel had 2755 counts while the 8-step walk channel had 2237 counts. Has anyone noticed this or have an explanation?

 

[mfb]

A walk ends if there is no free spot any more?

Up to symmetries, there is just one 7-step walk (up, left, left, down, down, right, up), and two 8-step walks (same pattern starting one step later). The 8-step walk needs a more precise arrangement of the steps.

 

[herb helbig]

A walk ends if there is no free spot any more?

Up to symmetries, there is just one 7-step walk (up, left, left, down, down, right, up), and two 8-step walks (same pattern starting one step later). The 8-step walk needs a more precise arrangement of the steps.

Yes, thank you for the prompt reply! But isn't it odd that this bias should persist for all walks up to a length of 50 steps or more? And if that sort of argument is valid, how does it apply to, for example, channels 8 and 9? Or, for that matter, channels 48 and 49 where the distribution is past its maximum (which occurs at ~ walks of length 30 steps?

 

[mfb]

I see an effect from parity (like black/white checkerboard fields), but I would not expect it to be so large: a walk after an odd number of steps N can potentially be blocked by (N+1)/2 other elements, while a walk after an even number of steps can be blocked by N/2 other elements.

The probability of a walk ending after 7 steps is 6/3⁷, while the probability of ending after 8 steps is 5/3⁷.

 

[herb helbig]

I see an effect from parity (like black/white checkerboard fields), but I would not expect it to be so large: a walk after an odd number of steps N can potentially be blocked by (N+1)/2 other elements, while a walk after an even number of steps can be blocked by N/2 other elements.

The probability of a walk ending after 7 steps is 6/3⁷, while the probability of ending after 8 steps is 5/3⁷.

mfb - Again many thanks for taking an interest in this problem. The wheels in my 82 year old head don't spin as fast as they once did! Your values for the probabilities, P(7) and P(8), of 7 and 8 step walks agree well with two 1-million walk simulation runs;

P(7)=6/3^7 Run 1 Run 2
0.002743 0.002755 0.002791

P(8)=5/3^7
0.002286 0.002237 0.002258

I think I understand 6/3^7; each step has 3 branches so in 7 steps there are 3^7 possible walks, and for each of the 3 branches there is a left- and a right-handed trapped loop making 6 successes. (Since trapping involves a curling path, is it so that all trapped walks come in left- and right-hand pairs?)

Attempting to use the previous reasoning for the 8 step walk leads me to this (wrong) conclusion: 3 branches for 8 steps gives 3^8 walks, for each branch there is the same, left/right pair of 7-step trapped loops, but with two possible additional first steps for a total of 12 successful 8-step walks. That gives me 12/3^8 = 4/3^7 instead of your 5/3^7. I have spent many waking and even dreaming hours trying to understand why 4 must be 5! I'm sure I'm missing something that should be obvious, but would be grateful for your explanation!

I suppose, more accurately, the 8-step probability should be reduced by multiplying by the probability of not being trapped at 7 steps: 1-P(7) = 0.99726, but it would take a simulation of about 50 million walks to verify that, and much confidence in the random number generator!

I start all walks with the same [1,0] step since symmetry suggests that this should have no effect on the distribution of walk lengths, and it will allow me to see what effect this bias might have on final displacement.

The trend of your (n+1)/2, N/2 parity effect is evident in the data, but apparently an underestimate.

I have a figure summarizing what I have said, but not sure whether it has uploaded.

 

[mfb]

I suppose, more accurately, the 8-step probability should be reduced by multiplying by the probability of not being trapped at 7 steps: 1-P(7) = 0.99726, but it would take a simulation of about 50 million walks to verify that, and much confidence in the random number generator!

The probabilities are absolute. If we would have those values for all N, they would add to 1.

The 8-step path has a tricky case: if you go NNWWSSE (using the directions as you would expect), there are just two instead of three options left for step number 8, one of them ends.

Define North to be the direction of the first step.
- With 1/3 probability the next step is also N, then we have 2/3 probability to go E or W, afterwards we have to choose the right direction out of 3 four times in a row, and finally a 1/2 chance to get trapped. Total: 1/3⁶ = 3/3⁷
- With a 2/3 probability the next step is W or E, then the next 6 steps have to pick the right direction out of 3, for a total contribution of 2/3⁷.
Sum: 5/3⁷

The 7-step walk has 1 case, the 8-step walk has 2 cases, the 9-step walk has 6 cases, and the 10-step walk has at least 15 cases. Manual analysis becomes messy quickly.

The trend of your (n+1)/2, N/2 parity effect is evident in the data, but apparently an underestimate.

I have a figure summarizing what I have said, but not sure whether it has uploaded.

That (n+1)/2 vs n/2 pattern should have an odd/even pattern.

 

[herb helbig]

p { margin-bottom: 0.1in; line-height: 120%; }

mfb -

Thank you for explaining how to count the probabilities for each path of a random walk! And for soothing my pride with the word “tricky”.


I have found six 9-step trapped walk paths that end next to the starting square. Together with their mirror images that makes twelve. I also found four 9-step paths that end a knight’s move from the starting square and one that ends three steps from the starting square in the direction of the first step. With their mirror images that brings the total number of 9-step paths to 22. I have worked out the probabilities for the 9-step walks and they check nicely with my simulation.

That led me to try the 10-step case where I found 25 paths with their mirror images to make 50 total. Again, the calculated and simulated results agree; see attached graph.
https://physicsforums-bernhardtmediall.netdna-ssl.com/data/attachments/90/90305-8f8dc085dc1cb941a4f653baea3f44e9.jpg

I found at least 190 different 11-step trapped walk paths (including symmetric ones) in a sample of 10^6 walks. The samples of 11-step paths ranged in size from 93 down to 10.

I have a copy of “The Self-Avoiding Walk” by Madras and Slade on order in hopes it may provide further insight into this system.

 

[mfb]

If we define the first step to be North, we have 10 steps left for the 11-step walk, removing the mirror symmetry each path has a probability of at least 2/3^10 or 1 in 30,000. With an expected occurrence of 30 or more in a million samples, it is extremely unlikely that you missed any pattern. It should be possible to automatically analyze those patterns in terms of the number of available spaces in each move, which leads to the probability of this path.

 

[mfb]

With a back-tracking algorithm, it should be possible to list all cases (less than 30,000) and their probabilities. The less than 1 million cases for 14 steps should still work, afterwards it might need some computing time. n steps in a self-trapping walk need at most n-5 empty space in every direction from the starting point, but grid size should not be a limit anyway.