Expectation of stopping time on a random walk

Question

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.

Answer 1

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

Answer 2

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.