Expected number of steps to reach absorbing steps in a random walk.

Question

Suppose a Markov Chain, {$ X_n, n \ge 0$}, so that $P_{i,i+1} = P_{i,i-1} = 1/2$, for $0 < i < K$, and $P_{K, K} = P_{0, 0} = 1$.

How can I proof that the expected number of steps for reach $K$ or $0$, given that $X_0 = i$, is equal to $i(n-i)$?

Answer 1

Hints: let $a_i$ the expected number of steps for reach $K$ or $0$ given $X_0 = i$, then can you prove that $$a_{i} = \frac{a_{i-1} + a_{i+1}}2$$ for $ 0 < i < K$? How about $a_0$? and $a_K$? Finally use induction.