Why does this strategy to pick the largest envelope work?

Question

Game:
You have two envelopes. Each one contains a real number.
Choose one envelope and you get to see the number on it. Now you have two choices: select the same envelope, or swap.
At the end, if you have chosen the greater number, You win.

Problem:
Find a strategy that gives you a probability of winning that is more than $0.5$

---

Solution:
Choose one real number $x$. If envelope one contains $y>x$, keep it, else swap.

---

My Question: Why does the strategy work? Can we prove that probability-theoretically?

Answer 1

At first, it seems incredible that this can even work. The two numbers can be selected in any way at all, and you have no way of knowing what the other number is. Nonetheless, you can answer in such a way that your choice is more likely than not to be correct.

Method: Select any cumulative distribution function (CDF) $F(x)$ that is strictly increasing; that is, pick a function $F(x)$ such that

• $F(x) > F(y)$ for all $x > y$.
• $F(x)$ goes to $0$ as $x$ goes leftward to negative infinity.
• $F(x)$ goes to $1$ as $x$ goes rightward to positive infinity.

To make things simple, a suitable function is $F(x) = \frac{2^x}{1 + 2^x}$. (This is similar to the standard logistic function, but with base $2$ instead of base $e$.)

I'll use this function in what follows. (As an aside, I don't think it's actually significant that $F(x)$ is a CDF; we're not drawing numbers from that distribution in any explicit sense. It's just a convenient shorthand for what we want it to look like.)

The OP's function is the step function; that is,

$$ F(x) = \begin{cases} 0 & x < x_0 \\ 1 & x \geq x_0 \end{cases} $$

That has the disadvantage that it's not strictly increasing, so there are some cases (in which both numbers are greater than $x_0$, or both numbers are less than $x_0$) where the strategy doesn't help. Averaged over all cases, however, the strategy does help. (But how much? Ahh, that's the question.)

---

Now, if the number you look at is $x$, you keep your envelope with probability $F(x)$, and switch it with probability $1-F(x)$. For instance, if you open an envelope and see the number $3$, you keep your envelope with probability $F(3) = \frac{2^3}{1+2^3} = 8/9$, and switch it with probability $1-F(3) = 1/9$.

Your probability of getting the right answer can now be determined as follows: Suppose the two numbers I selected were $a$ and $b$, with $b > a$. Your answer is correct if either you looked at $a$ and switched (with probability $1–F(a)$), or you looked at $b$ and kept the envelope (with probability $F(b)$). Since each of these two scenarios is equally likely—remember, you got to choose the envelope you looked at, with no prior information—your overall probability of guessing correctly is

$$ P(\text{correct}) = \frac{1-F(a)+F(b)}{2} = \frac12 + \frac{F(b)-F(a)}{2} $$

Since $F(x)$ is strictly increasing on the reals, and $b > a$, we must have $F(b) > F(a)$, and so your probability of being correct must be strictly greater than $1/2$.

---

On my work blog, one of my work colleagues mentioned that he felt initial unease about this result, but eventually resolved it by proposing that if you were to draw a "random" CDF in some way, then the average difference between their CDF values $E[F(b)-F(a) \mid a, b]$ is equal to $0$. That is, on average (in some sense), the bump we get from our CDF is zero. This seems like it contradicts the fact that the bump is always positive—or does it?

Part of the problem with our intuition here is that there is no uniform distribution on the space of strictly increasing CDFs, in pretty much the same way that there is no uniform distribution on the integers. (That is to say, there's no algorithm that picks a random integer such that each value is equally likely.) The way we negotiate this in the case of the integers is to restrict our attention to the interval $[-m, m]$, analyze the behavior on that domain, and then see how that behavior evolves as we let $m$ go off to infinity.

As an example, we might consider the double-ended sequence $a_n = \frac{1}{|n|+1}$, defined on the integers. (Note: This is not a distribution; we're going to take the expected value of a randomly selected value from this sequence, given a uniform distribution over larger and larger intervals.) The central portion of this sequence looks like this:

It's clear that every value of this sequence is positive. But, we might ask, what is its average value? We can't evaluate this directly by just summing the product of each value and its probability, because as we said, there is no uniform distribution on the integers. We can't even add up the values and divide by the number of values, because both the sum and the count are infinite. The way we approach this is to consider the sum of the sequence for $n$ between $–m$ and $m$. This is related to the harmonic numbers $H_m$; the sum of our sequence is given by $2H_{m+1}–1$. We don't actually need to know the exact value of $H_m$; we only need to know a good upper bound. In this case, a good upper bound is $1+\ln m$, where $\ln$ denotes the natural log. This tells us that the sum of this sequence between $–m$ and $m$ is a positive value less than $1+2\ln(m+1)$. Since there are $2m+1$ values in all, the average of these values is bounded by

$$ E_m \leq \frac{1+2\ln(m+1)}{2m+1} $$

All we need to do now is see what what $E_m$ does as $m$ goes off to infinity. Of course, we only have an upper bound, and not $E_m$ itself, but there is a limit theorem, popularly called the squeeze theorem, that tells us (broadly speaking) that if we have a function that is always between two other functions, and the two other functions have the same limit, then the middle function must have the same limit. Since our average is always between $0$ and our upper bound, and our upper bound goes to $0$ (and $0$ obviously goes to $0$), our average must therefore go to $0$, even though it's the average of values that themselves are always positive!

Something similar can be done with our CDFs. One property that we might expect a uniform distribution over the CDFs to have is indifference to translation. This is getting a little hand-wavy, I concede, but the basic idea is that if all CDFs are, in some sense, equally likely, then sliding a CDF either left or right (without otherwise changing it) shouldn't make that CDF more or less likely to be chosen. If we let it slide by up to m units either left or right, and average uniformly over that range, we get

\begin{align} E_m[F(b)-F(a)] & = \frac{1}{2m} \int_{t=-m}^m F(b+t)-F(a+t) \, dt \\ & = \frac{1}{2m} \left[ \int_{t=-m}^m F(b+t) \, dt - \int_{t=-m}^m F(a+t) \, dt \right] \\ & = \frac{1}{2m} \left[ \int_{u=a}^b F(u+m) \, du - \int_{u=a}^b F(u-m) \, du \right] \\ & = \frac{1}{2m} \int_{u=a}^b F(u+m) - F(u-m) \, du \\ & \leq \frac{b-a}{2m} \end{align}

where the last step follows because $F$ is bounded between $0$ and $1$. But it's clear that if we let $m$ go to infinity, for any given values of $a$ and $b$, this fraction will go to $0$. Since the expectation cannot be negative, we can use the squeeze theorem again to show that the expected gain in our decision algorithm is $0$, even though any particular gain is always positive, thus resolving the apparent paradox.

Answer 2

Let $P$ denote the unknown probability distribution that generates the numbers in the envelopes, and $X_1,X_2$ be iid $\sim P$. Let $F$ denote the CDF of $P$.

A strategy is specified once you define the set $A$ such that: if the number in envelope 1 is in $A$, keep envelope 1, otherwise swap. Assume that $A$ is a Borel set and note that the probability $W$ of winning is

$$ \begin{aligned} W &=P(\{X_1\geq X_2\} \cap \{X_1\in A\}) + P(\{X_1< X_2\} \cap \{X_1\notin A\}) \\&= E[E[1_{X_1\geq X_2}1_{X_1\in A}|X_1]] + E[E[1_{X_1< X_2}1_{X_1\notin A}|X_1]] \\&= E[F(X_1)1_{X_1\in A} + (1-F(X_1))1_{X_1\notin A} ], \end{aligned} $$ hence $$W-1/2 = 1/2E\big[\big(1-2F(X_1)\big)\big(1-2\cdot1_{X_1\in A}\big)\big].$$

Now, if $m$ satisfies $F(x)\geq 1/2 \iff x\geq m$ (i.e., $m$ is the leftmost median), by letting $A=[m,\infty)$ (i.e, the strategy is to keep the first envelope if and only if the number in it is $\geq m$), then $$\big(1-2F(X_1)\big)\big(1-2\cdot1_{X_1\in A}\big)$$ is always nonnegative. If additionnally $P\big(F(X_1)=1/2\big)<1$, then $W> 1/2$.

Note that this strategy is deterministic, there is no additional sampling compared to the other answer.

---

OP's suggested strategy is to take $A=(x,\infty)$ for arbitrary $x$. Given the formula for $W-1/2$ given above, I doubt this works.

Answer 3

(Previously looked at it from the wrong point of view...)

If the two envelope numbers, and YOUR number, are all picked using the same random number generator, and all you can ask is is A > B, then, for all that it matters, the random number generator could be handing out 1, 2, and 3 for each set.

So if we call the numbers in the envelopes Y and Z, and your number X, then one of these is true, with equal probability:

Y<Z<X
Z<Y<X
Y<X<Z
Z<X<Y
X<Y<Z
X<Z<Y

In the first three cases, you elect the second envelope, as Y<X. In the last three cases you elected the first envelope as X<Y.
And you win with those selections in: 1, 3, 4, and 6. Thus 2/3 probability of a win.

One might claim that one could get equal numbers. I claim that this is negligible, as we are talking about real numbers, and presumably a continuous distribution.

Answer 4

My two cents, or maybe just a rewriting with a different terminology.

Call $1,2$ the envelops and $f(x)$ the p.d.f. of their values $X_1$ and $X_2$, supposed to be independent. Call also $e \in {1,2}$ the r.v. corresponding to the envelop chosen at first. Then the probability of winning can be written:

$$P=\sum_e \int_R \int_R dx_1 dx_2 f(x_1)f(x_2)p(e) 1_{V}(x_1,x_2,e)$$

where $1_V$ is the indicator function of the winning set and $p(e)=1/2$. Now by symmetry we can choose $e=1$ and multiply by 2:

$$P=\int_R \int_R dx_1 dx_2 f(x_1)f(x_2)1_{V}(x_1,x_2,e=1)$$

Remaining steps. Observe that:

$$1_{V}(x_1,x_2,e=1)=\theta(x_1-x_0)\theta(x_1-x_2)+\theta(x_0-x_1)\theta(x_2-x_1)$$

Substituting after some calculations:

$$P=\int_{x_0}^{+\infty}dx'\int_{-\infty}^{x^{''}} dx^{''} f(x')f(x'')+ \int_{-\infty}^{x_0}dx'\int_{x'}^{+\infty} dx^{''} f(x')f(x'')$$

We conclude with a visual proof. Note that what we are doing here is integrating the density over the areas A,B. Since the blue parts have a symmetric (w.r.t. the diagoanl) part included into $A \bigcup B$, that $f(x_1,x_2)$ is symmetric, and that the total density integrates to $1$, it follows that the integral of the joint density over $A \bigcup B$ must be greater than $0.5$.