June 2007
Ponder This Solution:
The answers with a sketch of the proofs follow.
1. exp(x)*(1-x)
Suppose you request numbers until you win or go above 1. Let p(k+1) be the probability you win after receiving k+1 numbers (0 < k < infinity). We claim p(k+1)=(1-x)*(x**k)/k!. Let q(k) be the probability that the sum of k random numbers is less than x. Clearly p(k+1)=(1-x)*q(k) since if the first k numbers sum to less than your chance of winning with the next number is 1-x. Let x1, ... ,xk be k random numbers uniformly and independently distributed between 0 and 1. For i=1,...,k let yi=(x1+...+xi) where the sum is mod 1. Then the yi are also uniformly and independently distributed random numbers between 0 and 1. Furthermore x1+...+xk < x iff all the yi < x and y1<y2< ... <yk. So the probability is x**k/k! as claimed. The result follows as exp(x)=sum(k=0,1,...,infinity) x**k/k!.
2. 1-x*x
Suppose we request numbers x1,x2, ... until the sum exceeds n+x at which point we will either win or lose. Let xk be the value that causes the sum to exceed n+x. Values between 0 and 1 are equally likely but larger values are more likely to cause the sum to exceed n+x. So as n --> infinity the differential probability that xk=t is 2*t*dt. Furthermore as n --> infinity the value (x1+x2+...+xk)-(n+x) will be equally likely to lie anywhere in the interval (0,t). We win when the value is < 1-x. So the probability of winning is Integral(0 to 1)(min(t,1-x)/t * 2*t*dt) = 2*Intgeral(0,1-x)(t*dt) + 2*Integral(1-x,1)((1-x)*dt) = (1-x)**2 + 2*x*(1-x) = (1-x)*(1+x) = 1-x*x as claimed above.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com