Expectation of stopping time on a random walk

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.

• @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. – 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.

• Thanks for the pointer, I just refined the expression accordingly. What about the possibility of $\mathbb{E}[\tau_{1000}]=\infty$? – user2348674 May 4 '16 at 17:30
• @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. – Eric Towers May 5 '16 at 1:44