tag:blogger.com,1999:blog-805662863526468887.post3013705450054461381..comments2023-12-20T00:58:04.067-08:00Comments on Fails to Accept: A puzzle about uniform random variblesAnonymoushttp://www.blogger.com/profile/10716393385703376978noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-805662863526468887.post-66285513832890333102013-12-20T20:35:30.512-08:002013-12-20T20:35:30.512-08:00Sorry, "then we're equally likely to be i...Sorry, "then we're equally likely to be in the subproblem f(y), for values of y between 0 and x."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-805662863526468887.post-59429220308042902252013-12-20T20:33:49.936-08:002013-12-20T20:33:49.936-08:00Let f(x) be the expected number of draws to reach ...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.<br /><br />Notice 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).<br /><br />So, f(x) = 1, with probability 1-x<br /> = 1 + average value of f(y) for y in (0,x), with probability x.<br /><br />So the expected value is f(x) = (1-x)(1) + x*(1 + 1/x * integral from 0 to x of [f(y)dy]).<br /><br />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. <br /><br />So f(x) = e^x, and the answer to the question is f(1) = e.<br /><br />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.Anonymousnoreply@blogger.com