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.