A random walk on half the number line Consider a symmetric random walk on the number line where steps are size $1$.  If a step from $0$ tries to go to $-1$ you stay at $0$ instead. You start at $0$ and we want to compute the expected time to reach $x>0$.
From numerical experiments it seems to be $x(x+1)$.  How can this be proved?
 A: Let $E_k=$ expected number of steps to reach $x$ starting from $k$.
For $k=1,2, 3, ..., x-1$ we have the following recurrence relation:
$$E_k=\dfrac{1}{2}(E_{k-1}+1)+\dfrac{1}{2}(E_{k+1}+1)$$
(Explanation: From $k$, if the random direction is $-1$ then the number of steps to reach $x$ becomes $E_{k-1}+1$. If the random direction is $+1$ then the expected number of steps to reach $x$ becomes $E_1+1$.)
It is easy to show that $E_k=x(x+1)-k(k+1)$ satisfies the recurrence relation. This must be the correct expression for $E_k$, because there is only one value for $E_k$ for each value of $k$.
$\therefore E_1=x(x+1)-2$
We also have
$$E_0=\frac{1}{2}(E_0+1)+\frac{1}{2}(E_1+1)\implies E_0=E_1+2$$
$\therefore E_0=x(x+1)$
A: Let $\tau_x$ be the hitting time of the level $x>0$. Decompose this time into the separate returns to zero. Formally, $\tau_x = T_R$ where $T_i$ is defined recursively with $T_0 = 0$ and
$T_i = \min\{k> T_i, X_k \in \{0,x \}\}$, and $R = \min\{i, X_{T_i} = x\}$.
What the walk does in each of the intervals $[T_{i-1},T_i]$ is independent of the past, conditional on the knowledge of where you were at time $T_i$ (either $x$ or $0$), and is distributed as a fresh walk started from this point. This is the strong Markov property.
Now write
$$\tau_x = T_R = \sum_{i=1}^R T_i - T_{i-1}\\
= \sum_{i=1}^\infty  \Bbb 1_{R\geq i} (T_i - T_{i-1})\\
= \sum_{i=1}^\infty  \Bbb 1_{X_{T_1}=0}1_{X_{T_2}=0}\ldots 1_{X_{T_{i-1}}=0}(T_i - T_{i-1})\\
$$
The expectation of each of the terms is easy to compute with successive conditioning, that is $$\mathbb E[\Bbb 1_{X_{T_1}=0}1_{X_{T_2}=0}\ldots 1_{X_{T_{i-1}}=0}(T_i - T_{i-1})] \\= \mathbb P(X_{T_1}=0) \mathbb P(X_{T_2}=0 | X_{T_1}=0) \mathbb P(X_{T_{i-1}}=0 | X_{T_{i-2}}=0) \mathbb E[T_i - T_{i-1}|T_{i-1}=0]$$
Now because of the strong Markov property, these are the same as the original walk wich was started at zero.
$$ = \mathbb P(X_{T_1} = 0)^{i-1} \mathbb E[T_1].$$
So by linearity of expectation
$$\mathbb E[\tau_x] = \sum_{i=1}^\infty \mathbb P(X_{T_1} = 0)^{i-1} \mathbb E(T_1) = \mathbb E[T_1] \times \dfrac 1 {1-P(X_{T_1} = 0)} = \dfrac {\mathbb E[T_1]}{P(X_{T_1} = x)}.$$
We have reduced the problem to something much simpler. Now if you think about it, $T_1$ is the same as the first time to hit either $x$ or $-1$ started from $0$ for the simple random walk on $\mathbb Z$, a very classical setting called gambler's ruin. You will readily find formulas in books or on the web both for the expected hitting time of a upper and lower level started from zero, and for the probability that the upper level is reached. Plugging these in will yield the formula you conjectured (good job for that).
