Let e_{i} = h_{i1} be the expected number of steps for
a random walk starting at vertex i to reach vertex 1

We need to solve the recurrence equations:

- e
_{1}= 0 - e
_{i}= e_{i-1}/2 + e_{i+1}/2 + 1 for 1 < i < n - e
_{n}= e_{n-1}+ 1

e_{i} = (i-1)e_{2} - i^{2} + 3i -2

Plugging this into the third equation above and solving gives

e_{i} = (i - 1)(2n - 3) - i^{2} + 3i - 2

This is monotonically increasing from 1 to n, and e_{n} = (n - 1)^{2}

**Reference:** This is using techniques similar to those found in

Elementary probability Theory with Stochastic Pocesses

Kai Lai Chung

Springer-Verlag, 1974