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

Assuming steps are $+1/-1$ with a $50/50$ probability. What is the expected step count for reaching $10, 100$ or $K$?

• Answer: +Infinity. – Did Feb 17 '13 at 20:26
• But even though it takes infinite time on average, it still happens sooner or later with probability 1. – hmakholm left over Monica Feb 17 '13 at 20:50

## 1 Answer

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$$

• Thank you for this. I assumed the expected amount of steps would be a bit smaller. – ubershmekel Aug 31 '15 at 4:45
• Let's say we were trying to figure out P(S2=2) , P(S2 = 4), P(S2 = 6), etc., how could we modify this answer to get there? – Blake Steines May 22 '19 at 22:22