Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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. – Henning Makholm Feb 17 '13 at 20:50
up vote 2 down vote accepted

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

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

share|cite|improve this answer
Thank you for this. I assumed the expected amount of steps would be a bit smaller. – ubershmekel Aug 31 '15 at 4:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.