2
$\begingroup$

Let $G$ be a graph and $v$ one of its vertices.

Are there any known formulas or fast algorithms for calculating the expected length of a random path in $G$ starting in $v$?

In each step we choose a neighbour of the current vertex uniformly, if it has already been visited we stop the process, otherwise we move to that vertex.

For example, if our graph is a path with $3$ vertices and $v$ is one of the edges, the expected length is $\frac{3+2}{2}$


I am also interested in formulas for the expected length if the initial vertex is chosen uniformly. Thank you kindly.

$\endgroup$
1
  • $\begingroup$ Here's a few simple ideas. In practice a simple random sampling algorithm probably works fine. More theoretically you can probably compute the expected path length for a random graph by relating it to coupon collecting. Then you might be able to connect the expected length of a random graph to the expansion properties of that graph and use this to estimate the expected length, i e by estimating the expansion properties of the graph you were interested in. $\endgroup$
    – ericf
    Mar 28, 2018 at 16:17

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.