1

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)...$

wwyws
  • 331
  • 1
  • 7
  • 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.$ – whuber Sep 08 '22 at 17:20
  • 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. – whuber Sep 08 '22 at 21:56

1 Answers1

-1

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?

kjetil b halvorsen
  • 77,844