‌

Nest / NestList

Nest

Often instead of mapping a function over a list we want to map a function in a nested fashion, taking the previous result as the argument of our next call. For this, there is Nest . We could, for instance, implement a random-walk function using this.

First the random vector:

 randomVector=
Compile[{ {mag,_Real} },
 mag*Normalize@RandomReal[{-1,1},3]
 ];

Then the random walk starting from a point:

 randomWalk[start_,n_,stepSize_]:=Nest[randomVector[stepSize]+#&,start,n];
randomWalk[{0,0,0},100,.1]

 {-0.6701260860918063`,0.14108631400644098`,-0.18613771198513052`}

Do to this procedurally we would have had to have scoped it then looped:

 randomWalkP[start_,n_,stepSize_]:=
Module[{current=start,i},
 For[i = 1, i<= n , i++,current+= randomVector[stepSize]];
 current
 ];

randomWalkP[{0,0,0},100,.1]

 {-0.014976940150273566`,0.9945437636484472`,-0.08019586484541548`}

And then we can see the efficiency gains of the former:

 randomWalkP[{0,0,0},10^6,.1]//
AbsoluteTiming//First

 2.599178`

randomWalk[{0,0,0},10^6,.1]//
AbsoluteTiming//First

 1.824635`

Small (most of the cost comes from the normalization in randomVector , hence the Compile call) but non-negligible.

NestList

The gains are drastic if we want all of our walk positions. For this we use the corresponding NestList function:

 randomWalk2[start_,n_,stepSize_]:=
NestList[randomVector[stepSize]+#&,start,n];

randomWalk2[{0,0,0},10^6,.1]//AbsoluteTiming//First

 1.892415`

randomWalkP2[start_,n_,stepSize_]:=
Module[{path={start},i},
 For[i = 1, i<= n , i++,AppendTo[path, randomVector[stepSize]+Last@path]];
 path
 ];

randomWalkP2[{0,0,0},10^5,.1]//
AbsoluteTiming//First

 27.372997`

Note that, not only does it take almost 15x as long, we accumulated an order of magnitude fewer points.

Let’s put this to good use, now, seeing where our random walks end up:

 randomWalkP2[{0,0,0},2.5*10^4,.1]//Mean//AbsoluteTiming

 {1.821336`,{7.575784741863281`,-5.394047567758916`,2.3229639385579515`}}

randomWalk2[{0,0,0},25*10^3,.1]//Mean//AbsoluteTiming

 {0.043608`,{-6.015475841270593`,-0.6336148160099607`,-3.303309091893062`}}

Both have traveled a considerable distance and using the vast efficiency gains from the NestList we can actually see if this holds in general or if it’s just a spurious effect:

 Table[randomWalk2[{0,0,0},25*10^3,.1]//Mean//Norm,100]//Mean//AbsoluteTiming

 {4.537624`,8.4477492155034`}

So it does in fact seem that, on average, a random walk will leave its origin. Note that doing that checking the same thing procedurally would have take a number of minutes. We can do it in under five seconds.