We keep drawing random variables from distribution (normal distribution with mean 0
and variance 1) until the total sum is at least 1. If all the draws are
independent, what is the average number of variables that we draw?
The answer is equal to .
In other words, the average number of steps that we take before the
total sum is at least 1 is infinity.
Let us denote by the average
number of draws from until
the absolute value of the sum of the variables is at
least . Let be the sum of the variables, which is
initially equal to 0. It takes
steps on average until the absolute value of the sum of the variables
() is at least . At this point, if is positive, the process will end,
otherwise the total sum of variables is smaller than or equal to . Notice that since is symmetric, the odds that is negative is exactly .
Now, for the case that ,
we draw new variables from
until the absolute value of the sum of the new variables is at least
. This again takes steps on average. Notice that again
since holds initially,
will never reach a value of at
least before the absolute value
of the sum of the new variables is at least . We assume for simplicity that if the
total sum of the new variables is at least , the process ends (although this may
not be the case in reality) however, we know that with probability 0.5,
the total sum of the new variables is smaller or equal to in which case the new value of would be less than or equal to . Now, we repeat the same process until
the absolute value of the sum of the new variables is at least . This continues until at some point the
sum of the new variables is at least in some step in which case we stop the
process.
Notice that in the first step, we draw variables on average. In the second
step, we draw variables on
average and generally in step we
draw variables on
average. Moreover, the probability that in our process we go to step
is . Thus, by linearity of
expectation, the average number of variables we draw is at least . We show
in the following that
which implies that the expression of the solution is not bounded by any
real number. Thus, the answer to the problem is infinity.
Lemma 1. .
Proof. Notice that (the expected value
of the absolute value of a normal variable with mean 0 and variance 1)
is less that . Thus, on average
it takes at least steps until
the absolute value of the sum of the variables is at least .