Pick a Number

Pick a Number

Here is a logic puzzle I find interesting. Unfortunately I don’t recall the source.

Alice picks two distinct real numbers, and puts one in each of two envelopes. Bob wants to pick the envelope containing the larger of the two numbers. Bob picks an envelope, and look at the number inside it.

After seeing the number, Bob can elect to switch envelopes. If he switches he has to take the second. If he doesn’t switch, he has to keep the first.

Is there a strategy that allows Bob to select the larger value with greater than a 50% chance?

As usual, this is a pure logic (well, math) puzzle. There is no trickery needed.

Solution

Let the two numbers Alice selected be $x<y$. Bob wants to select the envelope containing $y$ with greater than a 50% chance.

Bob picks a probability distribution (pdf) on the real numbers. (If you’re fuzzy on what this means, it is a method to select a real number at random with every possible real number as a possible outcome. Note that every number cannot be equally likely since the real numbers are infinite.) For example, the pdf

$$f(t)= \frac{1}{\sqrt{\pi}}\int_{-\infty}^{t} e^{-x^2} dx$$

works.

Bob rolls another number t from his distribution. Now when Bob opens his envelope, suppose he obtains value s (which is either x or y). If s < t, he switches, otherwise he keeps his original envelope. Here is a proof why this works.

Since $x<y$, the pdf gives some nonzero probability to pick a value between $x$ and $y$, call this $\epsilon>0$. Bob picked $s=x$ with 50% probability, so he wins if $x < t$, which triggers a switch to the envelop containing $y$. This case has probability $\frac{1}{2}\times P(x<t)$. Bob picked $s=y$ with probability 50, so he wins if $t < y$. This case has probability $\frac{1}{2}\times P(t < y)$

Thus Bob wins with probability
$$
\begin{aligned}
\frac{1}{2}\left(P(x<t)+P(t<y)\right) &= \frac{1}{2}\left(1 + P(x<t<y)\right) \\
&=\frac{1}{2}+\frac{\epsilon}{2}
\end{aligned}
$$

This Bob wins with probability strictly greater than 50%.

This non-intuitive result is because people often have trouble dealing with probabilities over an infinite set. This problem works because for any $x<y$, there is some small area between them on the pdf chosen, making it possible to decide to switch with better than 50% outcome.

Proof of pdf:

Let $I=\int_{-\infty}^{\infty} e^{-x^2} dx$. Then, multiplying two and switching to polar coordinates

$$
\begin{aligned}
I^2 &=\int_{-\infty}^{\infty} e^{-x^2} dx \int_{-\infty}^{\infty} e^{-y^2} dy \\
&= \int \int e^{-(x^2+y^2)} dx dy \\
&= \int_0^{2\pi} \int_0^\infty e^{-r^2} r dr d\theta \\
&= \int_0^{2\pi} d\theta \int_0^\infty e^{-r^2} r dr \\
&= 2\pi \left(\left.-\frac{1}{2}e^{-r^2}\right|_0^\infty \right) \\
&= 2\pi (\frac{1}{2})\\
&= \pi
\end{aligned}
$$

Thus $I=\sqrt{\pi}$, so $\frac{1}{\sqrt{\pi}}\int_{-\infty}^{\infty} e^{-x^2} dx=1$ and we can take the pdf to be

$$f(t)= \frac{1}{\sqrt{\pi}}\int_{-\infty}^{t} e^{-x^2} dx$$