0
$\begingroup$

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.

$\endgroup$

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.