[home]     [professional]     [personal]     [resume] Project: "Generating constrained Self-Avoiding Random Walks uniformly at random" Brief technical write-up and online demonstration:     [SAWs project page] Abstract: A self-avoiding walk, or SAW, is a random walk which never crosses its own path. This paper describes an algorithm that allows us to sample uniformly at random from the set of 2-dimensional self-avoiding walks with a fixed endpoint. The motivation for this algorithm was to empirically determine the distribution of different subsequences of directional steps in such paths, and later to make generalizations about these distributions in the limit. For example, we were interested in studying the distribution of the number of ?left,up? subsequences that appear in a typical self-avoiding path with the endpoint fixed at 20% of the path length to the right and 30% of the path length up, as the path length goes to infinity. Our solution uses an algorithm similar to Metropolis-Hastings to generate a sequence of paths which are allowed to cross themselves with small probability, then samples a single self-avoiding path after a sufficient burn-in period.