How should one simulate self-avoiding random walks?

Question

There is a trivial method for simulating a random walk through a graph by exponentiating a stochastic adjacency matrix, but the problem becomes harder if you ask that the random walk be self-avoiding. In other words, the process must traverse the graph using paths, like an infection or something.

If the edge probabilities are large, there is a simple Monte Carlo algorithm : In each trial, you simply delete each edge $e$ with probability $1-p_e$, compute the new graph's connected components, and increment a counting matrix by matrices of 1s for each contacted component. You divide by the number of trials at the end.

Does anyone know any algorithm for doing this computation when the probabilities are quite small?

If the graph isn't too highly connected, you can find some minimum cut sets, and do inclusion-exclusion counting on them, but such an approach is doubly exponential in the size of the cut sets. There are various optimizations for specific cases of high connectivity too, like treating all the clique subgraphs separately via the obvious computation. Any more general ideas?

Answer 1

I'm not sure if I'm interpreting your question correctly, but it sounds to me that you're asking not about simulating self-avoiding random walks, but about enumerating self-avoiding random walks. I say this because you talk about exponentiating an adjacency matrix, which will give you a (weighted) enumeration of random walks.

I'm not sure if there is much literature on enumerating self-avoiding walks in general graphs; I believe that most attention has been focused on self-avoiding walks in lattices in Euclidean space, and that's what my comments below are based on. I suspect that many of the ideas will carry over to general graphs.

The classic tool for reducing the labor involved in exactly enumerating self-avoiding walks is the lace expansion. You should be able to locate the relevant literature easily with that keyword. For highly connected graphs, though, my guess is that the lace-expansion idea won't help too much (but then maybe nothing will help much in that case).

If you're satisfied with approximate enumeration then there are a few options. See EJJ van Rensburg's 2009 paper on "Approximate enumeration of self-avoiding walks" for a survey. See also "Self-testing algorithms for self-avoiding walks" by Randall and Sinclair (2000).