1
$\begingroup$

If we have a series of $n$ IID random variable $X_i$ that are uniform [0,1], and at each round $i$ we decide to either keep $X_i$ or discard it for the next number. What is our strategy to maximize our final number? and what is the expected number we get under this strategy?

I figured this is pretty much the coin toss problem but with a continuous uniform [0,1] distribution. Let $f(n)$ be our expected final number if we're allowed n "re-toss". The strategy is that, if we have $n$ "tosses" left, we only keep our current number if it's greater than $f(n-1)$,otherwise we go for the next number.

With Uni~[0,1], the probability that we draw a number less than $f(n-1)$ is $f(n-1)$, so This gives the equation $$ \begin{aligned} f(n) &= P(X_1 < f(n-1))f(n-1) + P(X_1 >= f(n-1))E[X_1|X_1 >= f(n-1)]\\ &= f(n-1)*f(n-1) + (1-f(n-1))*\frac{f(n-1)+1}{2}\\ &= f(n-1)^2 + \frac{1-f(n-1)^2}{2}\\ &=\frac{f(n-1)^2}{2} + \frac{1}{2} \end{aligned} $$

My question is, with the initial condition that $f(1) = 0.5$, is there any way to make the above into a non-recursive solution? As in, a solution where we can compute $f(n)$ without computing $f(n-1),f(n-2)...$

$\endgroup$
2
  • $\begingroup$ I cannot find a closed form for your $f,$ but it is straightforward to show that asymptotically $f(n) \approx 1 - 2/(n+1).$ For instance, $f(1000000) = 0.999998\, 000032\ldots$ while $1 - 2/1000001 = 0.999998\, 000002\ldots.$ $\endgroup$
    – whuber
    Sep 8, 2022 at 17:20
  • $\begingroup$ BTW, it's unclear what your objective is. Do you want to maximize the chance of selecting the largest value in the series? If not, then what actually is being maximized? Your strategy maximizes the expectation of the number that is kept. $\endgroup$
    – whuber
    Sep 8, 2022 at 21:56

1 Answer 1

-1
$\begingroup$

I think you are overcomplicating this. With $X_1, X_2, \dotsc, X_n$ iid uniform on the standard interval $(0,1)$, your construction is simply computing $\max_{i=1}^n X_i$, and to find that distribution is a standard exercise, solved at How do you calculate the probability density function of the maximum of a sample of IID uniform random variables?

$\endgroup$
1
  • $\begingroup$ How does this lead to a strategy?? $\endgroup$
    – whuber
    Sep 8, 2022 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.