<p>We're given an <em>arbitrary</em> graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists.
Clearly, this random walk can get stuck very quickly.</p>

<p>Now, the questions are 1) How can one compute (or even approximate) the expected walk time?
2) How can one choose the initial node that maximizes the walk time? For example, the lollipop graph
composed of a $3$-cycle over the set $\{1,2,3\}$ with a fourth node $4$ attached to node $1$.
The ratio of the expected walk times corresponding to choosing nodes $4$ and $1$ is $8/5$.</p>

<p>In trees the problem is trivial (average depth of leaves), but I don't see how to generalize that.</p>

<p>A sampling approach may do trick, as the naive bound on each sampled walk would be $n$. However, I suspect that some graph classes might be amenable to more efficient analyses.</p>

CC BY-SA 3.0
2013-04-29T10:43:55.170Z
Of course, a brute-force backtracking approach will do it. Just simulate all possible walks, accumulating their length and probability, then take the weighted average. If you're looking for something more efficient, you should ask for it in your question.
mhelvens
CC BY-SA 3.0
2013-04-29T12:16:02.433Z
Thanks. Well, that would be the obvious quick-and-dirty way to go. You could use the Hoeffding bound, with an upper bound of $n$ on the lengths.

I'm looking for something more efficient though. Something that possibly depends on the properties of the graph (e.g., treewidth, d-clawfreeness etc.). I'll update my question.
JoelO
CC BY-SA 3.0
2013-04-29T12:48:07.453Z
Second thought: Isolate the strongly connected components. With a little bit of thought you should be able to process each one in isolation and compose the results.
mhelvens
CC BY-SA 3.0
2013-04-29T13:52:38.390Z
@mhelvens : Well, looking at the SCCs may not cut it. You need some "cut" property of the graph, and also take into account the starting node (as I mentioned in the example, or in the case of a path -- comparing the middle node to an endpoint).
JoelO
CC BY-SA 3.0
2013-04-30T22:45:04.213Z
Looking at the forest formed by all induced paths in the graph might be a start, with each tree rooted at a particular starting vertex.  The process chooses a child of the current vertex uniformly at random.  One might then be able to prove various useful properties of the forest, based on properties of the class of graphs.  Of course, this is just shifting your question: the forest seems to allow one to compute the quantities of interest, but now one probably has to study the shapes of the trees in excruciating detail.
András Salamon
<optimization><random-walks>
Expected length of a self-avoiding random walk
JoelO
# Expected length of a self-avoiding random walk

(Asked by: username_0 on 2013-04-29)

We're given an *arbitrary* graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists.
Clearly, this random walk can get stuck very quickly.

Now, the questions are 1) How can one compute (or even approximate) the expected walk time?
2) How can one choose the initial node that maximizes the walk time? For example, the lollipop graph
composed of a $3$-cycle over the set $\{1,2,3\}$ with a fourth node $4$ attached to node $1$.
The ratio of the expected walk times corresponding to choosing nodes $4$ and $1$ is $8/5$.

In trees the problem is trivial (average depth of leaves), but I don't see how to generalize that.

A sampling approach may do trick, as the naive bound on each sampled walk would be $n$. However, I suspect that some graph classes might be amenable to more efficient analyses.

**Tags:** optimization, random-walks
> **Comments:**
> **username_1**: Of course, a brute-force backtracking approach will do it. Just simulate all possible walks, accumulating their length and probability, then take the weighted average. If you're looking for something more efficient, you should ask for it in your question.  
> **username_0**: Thanks. Well, that would be the obvious quick-and-dirty way to go. You could use the Hoeffding bound, with an upper bound of $n$ on the lengths.  I'm looking for something more efficient though. Something that possibly depends on the properties of the graph (e.g., treewidth, d-clawfreeness etc.). I'll update my question.  
> **username_1**: Second thought: Isolate the strongly connected components. With a little bit of thought you should be able to process each one in isolation and compose the results.  
> **username_0**: @mhelvens : Well, looking at the SCCs may not cut it. You need some "cut" property of the graph, and also take into account the starting node (as I mentioned in the example, or in the case of a path -- comparing the middle node to an endpoint).  
> **username_2**: Looking at the forest formed by all induced paths in the graph might be a start, with each tree rooted at a particular starting vertex.  The process chooses a child of the current vertex uniformly at random.  One might then be able to prove various useful properties of the forest, based on properties of the class of graphs.  Of course, this is just shifting your question: the forest seems to allow one to compute the quantities of interest, but now one probably has to study the shapes of the trees in excruciating detail.  

---

## 0 answers

