On the importance sampling of self-avoiding walks
From MaRDI portal
Abstract: 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). But how large? For the analogous Rosenbluth algorithm, which samples unconfined self-avoiding walks of length n, the variance of the corresponding estimator is believed to be exponential in n. A few years ago, Bassetti and Diaconis showed that, for a sampler `a la Knuth, that generates walks crossing a k imes k square and consisting of North and East steps, the relative variance is only O(sqrt k). In this note we take one step further and show that, for walks consisting of North, South and East steps, the relative variance jumps to 2^{k(k+1)}/(k+1)^{2k}. This is quasi-exponential in the average length of the walks, which is of order k^2. We also obtain partial results for general self-avoiding walks crossing a square, suggesting that the relative variance could be exponential in k^2 (which is again the average length of these walks). 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 the variance of the estimator can be found.
Recommendations
Cites work
- A faster implementation of the pivot algorithm for self-avoiding walks
- A Monte Carlo study of non-trapped self-avoiding walks
- Analytic combinatorics
- Critical behaviour of self-avoiding walks: that cross a square
- Generating functions for generating trees
- Linear recurrences with constant coefficients: The multivariate case
- Mathematics and computer science: coping with finiteness
- Scaling of the atmosphere of self-avoiding walks
- Self-avoiding walks crossing a square
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- Weakly directed self-avoiding walks
Cited in
(6)- The sample size required in importance sampling
- An optimal algorithm to generate extendable self-avoiding walks in arbitrary dimension
- Taming reluctant random walks in the positive quadrant
- Exact and efficient sampling of conditioned walks
- Robust importance sampling with adaptive winsorization
- Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
This page was built for publication: On the importance sampling of self-avoiding walks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191198)
