Expected number of steps for reaching $K$ in a random walk

Solution 1:

Let's study the expected time it takes for the symmetric random walk to reach $+1$, assuming it begins at $0$. Let $S$ denote the number of steps we take until we reach $+1$ that is $S_1 = \min\{n > 0; X_n = +1\}$ where $X_n$ is your symmetric random walk. Note that $S_1$ is an odd number.

$$P(S_1 = 1) = \frac{1}{2}\\ P(S_1 = 3) = \frac{1}{2^3} \\ P(S_1 = 5) = 2 \frac{1}{2^5}\\ P(S_1 = 2n+1) = C_n \frac{1}{2^{2n+1}}$$

where $C_n$ is the number of non positive paths of length $2n$ begin at $0$ and end at $0$, this is given by $C_n = \frac{1}{n+1} {2n\choose n}$ see https://en.wikipedia.org/wiki/Catalan_number

Now we calculate $$E[S_1] = \sum_{k=0}^\infty (2k + 1) C_k \frac{1}{2^{2k+1}}$$

Now assymptotically, $$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$

therefore $$ C_k \frac{1}{2^{2k+1}} \sim \frac{1}{2 k^{3/2}\sqrt{\pi}} $$

and therefore

$$ (2k + 1) C_k \frac{1}{2^{2k+1}}\sim \frac{2k+1}{2 k^{3/2}\sqrt{\pi}} > \frac{1}{k}$$

therefore the sum diverges and $E[S_1] = \infty$. Now for $S_{10} = \min\{n > 0, X_n = 10\}$ we have $S_{10} \geq S_1$ therefore $$E[S_{10}]\geq E[S_1] = \infty$$

Solution 2:

Let $x$ be the expected number of steps to go from $0$ to $1$. Then, half the time you'll get there in one step, and the other half of the time you'll take one step and then need to cover twice the distance (because now you need to go from $-1$ to $1$). Therefore

$$ x = \frac{1}{2}(1) + \frac{1}{2}(1 + 2x) $$

which simplifies to

$$ x = x + 1 $$

which means that

$$ x = \infty $$

So if going from $0$ to $1$ in expectancy takes infinity steps, then going from $0$ to any other number also takes infinity steps.