Self-Avoiding Walks

A.P. 1601
Columbia University

With help from Computer Simulations with Mathematica by R.Gaylord and P.Wellin (Springer-Verlag,1995)

Introduction

A random walk consists of random steps without any regard to past history. Each step is independent. The behavior of a large number of particles undergoing random walk exhibits diffusion.

The self-avoiding walk (SAW) is fundamentally different. As we trace random steps, our algorithm checks to make certain the path never contacts itself. To implement this algorithm, we need a record of the entire path in order to make decisions about the direction of the next step. As the path gets longer and longer, the SAW requires more computation.

Self-avoiding walks are often used to represent simple models of long polymer chains. In two-dimensions, a SAW can represent the precipitation of a polymer onto a surface. This notebook presents the "pivot" technique for generating different self-avoiding walks of fixed length.

The behavior of the SAW is much different than the random walk (which could be easily predicted with ⟨r⟩ ~ (Sqrt[n]).

The Pivot Algorithm

The "pivot algorithm" is considered to be a very efficient algorithm for generating a large set of "self-avoiding" paths. It is based on selecting a random position on the path and the applying a random rotation or reflection on that part of the path beyond the selected position.

We will look at two-dimensional self-avoiding walks, and we need consider only three rotations: 
	1) rotate by 90 Degrees
	2) rotate by 180 Degrees
	3) rotate by 270 Degrees

We will use the method introduced by R.Gaylord and P.Wellin. A walk begins at {0, 0}, and the initial unit step is along the x-direction. We write:

initial = {{1,0}};

For the three rotations, we define:

rot90 = {{0,1}, {-1,0}};
rot180 = {{-1,0}, {0,-1}};
rot270 = {{0,-1}, {1,0}};

Then, we are able to use Mathematica's built-in matrix multiplication to cause the direction of the walker to be rotated:

{initial.rot90, initial.rot180, initial.rot270}

Example

Let's examine an example pivot.

chain={{0,0},{0,1},{1,1},{1,2},{0,2}};
Show[Graphics[{Line[chain],RGBColor[1,0,0],PointSize[0.03`],Point/@chain}],AspectRatio->Automatic]

Select the pivot…

iPivot = 2;
pivot = chain[[iPivot]]

Rotate about pivot point…

chainRot90 = Table[If[i > iPivot, chain[[iPivot]] + (chain[[i]] - chain[[iPivot]]).rot90, chain[[i]]], {i, 1, Length[chain]}]

chainRot180 = Table[If[i ≥ iPivot, chain[[iPivot]] + (chain[[i]] - chain[[iPivot]]).rot180, chain[[i]]], {i, 1, Length[chain]}];
chainRot270 = Table[If[i ≥ iPivot, chain[[iPivot]] + (chain[[i]] - chain[[iPivot]]).rot270, chain[[i]]], {i, 1, Length[chain]}];

Show[GraphicsRow[(Show[Graphics[{Line[#1],RGBColor[1,0,0],PointSize[0.08`],Point[pivot]}],DisplayFunction->Identity,AspectRatio->Automatic]&)/@{chain,chainRot90,chainRot180,chainRot270},DisplayFunction->$DisplayFunction]]

Twist

The twist[...] command implements the "pivot" algorithm that generates new SAWs.

twist[chain_List]:=Module[{n,iPivot,fixpart,movepart,rotchoice,newpart,newchain,rot},rot={{{0,1},{-1,0}},{{-1,0},{0,-1}},{{0,-1},{1,0}}};n=Length[chain]-1;iPivot=RandomInteger[{1,n-1}];fixpart=Take[chain,iPivot];movepart=Take[chain,iPivot-(n+1)];rotchoice=rot[[RandomInteger[{1,3}]]];newpart=(chain[[iPivot]]+(#1-chain[[iPivot]]).rotchoice&)/@movepart;If[newpart⋂fixpart=={},newchain=Join[fixpart,newpart],chain]]

From 6-RandomWalks.nb…

showWalk2D[pts_List,opts___] := Show[Graphics[Line[pts],opts,AspectRatio-> Automatic]]

Example SAWs

nSteps=1000;chain0=Table[{i,0},{i,0,nSteps}];
chain100=Nest[twist,chain0,100];
chain500=Nest[twist,chain100,400];
chain1000=Nest[twist,chain500,500];
Show[GraphicsRow[{showWalk2D[chain100,DisplayFunction->Identity],showWalk2D[chain500,DisplayFunction->Identity],showWalk2D[chain1000,DisplayFunction->Identity]}],DisplayFunction->$DisplayFunction]

First /@ {chain0, chain100, chain500, chain1000}

Last /@ {chain0, chain100, chain500, chain1000}

Radius at end of walk…

N[Sqrt[#1^2 + #2^2]]& @@@ %

Statistics

We can compute the average radius of many, many "self-avoiding walkers" and estimate the scaling of ⟨r⟩ as a function of the number of steps. (Recall, for a completely random walk, ⟨r⟩ ~ (Sqrt[n]).)

Length[chain500]-1

walkList = NestList[twist, chain500, 1000];

(Remember: there may be duplicate paths in this set of walkers! How does this effect a statistical study of SAWs?)

Dimensions[walkList]

Dimensions[DeleteDuplicates[walkList]]

walkList = DeleteDuplicates[walkList];

rList = N[Sqrt[#1^2 + #2^2]]& @@@ (Last /@ walkList); (* <r> *)

ListPlot[rList, AxesLabel -> {"Walker","<r>"}]

xyList = {#1,#2}& @@@ (Last /@ walkList); (* {x,y} *)

ListPlot[xyList, AxesLabel -> {"x","y"}];
Mean[xyList]//N
ListPlot[{%},PlotStyle -> {Red,PointSize[0.02]}];
Show[%%%,%, PlotLabel -> "Independent SAW"]

Print["Unbiased Random Walker <r> = ",Sqrt[Length[chain500]-1] // N];
Print["Self-Avoiding Walker <r> = ",Mean[rList]];
Print["Standard Deviation of SAW δr = ±", StandardDeviation[rList]];

Clearly, a self-avoiding walk moves radially much faster than a completely random walk.

Summary

We have presented the "Pivot Algorithm" for the computation of a large set of self-avoiding walks of a given size. We have seen that the length traveled during a self-avoiding walk is much longer than the average distance traveled in a random walk.