xxi. Two Envelopes Paradox

Problem. Two envelopes hold $a$ and $2a$. You pick one uniformly at random and see $x$. “The other one holds $2x$ or $x/2$ with probability $\frac{1}{2}$ each, so it is worth $\frac{1}{2}\cdot 2x+\frac{1}{2}\cdot \frac{x}{2}=\frac{5}{4}x>x$: always switch.” The same argument applied to the other envelope says to switch back. Where is the error?

Answer. The step ”$2x$ or $x/2$ with probability $\frac{1}{2}$ each, for every $x$” is false for every probability distribution on $a$. Once a real prior is used, the answer depends on $x$; without looking, switching gains nothing; with a prior of finite mean, switching cannot gain for every $x$; and a randomized threshold beats $\frac{1}{2}$ against every prior.

Situation	Conclusion
no information used	staying and switching both give $\frac{3}{2}a$ in expectation (symmetry)
prior on $a$, you see $x$	switch iff $P(\text{you hold the smaller}\mid x)>\frac{1}{3}$
”$\frac{1}{2}$ / $\frac{1}{2}$ for every $x$“	needs a uniform distribution on all of $\{2^k:k\in \mathbb{Z}\}$, which does not exist
prior with $\mathbb{E}[a]<\infty$	switching cannot have positive conditional gain for every $x$
Broome’s prior $P(a=2^k)=\frac{2^k}{3^{k+1}}$, $k\ge 0$	conditional gain $+\frac{x}{10}$ for every $x\ge 2$ (and $+x$ for $x=1$), but $\mathbb{E}[a]=\infty$
unknown prior, random threshold $T$ with positive density (Cover)	switch iff $x<T$: win probability $\frac{1}{2}+\frac{1}{2}P(a<T<2a)>\frac{1}{2}$

Where the argument breaks

Let $p(a)$ be the prior on the smaller amount. Seeing $x$, you hold the smaller envelope with posterior probability

$$P_s(x)=\frac{\frac{1}{2}p(x)}{\frac{1}{2}p(x)+\frac{1}{2}p(x/2)}=\frac{p(x)}{p(x)+p(x/2)},$$

and the expected gain of switching is $P_s\cdot x-(1-P_s)\cdot \frac{x}{2}$, positive iff $P_s>\frac{1}{3}$. The paradox silently assumes $P_s(x)=\frac{1}{2}$ for all $x$.

// prior p[k] = P(smaller amount = 2^k), k = 0..K-1; you see x = 2^k. Returns E[other - x | x].
double switchGain(const vector<double>& p, int k) {
    double small = k < sz(p) ? p[k] : 0;           // you hold the smaller: smaller = 2^k
    double big = k > 0 ? p[k - 1] : 0;             // you hold the larger: smaller = 2^(k-1)
    double x = ldexp(1.0, k), ps = small / (small + big);
    return ps * x - (1 - ps) * x / 2;
}
 
// Cover's randomized switching: threshold T ~ Exp(1); switch iff x < T. Returns the empirical win rate for smaller amount a.
double coverWinRate(double a, int trials, mt19937_64& rng) {
    exponential_distribution<double> T(1.0); int win = 0;
    for (int t = 0; t < trials; t++) {
        bool holdSmall = rng() & 1; double x = holdSmall ? a : 2 * a;
        bool sw = x < T(rng);
        win += (holdSmall != sw) ? 0 : 1;          // end with 2a iff (hold small and switch) or (hold big and stay)
    }
    return double(win) / trials;
}

Proof: symmetry, the impossible uniform prior, and the finite-mean theorem

Symmetry. Let $X$ be the amount in your envelope and $Y$ the other. The pair $(X,Y)$ has the same distribution as $(Y,X)$ (the choice is a fair coin independent of $a$), so $\mathbb{E}[X]=\mathbb{E}[Y]=\frac{3}{2}\mathbb{E}[a]$ whenever this is finite: switching blindly gains nothing.

No prior gives $\frac{1}{2}$ everywhere. $P_s(2^k)=\frac{1}{2}$ for all $k\in \mathbb{Z}$ means $p(2^k)=p(2^{k-1})$ for all $k$, so $p$ is constant on $\{2^k\}$; a constant cannot sum to 1 over infinitely many points.

Finite mean. Suppose $\mathbb{E}[a]<\infty$ and $g(x)=\mathbb{E}[Y-X\mid X=x]\ge 0$ for every $x$ with $g>0$ on a set of positive probability. Then $\mathbb{E}[Y-X]=\mathbb{E}[g(X)]>0$, contradicting $\mathbb{E}[Y]=\mathbb{E}[X]$. Hence with a finite-mean prior, “switching is better whatever I see” is false.

Broome’s prior. For $k\ge 1$, $\frac{p_k}{p_{k-1}}=\frac{2^k/3^{k+1}}{2^{k-1}/3^k}=\frac{2}{3}$, so $P_s=\frac{2/3}{1+2/3}=\frac{2}{5}>\frac{1}{3}$ and the gain is $\frac{2}{5}x-\frac{3}{5}\cdot \frac{x}{2}=\frac{x}{10}$; at $k=0$ you surely hold the smaller and gain $x$. The prior sums to $\frac{1}{3}\sum (2/3{)}^k=1$, but $\mathbb{E}[a]={\sum }_k\frac{2^k\cdot 2^k}{3^{k+1}}=\frac{1}{3}\sum (4/3{)}^k=\infty$, so the symmetry identity $\mathbb{E}[Y-X]=0$ is $\infty -\infty$ and nothing contradicts the positive conditional gains.

Cover’s strategy. Condition on $a$ and $T$. If $T\le a$ both possible $x$ are $\ge T$: you never switch and win with probability $\frac{1}{2}$. If $T>2a$ you always switch: again $\frac{1}{2}$. If $a<T\le 2a$ you switch exactly when holding $a$, so you always end with $2a$. Averaging, the win probability is $\frac{1}{2}+\frac{1}{2}P(a<T\le 2a)$, and $P(a<T\le 2a)>0$ because $T$ has positive density on $(0,\infty )$. For $T\sim \mathrm{Exp}(1)$ this is $\frac{1}{2}+\frac{1}{2}(e^{-a}-e^{-2a})$. Both functions were checked against simulation (posterior gains for Broome’s prior, win rates for $a=0.1,0.7,2,5$).

Related notes

• Probability and Expectation
• St. Petersburg Paradox (the other famous infinite-expectation paradox)
• Monty Hall