<p>I'm not sure if I'm interpreting your question correctly, but it sounds to me that you're asking not about <i>simulating</i> self-avoiding random walks, but about <i>enumerating</i> 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.</p>

<p>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.</p>

<p>The classic tool for reducing the labor involved in <i>exactly</i> 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).</p>

<p>If you're satisfied with <i>approximate</i> 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).</p>

CC BY-SA 3.0
2011-11-18T14:45:48.813Z
Interesting, thanks!  I'm talking about probability, not enumeration.  I have apparently implied the edge probabilities mentioned were identical.  I'll correct that to stochastic adjacency matrix.
Jeff Burdges
CC BY-SA 3.0
2011-11-18T18:51:14.733Z
No, it was clear that you had edge probabilities; that's why I put the word "weighted" in parentheses in my answer.  Calculating probabilities is equivalent to weighted enumeration and most of the ideas for simple enumeration carry over straightforwardly to weighted enumeration.
Timothy Chow
CC BY-SA 3.0
2011-11-16T19:13:56.777Z
2011-11-16T19:13:56.777Z
Timothy Chow
<p>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.</p>

<p>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.</p>

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

<p>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?</p>

CC BY-SA 3.0
2011-11-11T18:04:12.683Z
not exactly what you are looking for, but a good start is [loop-erased random walks](http://en.wikipedia.org/wiki/Loop-erased_random_walk)
Artem Kaznatcheev
<ds.algorithms><graph-algorithms><randomized-algorithms><random-walks>
How should one simulate self-avoiding random walks?
Jeff Burdges
# How should one simulate self-avoiding random walks?

(Asked by: username_0 on 2011-11-11)

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?

**Tags:** ds.algorithms, graph-algorithms, randomized-algorithms, random-walks

> **Comments:**
> **username_1**: not exactly what you are looking for, but a good start is [loop-erased random walks](http://en.wikipedia.org/wiki/Loop-erased_random_walk)  

---

## 1 answers

### Answer by username_2 on 2011-11-16. Score: 7

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).

> **Comments:**
> **username_0**: Interesting, thanks!  I'm talking about probability, not enumeration.  I have apparently implied the edge probabilities mentioned were identical.  I'll correct that to stochastic adjacency matrix.  
> **username_2**: No, it was clear that you had edge probabilities; that's why I put the word "weighted" in parentheses in my answer.  Calculating probabilities is equivalent to weighted enumeration and most of the ideas for simple enumeration carry over straightforwardly to weighted enumeration.  

---

