# How should one simulate self-avoiding random walks?

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?