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.

  • $\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 '18 at 16:17

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.