Optimal strategy to get maximum element of $n$ sequentially i.i.d uniform distribution $X_1, \cdots, X_n \sim \text{Uniform}(0,1)$?

Question

This is a homework for probability. To warm-up let's consider the case of $3$.

Consider three random variables $X_1, X_2, X_3$ that are independently and identically distributed according to the Uniform$(0,1)$ distribution. I observe these random variables sequentially, one at a time. When I observe $X_1$, I have the choice to either accept it or reject it. If I accept it, the process stops. If I reject it, I move on to observe $X_2$ and again decide whether to accept or reject it. If I reject $X_2$, I must accept $X_3$.

What is the optimal strategy that I can get the maximum of $X_1, X_2, X_3$?

I found my answer is different from the standard solution.

Method1: my answer To solve this problem, we can define two thresholds, $t_1$ and $t_2$, which will determine whether we accept or reject $X_1$ and $X_2$.

Let $$f(t_1, t_2) = P(X_1 > t_1 \text{ and } X_1 > \max(X_2, X_3)) + P(X_1 < t_1 \text{ and } X_2 > t_2 \text{ and } X_2 > \max(X_1, X_3)) + P(X_1 < t_1 \text{ and } X_2 < t_2 \text{ and } X_3 > \max(X_1, X_2))$$

Our objective is to choose $t_1$ and $t_2$ to maximize $f(t_1, t_2)$. Unfortunately, there doesn't seem to be an analytic solution for this. Below is the Mathematica code to find a numerical solution:

f[t1_, t2_] := 
 Integrate[
   1, {x1, x2, x3} \[Element] 
    ImplicitRegion[
     0 < x1 < 1 && 0 < x2 < 1 && 0 < x3 < 1 && x1 > t1 && 
      x1 > Max[x2, x3], {x1, x2, x3}]] + 
  Integrate[
   1, {x1, x2, x3} \[Element] 
    ImplicitRegion[
     0 < x1 < 1 && 0 < x2 < 1 && 0 < x3 < 1 && x1 < t1 && x2 > t2 && 
      x2 > Max[x1, x3], {x1, x2, x3}]] +
  Integrate[
   1, {x1, x2, x3} \[Element] 
    ImplicitRegion[
     0 < x1 < 1 && 0 < x2 < 1 && 0 < x3 < 1 && x1 < t1 && x2 < t2 && 
      x3 > Max[x1, x2], {x1, x2, x3}]]

NMaximize[f[t1, t2], {t1, t2}]

{0.679846, {t1 -> 0.672608, t2 -> 0.545532}}

Method2: standard solution by teacher To find the optimal $t_1$, we need to maximize the following probability function $f(t_1)$: $$f(t_1) = P(X_1 > t_1 \text{ and } X_1 > \max(X_2, X_3)) + P(X_1 < t_1 \text{ and } X_1 < \max(X_2, X_3))$$

Note that the probability density function of $\max(X_2, X_3)$ is $2y$. Substituting this into the equation for $f(t_1)$, we get: $f(t_1) = -\frac{2}{3} t_1^3 + t_1 + \frac{1}{3}$. Upon maximizing $f(t_1)$, we find $t_1 = \frac{1}{\sqrt{2}}$ yields the maximum value.

Similarly, for $t_2$, the objective is to maximize the following probability function $g(t_2)$:

$$g(t_2) = P(X_2 > t_2 \text{ and } X_2 > X_3) + P(X_2 < t_2 \text{ and } X_2 < X_3)$$ By optimizing $g(t_2)$, we find that the optimal value is $t_2 = \frac{1}{2}$.

The teacher's solution can be generalized to get analytic solution to $n$ cases.

Which way is correct? I have a feeling that the instructor's solution resembles a greedy algorithm, but is it truly globally optimal?

Answer 1

The teacher's solution is incorrect. To compute $t_1$, it is insufficient to maximize $$P(X_1 > t_1 \text{ and } X_1 > \max(X_2, X_3)) + P(X_1 < t_1 \text{ and } X_1 < \max(X_2, X_3))$$ because the two events we're summing mean different things for us. If $X_1>t_1$ and $X_1 > \max(X_2, X_3)$, then we choose $X_1$ and definitely win. If $X_1 < t_1$ and $X_1 < \max(X_2, X_3)$, then we reject $X_1$ and still have a chance to win - however, depending on $X_2$, we may also still lose.

Method 1, however, is also incorrect. In the situation where $X_1 < t_1$ (so we moved on to $X_2$) and $X_2 < X_1$, we must always move on to $X_3$ to maximize our probability of victory, even if $X_2 > t_2$. (If $X_2 < X_1$, then it cannot possibly be the largest, but $X_3$ still might be.) Therefore our winning scenarios are:

1. $X_1 > t_1$ and $X_1 > \max(X_2, X_3)$. We select $X_1$ and win.
2. $X_1 < t_1$ and $X_2 > \max(X_1, t_2)$ and $X_1 > \max(X_2,X_3)$. We skip $X_1$ and select $X_2$ and win.
3. $X_1 < t_1$ and $X_2 < \max(X_1, t_2)$ and $X_3 > \max(X_1,X_2)$. We skip $X_1$ and skip $X_2$ and win.

My Mathematica code to solve this is

 psuccess = FullSimplify[Probability[
  (X1 > t1 && X1 > Max[X2, X3]) || 
  (X1 < t1 && X2 > Max[X1, t2, X3]) || 
  (X1 < t1 && X2 < Max[X1, t2] && X3 > Max[X1, X2]), 
  {X1 \[Distributed] UniformDistribution[], 
   X2 \[Distributed] UniformDistribution[], 
   X3 \[Distributed] UniformDistribution[]}], 
  0 < t1 < 1 && 0 < t2 < 1]
FullSimplify[Maximize[{psuccess, 0 <= t1 <= 1, 0 <= t2 <= 1}, {t1, t2}]]

and it gives me a probability of success of $\frac{1}{600} \left(48 \sqrt{6}+293\right) \approx 0.684293$ when $t_1 = \frac{1+\sqrt6}{5}$ and $t_2 = \frac12$.