8
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jeff Burdges Nov 18 '11 at 14:45
  • $\begingroup$ 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. $\endgroup$ – Timothy Chow Nov 18 '11 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.