Ponder This Challenge - June 2007 - Sum of random (0,1) game

Ponder This Challenge:

You are playing a game in which you can ask for numbers. Each such number is a random value uniformly (and independently) distributed between 0 and 1. After you receive each number you can decide whether to request an additional number or to stop. When you stop your score is the sum of all the numbers you have received. Let 0<x<1. We ask two questions.

1. Suppose you are trying to achieve a score between x and 1. What are your chances of success?
2. Suppose you are trying to achieve a score between n+x and n+1. What are your chances of success in the limit as n --> infinity?

In both cases assume you are following the obvious best strategy. The answers are simple functions of x. Both questions must be answered correctly for credit.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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

Solvers

• Henry Bottomly (06.01.2007 @11:24:32 PM EDT)
• Michael Brand (06.02.2007 @06:18:49 AM EDT)
• Roberto Tauraso (06.02.2007 @10:09:37 AM EDT)
• Frank Yang (06.02.2007 @12:28:16 PM EDT)
• John T. Robinson (06.02.2007 @03:20:44 PM EDT)
• V Balakrishnan (06.02.2007 @09:49:02 PM EDT)
• Gary Gerken (06.02.2007 @11:53:12 PM EDT)
• Christian Blatter (06.03.2007 @09:20:09 AM EDT)
• Celia Anteneodo (06.03.2007 @07:59:04 PM EDT)
• Renato Fonseca (06.03.2007 @10:13:16 PM EDT)
• Ashish Srivastava (06.03.2007 @11:22:41 PM EDT)
• James Dow Allen (06.04.2007 @02:14:25 AM EDT)
• Andreas Eisele (06.04.2007 @05:44:34 AM EDT)
• Eugene Vasilchenko (06.04.2007 @01:16:35 PM EDT)
• Dan Dima (06.04.2007 @04:14:11 PM EDT)
• Arthur Breitman (06.04.2007 @07:46:19 PM EDT)
• Ed Sheppard (06.04.2007 @10:22:43 PM EDT)
• Zhou Guang (06.04.2007 @10:48:17 PM EDT)
• Heiko Selber (06.05.2007 @11:13:58 AM EDT)
• John Tromp (06.05.2007 @12:13:33 PM EDT)
• Luke Pebody (06.05.2007 @04:19:19 PM EDT)
• David Friedman (06.07.2007 @02:25:28 PM EDT)
• Ashish Mishra (06.06.2007 @03:27:33 PM EDT)
• Alan Murray (06.06.2007 @09:46:54 PM EDT)
• Murray Garth (06.07.2007 @06:46:57 AM EDT)
• Mark Thornquist (06.07.2007 @06:13:52 PM EDT)
• Wei Zhou (06.07.2007 @07:31:27 PM EDT)
• Jiri Navratil (06.08.2007 @03:26:23 AM EDT)
• Ashutosh Mehra (06.09.2007 @03:33:27 AM EDT)
• Bart De Vylder (06.11.2007 @10:14:45 AM EDT)
• Nancy Schechner (06.11.2007 @03:27:35 PM EDT)
• suthambhara (06.13.2007 @12:16:50 AM EDT)
• Rick Kaye (06.13.2007 @02:46:14 PM EDT)
• Joseph C. Bonneau (06.14.2007 @11:49:18 AM EDT)
• Gale W. Greenlee (06.14.2007 @12:16:22 PM EDT)
• Erik Hostens (06.15.2007 @04:34:33 AM EDT)
• John Fletcher (06.16.2007 @06:58:40 PM EDT)
• David McQuillan (06.17.2007 @05:45:38 AM EDT)
• William C. Hasenplaugh (06.17.2007 @06:25:16 PM EDT)
• Dion Harmon (06.18.2007 @03:10:53 PM EDT)
• Ji Feng (06.18.2007 @04:01:07 PM EDT)
• Phil Muhm (06.19.2007 @09:16:12 AM EDT)
• Ariel Flat (06.23.2007 @11:16:26 AM EDT)
• Chris Shannon (06.26.2007 @01:18:21 AM EDT)
• Chris Danielian (06.27.2007 @02:39:45 PM EDT)
• Maxim Smith (06.27.2007 @03:22:10 PM EDT)
• Majid Khabbazian (06.29.2007 @12:55:38 AM EDT)
• Andrea Andenna (06.29.2007 @07:08:28 PM EDT)
• Dharmadeep Muppalla (06.29.2007 @11:53:25 PM EDT)
• Ilya Khivrich (06.30.2007 @12:27:54 PM EDT)
• Arun Sivaramakrishnan (06.30.2007 @01:15:37 PM EDT)
• Adriano Batista (06.30.2007 @09:48:05 PM EDT)
• Du Yang (07.02.2007 @12:25:28 AM EDT)
• Se Kwon Kim (07.04.2007 @11:55:52 AM EDT)