Simple sampling and its variants

The trouble with this algorithm is, of course, the exponentially rapid sample attrition for long walks. Clearly, the probability of an A-step walk being self-avoiding is cn/(2cI), which behaves for large A as 

Some improvement can be obtained by modifying the walk-generation process so as to produce only walks without immediate reversals (such walks are called non-reversal random walks (NRRWs) or memory-2 walks). The algorithm is thus  

Uj — a random nearest neighbor of Uj-i, not equal to Ut-i if e u/b,. , Wf-i goto start enddo return u 

For comparison, A is approximately 0.13, 0.07 and 0.03, respectively, for 2,3,4. This is much smaller than in the unmodified scheme, but the exponential attrition is still prohibitive for walks of length more than 80-300 steps. 

The logical next step is to modify the walk-generation process so that walks with loops of length r are automatically absent. Let us start by building the walk out of strides of r steps.That is, let us enumerate in advance all the r-step SAWs—call them (Obviously this takes 

---