So if our sequence is 0.2,0.7,0.4, 0.6 and so on our running totals will be 0.2, 0.9, 1.3, 1.9 and so on.
However we'd stop after the 3rd number as the sum is over 1. So in his case the number of draws would be 3.
The puzzle today is how many numbers we expect to draw. That is if X is the number of draws find E[X].
Hat tip to Simon Spicer for showing me this one (neither he nor I knows where he got it from). Enjoy.
The puzzle today is how many numbers we expect to draw. That is if X is the number of draws find E[X].
Hat tip to Simon Spicer for showing me this one (neither he nor I knows where he got it from). Enjoy.
Let f(x) be the expected number of draws to reach a sum of x. The problem is asking for f(1). Also, let's only concern ourselves with defining f(x) on the interval 0 <= x <= 1.
ReplyDeleteNotice that we can reach a sum of x in one step by drawing any number between x and 1; this happens with probability 1-x. If we do not reach the sum of x (with the remaining probability x), then we're equally likely to be in the subproblem f(y).
So, f(x) = 1, with probability 1-x
= 1 + average value of f(y) for y in (0,x), with probability x.
So the expected value is f(x) = (1-x)(1) + x*(1 + 1/x * integral from 0 to x of [f(y)dy]).
This simplifies to f(x) = 1 + int from 0 to x of [f(y)dy]. Differentiating w.r.t x gives the differential equation f(x) = f'(x), which has solution f(x) = Ce^x, for some C. Plugging back into the integral equation we had for f, we see that C=1 gives the unique solution.
So f(x) = e^x, and the answer to the question is f(1) = e.
Remark: f(0) seems like it should be 0, by the semantics of the problem, but it's actually 1. This is ok, because it's consistent with our relation for f that we had at the beginning, where we say that f(x) is 1 with probability 1-x.
Sorry, "then we're equally likely to be in the subproblem f(y), for values of y between 0 and x."
Delete