Assume $X_1 , X_2 , \cdots$ are i.i.d. with distribution Bernouli$(\frac{1}{2})$, i.e., $P(X_i = 0)=P(X_i=1)=\frac{1}{2}$. Denote $S_0 := 0$, $S_n := \sum\limits_{i=1}^n X_i$, and $\tau_{1000} := inf\{ n \ge 1 : S_n = 1000 \}$. I need to find $\mathbb{E}[\tau_{1000}]$.

Here is the way I tried to solve this:

$\mathbb{E}[\tau_{1000}] = \sum\limits_{k\ge 1000} k \; {k-1 \choose 999} \; (\frac{1}{2})^{999} \; (\frac{1}{2})^{(k-1)-999}$.

I am not sure whether I need to consider the possibility of $\mathbb{E}[\tau_{1000}] = \infty$ and whether my approach is sound.

  • $\begingroup$ @JohnDawkins : This is false. $\Bbb{E}[\tau_1] = 2$. It's $\sum_{j=1}^\infty \frac{j}{2^j}$, i.e., the probability-times-length that the sequence of $X_j$ is $(1)$ ($\frac{1}{2} \cdot 1$), or $(0,1)$ ($\frac{1}{4} \cdot 2$, or $(0,0,1)$ ($\frac{1}{8} \cdot 3$), et c. $\endgroup$ – Eric Towers May 5 '16 at 1:41

Think about this: $\tau_1=G_1$, where $G_1$ is Geometric with parameter $\frac 12$. Continue inductively:

$$\tau_{n+1} = \tau_n + G_{n+1},$$

where $G_{n+1}$ is Geometric with parameter $\frac 12$, independent of $\tau_n$.

Therefore for each $n\ge 1$, $\tau_n$ is the sum of $n$ independent Geometric with parameter $\frac 12$. In particular, since $E G_1=2$, we have

$$E \tau_n = n E G_1 =2n.$$


It looks like you're overcounting... The sequence $(1, 1, \dots \text{ <<996 more "1"s>> } \dots, 1, 1, 0)$ is included in your $k=1$ count, even though that walk stopped when $k=0$. You actually require that the last $X_i$ is $1$, so you only need to scatter $999$ $1$s in the preceding sequence.

  • $\begingroup$ Thanks for the pointer, I just refined the expression accordingly. What about the possibility of $\mathbb{E}[\tau_{1000}]=\infty$? $\endgroup$ – user2348674 May 4 '16 at 17:30
  • $\begingroup$ @user2348674 : No chance of infinite expectation. This is a diffusion with drift. The drift is $\frac{1}{2}$ unit per step and the diffusion step size is $\frac{1}{2}$, so the un-stopped fraction will decrease more and more rapidly until time step $1000 / (1/2) = 2000$ then decrease like $\mathrm{e}^{-t^2}$ subsequently. The exponential distribution has a mean, so this distribution ($\mathrm{e}^{-t^2}$) has one too. $\endgroup$ – Eric Towers May 5 '16 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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