  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\times 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.
