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 graphcomposed 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.
Expected length of a self-avoiding random walk
optimization;random walks