5
$\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$ Commented Jan 28, 2024 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$ Commented Jan 28, 2024 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$ Commented Jan 28, 2024 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$ Commented Jan 28, 2024 at 21:54

1 Answer 1

Reset to default
9
$\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$ Commented Jan 29, 2024 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$ Commented Jan 29, 2024 at 10:42
  • $\begingroup$ Ah, nice. Maybe put that in the answer as well. $\endgroup$ Commented Jan 29, 2024 at 10:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.