A self-avoiding random walk (SAW) is a special random walk along an m-dimensional lattice such that no vertex (or site) is visited more than once, Hayes (1998). In this way the trajectory never intersects itself.

Self-avoiding random walks arise in modeling physical processes like the Markov Chain Monte Carlo 449 folding of polymer molecules. Such walks are difficult to model using traditional analytical methods, so they are best studied by simulation.

In this problem we simulate a self-avoiding walk of length N on the lattice using the Metropolis-Hastings algorithm. Specifically, consider a two-dimensional square lattice with unit spacing between sites. Starting at site 1, which is the origin, we choose site 2 at random from its four neighbors. Then for each site i, i = 2,...,N − 1, generate the next site i+1 from the three neighbors of i after excluding i−1. If a site is revisited at any stage of the process, the walk is abandoned and restarted.

a. Run the experiment 500 times. What is the expected length of a walk?

b. Consider a refinement of the process, which is that for each site i, i = 2,...,N − 1, generate the next site i + 1 from the neighbors of i that have not been visited before. Continue until a walk of length N is obtained or the process is trapped. If we run the experiment 100 times, how many full-length SAWs (i.e., SAWs of length N) can you get for N = 20 and N = 50?