Mathematics – Combinatorics
Scientific paper
2011-06-09
Mathematics
Combinatorics
17 pages
Scientific paper
In a 1976 paper published in Science, Knuth presented an algorithm to sample (non-uniform) self-avoiding walks crossing a square of side k. From this sample, he constructed an estimator for the number of such walks. The quality of this estimator is directly related to the (relative) variance of a certain random variable X_k. From his experiments, Knuth suspected that this variance was extremely large, so that the estimator would not be very efficient. A few years ago, Bassetti and Diaconis showed that, for a similar sampler that only generates walks consisting of North and East steps, the relative variance is O(\sqrt k). In this note we go one step further by showing that, for walks consisting of North, South and East steps, the relative variance is of the order of 2^{k(k+1)}/(k+1)^{2k}, and thus much larger than exponential in k. We also obtain partial results for general self-avoiding walks, suggesting that the relative variance could be as large as \mu^{k^2} for some \mu>1. Knuth's algorithm is a basic example of a widely used technique called sequential importance sampling. The present paper, following Bassetti and Diaconis' paper, is one of very few examples where variances of the estimators can be found.
No associations
LandOfFree
On the importance sampling of self-avoiding walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the importance sampling of self-avoiding walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the importance sampling of self-avoiding walks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-580865