Let G be a directed graph of n vertices (indexed 0 , 1, 2, ... , n-1).
Each vertex is connected to the next vertex and the 0 vertex (in directed edge from it to the next / 0 vertex).
(the 0 vertex connects to himself and to the 1 veryex and the n-1 vertex connected only to 0 vertex).
lets say we're going with random steps (with uniform probability) on the graph until we cover all of it.
what's the average length of a path starting at 0 and ending at 0?
(when we get to the n-1 vertex we don't step anymore).
I computed that the probability of a path to get to the n-1 vertex is $\frac{1}{2^{n-1}}$, but I cant compute the average length of a path.
I also only care about its big-O-notation value - asymptotic approximation (if its between $\frac{n}{2}$ to $\frac{n}{3}$ I care about the fact its O(n))
As the walk tries to get from vertex $j$ to vertex $n-1$ without returning to $0$, it has probability $2^{j-n+1}$ to succeed, so vertex $j$ is expected to be visited $2^{n-1-j}$ times. The expected length of the path is the sum of these expected visit counts minus $1$ and thus
$$ \sum_{j=0}^{n-1}2^{n-1-j}-1=\sum_{j=0}^{n-1}2^j-1=2^n-2\;. $$