Self-avoiding walk


Polymers are molecules with long strings of repeated units. When placed in a good solvent, the polymer can expand. One model of a polymer is a self-avoiding walk (SAW). In this model the walker steps at random, but cannot return to a site that has already been visited.


One approach to simulating SAWs is to generate a random number at each step and choose one of the maximum of three possible steps. However, there soon would be no allowable steps as the walker finds itself in a cul-de-sac of visited sites. There are a number of enrichment schemes that have been developed to improve the statistics. We will use the following algorithm which is an improvement of the Rosenbluth and Rosenbluth method due to Prelberg and Krawczyk. We consider walks on a square lattice.

  1. Begin with a collection of n walkers labeled by the index i. Assign a weight wi = 1 to each walker. Place each walker at the origin. Maintain a list of visited sites for each walker.
  2. At each step, N, determine for each walker how many available sites, m, there are for the next step. Move to one of these sites with equal probability. Update the weight as

    wi(N) = wi(N-1)(m/3).

    Update the arrays corresponding to the visited sites.
  3. Compute the average wave = <wi(N)> and the ratio r = wi/wave for each walker. If r > 1, then c = min((int)r,m), and make c copies of the walker each with weight wi/c. If r < 1, then remove the walker with probability 1 - r. Repeat for all the walkers.
  4. Compute averages such as <r2(N)> = <wi(N)(xi2 + yi2)>.
  5. Go to step 2.

In the program output the number of steps is equal to the time t. The input parameters are the number of initial walkers n and the number of steps N.


  1. Run the program with the default input parameters. Discuss the values for the mean positions of x and y. Use the Data Table in the Views menu and copy the table of data for ln <x2(t)>, ln <y2(t)>, and ln <r2(t)> versus ln t. Plot these data and estimate the exponent ν assuming that <r2(t)> = Ct. Use only the data that appears to be on a straight line. For large times you might not have enough walkers to obtain reliable data. What value of ν do you expect for a regular random walker? Explain why the value of ν for a self-avoiding walk is different.
  2. Based on your results what can you conclude about the mean displacement in the x and y directions? To make sure your answer is meaningful, do at least three independent trials. Discuss the meaning of your result. Is there a statistically significant difference between the results in the x and y directions?
  3. Increase the number of initial walkers to 1000, and repeat your analysis. Is there any significant differences. Repeat your simulations a few times to see how much your results vary with each trial.
  4. Increase the number of steps to 2048. Do your results improve significantly? Note that the program only takes data in increments of ln t. What does this increment mean about the ability to improve results by going to longer times?

Java Classes

Updated 27 February 2007.