# Proof verification: Two envelope problem with values generated independently from some distribution

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.

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$.
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$.
• 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}$? – Justin Liang Jun 2 '16 at 9:24
• @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. – joriki Jun 2 '16 at 9:26