1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ I think this is a similar problem: mathworld.wolfram.com/SultansDowryProblem.html $\endgroup$ Commented Sep 6, 2023 at 19:59
  • $\begingroup$ To be clear, the goal is just to maximize the probability you stop at the max of the 3 random variables, not to maximize the expected value of the random variable you stop at, right? $\endgroup$ Commented Sep 6, 2023 at 21:18
  • $\begingroup$ @user6247850 Yes, maximize the probability of get the best of three. $\endgroup$ Commented Sep 6, 2023 at 21:30
  • $\begingroup$ @BBBBBB Thanks for sharing this question. I believe there's a distinct difference. The Wolfram page assumes that the distribution of the random variable is unknown. Specifically, when (n = 2), the optimal strategy—according to the Wolfram page—is to pick the first variable, yielding a probability $P = 0.5$ that it will be the largest. However, if the distribution is known to be Uniform(0,1), a different strategy emerges: accepting the first variable if it is greater than 0.5, which leads to a higher probability of $P = 0.75$ for it to be the largest. $\endgroup$ Commented Sep 6, 2023 at 23:19
  • $\begingroup$ @maplemaple True. Though perhaps others will find the dowry problem interesting :) $\endgroup$ Commented Sep 7, 2023 at 0:44

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Awesome! It seems that existence of $t_1$ will not change the $t_2 = 0.5$. I also check the case $n = 4$, $t_2=(1+\sqrt{6}) / 5$ and $t_3=0.5$ still are same. I think there is a way to get general solution of $n$ by some recurrence relation. $\endgroup$ Commented Sep 7, 2023 at 1:19

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.