Introduction

• This project involves self-avoiding random walks (commonly called “SAW”).
• A self-avoiding random walk is not allowed to intersect itself.
• To explain, consider a two-dimensional integer grid
  1. The random walk begins at the origin (0, 0).
  2. At each increment, the walk takes a step horizontally ±1 unit else vertically ±1 unit
  3. Diagonal steps are not allowed: each step is either horizontal else vertical.
  4. Suppose that after n steps, the path of the random walk is given by the set of points {(x0, y0),(x1, y1), . . . ,(xn, yn)}, where (x0, y0) = (0, 0).
  5. At the next step, the random walk goes to the point (xn+1, yn+1), which is one of the four possible points (xn + 1, yn), (xn − 1, yn), (xn, yn + 1) or (xn, yn − 1).
  6. However, it is forbidden for the point (xn+1, yn+1) to equal one of the points (x0, y0), . . . ,(xn, yn).
  7. Once a self-avoiding random walk passes through a point, it cannot pass through the same point again.
• Two or more points in the random walk are not allowed to coincide.
• An example of a self-avoiding random walk is displayed in Fig. 1.
  1. The walk starts at the origin (0, 0)
  2. Twelve steps are shown, labelled 1 through 12.
  3. After step 12, three possible steps labelled 13a, 13b and 13c are shown,
  4. The step labelled 13a is forbidden because the random walk would intersect itself
  5. The steps labelled 13b and 13c are allowed.
     1. Note that if the next step is 13b, then the random walk reaches a dead end, because all possible steps after that will self-intersect the path of the random walk.
     2. It is possible for a self-avoiding random walk to reach a dead end.
  6. There is one additional step after step 12, which is not displayed in Fig. 1.
     1. That is to reverse the direction of step 12 and go from (−1, 1) to (−2, 1).
     2. A “reverse step” is forbidden because it also counts as a self-intersection.
• In this project, we shall only consider self-avoiding random walks on integer grids.
• Every random walk always starts at the origin.
• Figure 1

Result

2D Self Avoiding Random Walk

• The mean (or average) of the end-to-end squared distance is given by the average:

3D Self Avoiding Random Walk

• The mean (or average) of the end-to-end squared distance is given by the average:

4D Self Avoiding Random Walk

• The mean (or average) of the end-to-end squared distance is given by the average: