11
$\begingroup$

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

$\endgroup$
2
  • 6
    $\begingroup$ Answer: +Infinity. $\endgroup$
    – Did
    Commented Feb 17, 2013 at 20:26
  • 3
    $\begingroup$ But even though it takes infinite time on average, it still happens sooner or later with probability 1. $\endgroup$ Commented Feb 17, 2013 at 20:50

2 Answers 2

9
$\begingroup$

Let's look at 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 asymptotically, $$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$$

$\endgroup$
2
  • $\begingroup$ Thank you for this. I assumed the expected amount of steps would be a bit smaller. $\endgroup$ Commented Aug 31, 2015 at 4:45
  • 1
    $\begingroup$ 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? $\endgroup$
    – user251382
    Commented May 22, 2019 at 22:22
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I think x = x + 1 implies that either you made a miscalculation, or that no x exists which satisfies your assumptions. Not that anything goes to infinity. Also, your expected value math seems wrong to me. It's not x=½(1)+½(1+2x) rather I would calculate E(S2) = E(S1) + E(S1) and E(S1) = ½ + E(S2) then you arrive at a similar conclusion. But I'm not sure if this expected value arithmetic is valid. $\endgroup$ Commented Jun 13, 2021 at 23:53
  • $\begingroup$ That's right, since no real number $x$ satisfies the equation, that means that $x=\infty$. You are also right to say that $\mathbf{E}[S_2]=2\mathbf{E}[S_1]$, but to calculate $\mathbf{E}[S_1]$, you forget that it takes one step to get to $S_2$ from $S_1$. So rewriting it all in your notation, we get $\mathbf{E}[S_1] = \frac{1}{2}(1+\mathbf{E}[S_0])+\frac{1}{2}(1+\mathbf{E}[S_2])$. Now replace $\mathbf{E}[S_0]$ with $0$ and $\mathbf{E}[S_2]$ with $2\mathbf{E}[S_1]$. And about if this arithmetic is valid, I may be skipping some steps to make my answer 100% rigorous, but it is a valid answer. $\endgroup$
    – timidpueo
    Commented Jun 15, 2021 at 14:40
  • $\begingroup$ Gotcha. I now understand why you added one, because it's an extra turn. I still think "infinity steps" is not the same as "no valid real number of steps". What you constructed is a "proof by contradiction", not a calculation of the expected amount of steps. For example if I just state x = x + 1 by itself, that's just invalid, it doesn't mean anything about x. $\endgroup$ Commented Jun 15, 2021 at 19:09
  • $\begingroup$ I mean, sure, maybe... I feel like you're just arguing semantics... it doesn't really matter what you call it, in this context my reasoning is a perfectly valid way to arrive at the answer, which is the expected number of steps is infinity. $\endgroup$
    – timidpueo
    Commented Jun 18, 2021 at 15:36
  • 6
    $\begingroup$ @ubershmekel I think this is an elegant proof that unfortunately lacks a few important justifications. The first is that any nonnegative random variable (e.g. $X$ equals the number of steps to reach $k$) has an unambiguous expected value—either finite and positive or infinite (see here) due to monotone convergence. The second is that the proof should start “Assume $E[X]=x$ is finite…”, so that $x=x+1$ is a contradiction, allowing us to conclude $x=\infty$. So the proof is valid with the correct justifications. $\endgroup$
    – Jacob
    Commented Aug 11, 2022 at 20:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .