I came across this problem in a math course of mine a while back, and I haven't been able to solve it since. Anyone have any ideas?

Suppose we have a chain of $n$ vertices, such that the first vertex has an edge to the second, the $i$th vertex has an edge to the $(i-1)$th and $(i+1)$th vertices, and the $n$th vertex has an edge to only the $(n-1)$th vertex. If we perform a random walk on the graph, starting at the second vertex, what is $E(h)$, if $h$ is the number of steps it takes to reach the first vertex?

I wrote a program that performs ~100,000 random walks to find a reasonable answer, and from that, I was able to determine that it takes $O(n)$ time, but I have not been able to find any insight into the combinatorial nature of the problem that gives us this result.

How do I prove this result rigorously?

Furthermore, what is the expected hitting time $E(h_i)$ when performing a random walk starting at vertex $i$?

Note: Another result that I know from the textbook is that $E(h_n) = n^2$, but again, I have not yet been able to come up with a proof of this.


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.