2
$\begingroup$

The problem is as follows:

You get to choose between two envelopes, each of which contains a check for some positive amount of money. Assume that the two values inside the envelopes were generated independently from some distribution on positive real numbers, with no information given about what that distribution is.

After picking an envelope, you can open it and see how much money is inside and then you have the option of switching.

Consider the following strategy for deciding whether to switch. Generate a “threshold” $T \sim Expo(1)$, and switch envelopes if and only if the observed value $x$ is less than the value of $T$. Show that this strategy succeeds in picking the envelope with more money with probability strictly greater than $\frac{1}{2}$.

So I didn't really follow the strategy and was wondering whether or not my method is right. I think I may have found a more general solution to this problem that does not depend on the distribution of the threshold. Here is my solution:

Let $t$ be some threshold such that if the observed value is less than this threshold, we switch.

Let $I$ be the indicator variable indicating that we picked the better envelope.

Let $X,Y$ be the random variables describing the amount of money in each of the envelopes.

In the case that $t$ is in between $X$ and $Y$, the output of $I$ will always be $1$. This is because if the envelope we pick is smaller than $t$, then we would switch to the larger one and if the envelope we pick is larger than $t$, then we do no switch. If $t$ is larger than both $X$ and $Y$, then we have a $\frac{1}{2}$ chance that we switch to the correct envelope. If $t$ is smaller than both $X$ and $Y$, then we have a $\frac{1}{2}$ chance that we already picked the correct envelope. We can mathematically represent this as follows:

\begin{align} E(I) &= E(I \mid X \leq t \leq Y)P(X \leq t \leq Y) \\ &+ E(I \mid Y \leq t \leq X)P(Y \leq t \leq X) \\ &+ E(I \mid Y \leq t, X \leq t)P(Y \leq t)P(X \leq t) \\ &+ E(I \mid Y \geq t, X \geq t)P(X \geq t)P(Y \geq t) \\ &= 1P(X \leq t)P(Y \geq t) + 1P(Y \leq t)P(X \geq t) \\ &+ \frac{1}{2}P(Y \leq t)P(X \leq t) + \frac{1}{2}P(X \geq t)P(Y \geq t) \end{align}

To simplify the notation, suppose we let $x=P(X \leq t), y=P(Y \leq t)$, then we have:

\begin{align} E(I) &= x(1-y) + y(1-x) + \frac{1}{2}xy + \frac{1}{2}(1-x)(1-y) \\ &= \frac{1}{2} + \frac{1}{2}x + \frac{1}{2}y - xy \geq \frac{1}{2} \end{align}

Is this a valid solution? Furthermore, in my last line, is there a better way to show that it is always greater than a half? I did it by quickly finding the max and min using calculus.

$\endgroup$
3
$\begingroup$

This is a good idea, but not a valid solution, since the question asks you to prove that the probability is strictly greater than $\frac12$ and you merely showed that it's greater or equal, with equality for $x=y=0$ and $x=y=1$.

By the way, the question isn't quite well-posed; it should specify that the distribution of the amounts is continuous; as it's written, there could be a finite probability that the amounts are the same. You also glossed over this possibility in your solution.

As to your question about a better way to prove the last inequality: This follows from $\left(x-\frac12\right)\left(y-\frac12\right)\le\frac14$, which holds since $x$ and $y$ are probabilities, so the absolute value of either factor is $\le\frac12$.

$\endgroup$
  • $\begingroup$ Hmm, so if the question specified that it is continuous, would my solution be valid since "greater than or equal to" and just "greater than" have the same meaning when continuous? $\endgroup$ – Justin Liang Jun 2 '16 at 9:23
  • $\begingroup$ If it's invalid, do you know why my method is incorrect. That is, why does my solution suggest that it can be equal to $\frac{1}{2}$? $\endgroup$ – Justin Liang Jun 2 '16 at 9:24
  • 1
    $\begingroup$ @JustinLiang: The problem can't be solved with a constant threshold, since the distribution of the amounts could lie entirely above or entirely below the threshold (corresponding to $x=y=0$ and $x=y=1$, respectively). You need the threshold to have a distribution with support on all of the positive reals to avoid this problem. See also Wikipedia. $\endgroup$ – joriki Jun 2 '16 at 9:26
  • $\begingroup$ Ah okay, just wondering, if the answer asked for a solution that is "greater than or equal to" a half, would my solution be valid? $\endgroup$ – Justin Liang Jun 2 '16 at 16:07
  • 1
    $\begingroup$ @JustinLiang: Yes, but then the solution "uniformly randomly pick one of the envelopes" would also be valid, so no need to go to all that effort in that case :-) $\endgroup$ – joriki Jun 2 '16 at 16:15

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.