Expected length of a random walk on a line
The behavior when $p = 1/2$ and when $p &gt; 1/2$ is rather different. When $p &gt; 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. When $p = 1/2$, the situation is more complicated.

Consider a random walk on the line started at the origin. The number of walks of length $2n$ which never move right of the origin is $\frac{\binom{2n}{n}}{n+1}$ (these are the Catalan numbers), and so the probability that you move right of the origin at the first time after exactly $2n+1$ steps is
$$
q_{2n+1} = \frac{1}{2^{2n+1}} \frac{\binom{2n}{n}}{n+1} = \Theta\left(\frac{1}{n^{3/2}}\right).
$$
Therefore the expected number of steps until you first move right of the origin is
$$
\sum_{n=0}^\infty (2n+1) q_{2n+1} = \sum_{n=0}^\infty \Theta\left(\frac{1}{\sqrt{n}}\right) = \infty.
$$
On the other hand, the number of visits to the origin is
$$
\sum_{n=0}^\infty \frac{\binom{2n}{n}}{2^{2n}} = \sum_{n=0}^\infty \Theta\left(\frac{1}{\sqrt{n}}\right) = \infty,
$$
so you will move right of the origin infinitely many times.

The conclusion is that a random walk started at $i &gt; 0$ will hit the origin almost surely, but the expected time to reach the origin is infinite.

Your case is, however, different, since you "bounce" at $i = n$: when at position $n$, you always move to $n-1$. You can think of the situation in the following way. Although the actual set of positions is $0,\ldots,n$, we imagine reflecting this set along the point $n$, adding $n-1$ new positions $n+1,\ldots,2n$. Here position $n+k$ really plays the role of position $n-k$. We can run the random walk as usual, declaring victory upon reaching either position $0$ or position $2n$.

After $t$ steps, the displacement from the initial position has binomial distribution $\mathrm{Bin}(t,1/2)$, which is close to a normal distribution $N(t/2,t/4)$. Therefore after $t$ steps, we expect to be at a distance of about $\Theta(\sqrt{t})$ from where we started (this can be shown formally by considering the squared displacement and using Chebyshev's inequality, which requires an estimate of the fourth moment of a binomial random variable). In your case, we start at some position $i \in \{1,\ldots,n\}$. After $\Theta(n^2)$ steps, we expect to be about $\Theta(n)$ far from where we started, and so, hit either $0$ or $2n$. Therefore the process should converge in $O(n^2)$ steps.



We can also solve the recurrence directly when $p = 1/2$. Recall that the recurrence is
$$
E[X_i] = 1 + \frac{E[X_{i-1}] + E[X_{i+1}]}{2},
$$
with initial conditions $E[X_0] = E[X_{2n}] = 0$.

Let $N_i = E[X_i] + i^2$. Then
$$
N_i = 1 + \frac{N_{i-1} + N_{i+1} - (i-1)^2 - (i+1)^2}{2} + i^2 = \frac{N_{i-1}+N_{i+1}}{2},
$$
with initial conditions $N_0 = 0$ and $N_{2n} = 4n^2$.

Let $M_i = N_i - 2ni$. Then $M_i$ satisfies the same recurrence as $N_i$, with initial conditions $M_0 = M_{2n} = 0$. It is easy to check that the minimum and maximum of the sequence $M_0,\ldots,M_{2n}$ must be attained at the endpoints (since $\max(M_{i-1},M_{i+1}) \geq M_i$ and $\min(M_{i-1},M_{i+1}) \leq M_i$), and so $M_i \equiv 0$. Therefore $N_i = 2ni$, and so
$$
E[X_i] = i(2n-i) = n^2 - (n-i)^2.
$$