4
$\begingroup$

Here is a probability game description:

You generate a uniformly random number in the interval (0,1). You can generate additional random numbers as many times as you want for a fee of $ 0.02 per generation. This decision can be made with the information of all of the previous values that have been generated. Your payout is the maximum of all the numbers you generate. Under the optimal strategy, find your expected payout of this game.

For this game, my approach was to determine the number of rolls n, at which the expected difference between the maximum of n rolls and n-1 rolls is below 0.02. This would be the point at which I wouldn't roll anymore, as the fee overshadows the expected gain. Setting this up as follows:

$X = Max( X_1,...X_n)$, $Y = Max(X_1,...,X_{n-1})$

$E(X) - E(Y) \leq 0.02 $

$\frac{n}{n+1} - \frac{n-1}{n} \leq 0.02$

Solving this, we get n = 6.58. Then, as the number of rolls is discrete, we take n=6. Then the expected payout should be:

$Payout = \frac{6}{7} - 0.02*5 = 0.76$

However, the answer is 0.82. What is wrong with my logic?

$\endgroup$
4
  • 2
    $\begingroup$ You are not using the information of the previous rolls. For example, conditional on drawing a number $>0.98$ as the first number, you would stop immediately because then you couldn't gain more than $0.02$ anyway. $\endgroup$ Jan 28 at 20:21
  • $\begingroup$ The question seems to be: Consider the stochastic process $Y_n = \sup\{X_1,\dots,X_n\} - \frac n{50}$, then find a stopping time $\tau$ which maximizes $\mathbb E(Y_\tau)$. $\endgroup$ Jan 28 at 20:22
  • $\begingroup$ I see, so my answer would only be correct in the scenario where we have to choose the fixed number of rolls we make before starting the game? $\endgroup$
    – Anon
    Jan 28 at 21:43
  • $\begingroup$ When I saw $0.82$, I first thought that it was a version of a question I looked at in grad school mumblety-mumble years ago. But that question was actually the first question here. I think I got as far as obtaining $0.8185$ (approximately), but I never returned to it. $\endgroup$
    – Brian Tung
    Jan 28 at 21:54

1 Answer 1

5
$\begingroup$

If the current maximum is $x$, the expected maximum if you draw is $$ x^2 + (1-x) \Bigl( \frac{x+1}{2} \Bigr) $$ so the expected improvement is $$ \left( x^2 + (1-x) \Bigl( \frac{x+1}{2} \Bigr) \right) - x $$ which exceeds ${\large{\frac{1}{50}}}$ (the cost of the draw) when $x < {\large{\frac{4}{5}}}$.

Hence the optimal strategy is to draw if $x < {\large{\frac{4}{5}}}$, otherwise stop.

Let $e$ be the expected value of the game assuming the above stopping rule.

Then we get $$ e = \Bigl(\frac{1}{5}\Bigr) \Bigl(\frac{9}{10}\Bigr) + \Bigl(\frac{4}{5}\Bigr) \Bigl(e-\frac{1}{50}\Bigr) $$ which yields $e={\large{\frac{41}{50}}}=.82$.

$\endgroup$
3
  • $\begingroup$ Can you explain where your first formula comes from? $\endgroup$
    – quarague
    Jan 29 at 7:59
  • $\begingroup$ @quarague: With probability $x$ there will be no improvement, so the new maximum will still be $x$, hence for this case, the contribution to the expected maximum is $$ x{\,\cdot\,}x=x^2 $$ and with probability $1-x$ the expected new maximum will be half way between $x$ and $1$, hence for this case, the contribution to the expected maximum is $$ (1-x) \Bigl( \frac{x+1}{2} \Bigr) $$ $\endgroup$
    – quasi
    Jan 29 at 10:42
  • $\begingroup$ Ah, nice. Maybe put that in the answer as well. $\endgroup$
    – quarague
    Jan 29 at 10:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .