11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mhelvens Apr 29 '13 at 10:43
  • $\begingroup$ 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. $\endgroup$ – JoelO Apr 29 '13 at 12:16
  • $\begingroup$ 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. $\endgroup$ – mhelvens Apr 29 '13 at 12:48
  • $\begingroup$ @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). $\endgroup$ – JoelO Apr 29 '13 at 13:52
  • $\begingroup$ 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. $\endgroup$ – András Salamon Apr 30 '13 at 22:45

Your Answer

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

Browse other questions tagged or ask your own question.