Ponder This Challenge - January 2009 - Value of a replaceable lottery ticket

Ponder This Challenge:

Consider the following game. You have an opportunity to buy lottery tickets. Each ticket has a value t randomly and independently picked from the continuous and uniform distribution on the interval(0,1). Each ticket costs c (0<c<1). If you don't like the ticket you get you can throw it away and buy another one (at a cost of c). You can do this as often as you want. You can stop at any time and cash in the current ticket at which point the game ends. Your winnings are the value of the ticket you cashed less the cost of all the tickets you bought. You don't have to buy any tickets in which case your winnings are 0. If you adopt the best strategy what are your expected winnings as a function of c?

Suppose we modify the game so that you don't have to throw away any tickets. When you decide to stop buying tickets you can cash in any (but only one) of the tickets you have purchased and the game ends. Now what are your expected winnings (using the best strategy) as a function of c?

Note:

Some of the solvers are overlooking a minor point. For credit please ensure your answer is correct for the entire range of c.

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

  The answer to the first part is

  1-sqrt(2*c) for c < .5
  0 for .5 < c

  This can be seen as follows. Clearly the best strategy will be to keep buying tickets until you obtain one greater than some threshold x and then to stop (or for large c to buy no tickets at all). You can expect to buy 1/(1-x) tickets on average each at a cost of c. The expected value of the final ticket will be (1+x)/2. Hence your expected winnings are .5*(1+x)-c/(1-x). So we must find the threshold x which maximizes this. Setting the derivative to 0 we obtain .5-c/((1-x)**2)=0 or (1-x)**2 = 2*c or 1-x = sqrt(2*c) or x=1-sqrt(2*c). Substituting, the expected winnings are then 1-.5*sqrt(2*c)-c/sqrt(2*c) = 1-.5*sqrt(2*c)-.5*sqrt(2*c) = 1-sqrt(2*c). For c>.5 these values are less than 0 which means you shouldn't buy any tickets.

  The answer to the second part is the same. This is because if it is correct to buy an additional ticket it will be correct to keep on buying additional tickets until you get one which is better than the best one that you already hold. Thus when you are allowed to buy an unlimited number of tickets it will never be best to cash an earlier ticket. Note this is not the case when there is a limit on how many tickets you can buy.

Solvers

• Arthur Breitman (01.02.2009 @08:06 PM EST)
• Adam Daire (01.03.2009 @02:07 AM EST)
• Frank Yang (01.03.2009 @03:01 PM EST)
• V Balakrishnan (01.03.2009 @07:35 PM EST)
• Joe Riel (01.03.2009 @08:29 PM EST)
• Michael Peake (01.04.2009 @05:05 AM EST)
• Christian Blatter (01.04.2009 @11:44 AM EST)
• Ariel Flat(01.04.2009 @09:45 PM EDT)Mark Perkins(01.05.2009 @04:11 PM EST)David Meiri and Dan Arnon(01.05.2009 @05:00 PM EST)Koen Vossen(01.06.2009 @05:39 AM EST)James Dow Allen(01.06.2009 @06:28 AM EST)Rickard Bjorklund and Carl Hammarlund(01.06.2009 @06:27 PM EST)Javier Rodriguez and Els Claes(01.06.2009 @08:10 PM EST)Ashish Mishra(01.06.2009 @09:11 PM EST)Dave Parashar(01.07.2009 @01:26 AM EST)Oyvind Grotmol(01.07.2009 @02:01 AM EST)John Robinson(01.07.2009 @03:51 AM EST)Jonathan Campbell(01.07.2009 @02:13 PM EST)Tomas Sirgedas(01.07.2009 @10:13 PM EST)Erik Hostens(01.08.2009 @11:20 AM EST)John G. Fletcher(01.08.2009 @11:20 PM EST)Paul Shearer(01.11.2009 @07:06 PM EST)Chris Drost(01.07.2009 @06:26 PM EST)Dan Dima(01.07.2009 @07:36 PM EST)Martin Thiim(01.08.2009 @04:08 PM EST)Steve Langerwerf(01.09.2009 @06:52 AM EST)Joe Fendel(01.09.2009 @02:45 PM EST)Austin Shapiro(01.11.2009 @04:57 AM EST)Prodipta Ghosh(01.12.2009 @03:07 PM EST)John Ritson(01.12.2009 @08:40 PM EST)Gary M. Gerken(01.14.2009 @03:38 AM EST)Albert Stadler(01.14.2009 @08:33 AM EST)Robin J. Ryder(01.14.2009 @05:48 PM EST)Ganesh Lakshminarayana(01.14.2009 @08:40 PM EST)Renato Fonseca(01.16.2009 @12:52 AM EST)Jerry Wedekind(01.17.2009 @02:04 AM EST)Richard Mann(01.17.2009 @07:37 PM EST)Jeff Steele(01.19.2009 @06:55 PM EST)Boris Nikolaus(01.19.2009 @10:11 PM EST)Chris Hills(01.22.2009 @04:37 PM EST)Lovro Puzar(01.22.2009 @05:43 PM EST)Andrew Buchanan(01.24.2009 @10:10 AM EST)Aman_Cc(01.24.2009 @11:20 AM EST)Michael Schaaf(01.24.2009 @02:57 PM EST)Jesse Kolman(01.25.2009 @05:39 AM EST)Bojan Basic(01.27.2009 @06:09 PM EST)Greg Janoe(01.27.2009 @10:36 PM EST)Se Kwon Kim(01.28.2009 @06:33 AM EST)Martin Giese(01.30.2009 @07:26 AM EST)Andrea Andenna(01.31.2009 @10:16 AM EST)Ehud Schreiber(01.31.2009 @07:02 PM EST) (None)
• Ariel Flat (01.04.2009 @09:45 PM EDT)
• Mark Perkins (01.05.2009 @04:11 PM EST)
• David Meiri and Dan Arnon (01.05.2009 @05:00 PM EST)
• Koen Vossen (01.06.2009 @05:39 AM EST)
• James Dow Allen (01.06.2009 @06:28 AM EST)
• Rickard Bjorklund and Carl Hammarlund (01.06.2009 @06:27 PM EST)
• Javier Rodriguez and Els Claes (01.06.2009 @08:10 PM EST)
• Ashish Mishra (01.06.2009 @09:11 PM EST)
• Dave Parashar (01.07.2009 @01:26 AM EST)
• Oyvind Grotmol (01.07.2009 @02:01 AM EST)
• John Robinson (01.07.2009 @03:51 AM EST)
• Jonathan Campbell (01.07.2009 @02:13 PM EST)
• Tomas Sirgedas (01.07.2009 @10:13 PM EST)
• Erik Hostens (01.08.2009 @11:20 AM EST)
• John G. Fletcher (01.08.2009 @11:20 PM EST)
• Paul Shearer (01.11.2009 @07:06 PM EST)
• Chris Drost (01.07.2009 @06:26 PM EST)
• Dan Dima (01.07.2009 @07:36 PM EST)
• Martin Thiim (01.08.2009 @04:08 PM EST)
• Steve Langerwerf (01.09.2009 @06:52 AM EST)
• Joe Fendel (01.09.2009 @02:45 PM EST)
• Austin Shapiro (01.11.2009 @04:57 AM EST)
• Prodipta Ghosh (01.12.2009 @03:07 PM EST)
• John Ritson (01.12.2009 @08:40 PM EST)
• Gary M. Gerken (01.14.2009 @03:38 AM EST)
• Albert Stadler (01.14.2009 @08:33 AM EST)
• Robin J. Ryder (01.14.2009 @05:48 PM EST)
• Ganesh Lakshminarayana (01.14.2009 @08:40 PM EST)
• Renato Fonseca (01.16.2009 @12:52 AM EST)
• Jerry Wedekind (01.17.2009 @02:04 AM EST)
• Richard Mann (01.17.2009 @07:37 PM EST)
• Jeff Steele (01.19.2009 @06:55 PM EST)
• Boris Nikolaus (01.19.2009 @10:11 PM EST)
• Chris Hills (01.22.2009 @04:37 PM EST)
• Lovro Puzar (01.22.2009 @05:43 PM EST)
• Andrew Buchanan (01.24.2009 @10:10 AM EST)
• Aman_Cc (01.24.2009 @11:20 AM EST)
• Michael Schaaf (01.24.2009 @02:57 PM EST)
• Jesse Kolman (01.25.2009 @05:39 AM EST)
• Bojan Basic (01.27.2009 @06:09 PM EST)
• Greg Janoe (01.27.2009 @10:36 PM EST)
• Se Kwon Kim (01.28.2009 @06:33 AM EST)
• Martin Giese (01.30.2009 @07:26 AM EST)
• Andrea Andenna (01.31.2009 @10:16 AM EST)
• Ehud Schreiber (01.31.2009 @07:02 PM EST)