"A two-envelopes puzzle"

Question

This is Problem 1.25 from Tsitsiklis, Bertsekas, Introduction to Probability, 2nd edition.

You are handed two envelopes, and you know that each contains a positive integer dollar amount and that the two amounts are different. The values of these two amounts are modeled as constants that are unknown. Without knowing what the amounts are, you select at random one of the two envelopes, and after looking at the amount inside, you may switch envelopes if you wish. A friend claims that the following strategy will increase above $1/2$ your probability of ending up with the envelope with the larger amount:

Toss a coin repeatedly. Let $X$ be equal to $1/2$ plus the number of tosses required to obtain heads for the first time, and switch if the amount in the envelope you selected is less than the value of $X$ . Is your friend correct?

The answer given in the solution manual claims that this indeed helps, and that the probability of getting the better envelope is given by $$p = \frac{1}{2} + \frac{1}{2} P(B)$$

where $B$ is the event that $a<X<b$, with $a,b$ being the smaller and larger amount of dollars, respectively.

I do not buy this solution for the following reason: tossing a coin has nothing to do with the contents of the envelopes. You do not gain any information by doing it. You could just as well count the amount of leaves on a nearby tree instead and use that for $X$.

Similarly, opening the first envelope also gives you no useful information about the ordering relation between $a$ and $b$, so surely that's another red herring. Even if you forget the coin tossing, the probability of "winning" is still $1/2$, swap or no swap.

I suppose maybe the catch is in interpreting the following sentence: "The values of these two amounts are modeled as constants that are unknown". I take it to mean that they're just two randomly and independently generated numbers.

Am I out of my mind? Surely the solution manual is wrong.

Answer 1

The manual is right. The coin flips just generate the number $X$. If both envelopes contain numbers smaller than $X$, you have a random choice among the envelopes because you will take the second one. If both envelopes contain numbers greater than $X$, you have a random choice because you will take the first one. If one is greater than $X$ and the other is less, you will certainly pick the correct one, so if there is any probability this situation obtains you have a strictly greater than $\frac 12$ chance of picking the correct envelope. You can generate $X$ any way you want with the same effect as long as it has positive probability to be in each interval $(k,k+1)$. The argument tacitly assumes that it is possible one is below $X$ and one is above $X$. The reason to do the coin flipping is to get a distribution where all naturals plus $\frac 12$ have some chance to be chosen. This guarantees that there is some chance $X$ is between the two numbers.

Answer 2

Actually it seems logical to me.

The chance that you will change is larger for the wrong envelope.

Answer 3

So long as $X$ has a positive probability of being between the values in the two envelopes, it can help improve your decision making, by slightly biasing your decision upwards in the way indicated.

The coin toss version works since it has a positive probability of being in each gap between positive integers, no matter what are the distributions of the amounts in the two envelopes.

Your leaves on the tree idea might or might not help, as it runs the risk of being too high (you can already see there are lots of leaves, perhaps well in excess of the amounts in the envelopes) or of being too small (there is a limit to the the number of leaves), depending on the distributions of the amounts in the envelopes and of leaves on the tree. And you do not know those distributions.

Answer 4

This answer deals with a different two-envelope problem: the amount in one envelope is always double the amount in the other envelope. However, we can evaluate the strategy given in the solution manual in the same way that the strategy given in that answer was evaluated.

---

Let $P(a,b)$ be the probability that the lower amount is $a$ and the larger amount is $b$. Then $$ \sum_{1\le a\lt b}P(a,b)=1\tag1 $$ Picking an envelope at random, the expected value is $$ E=\sum_{1\le a\lt b}\frac{a+b}2P(a,b)\tag2 $$

---

Pick some $k$ and switch when the amount seen is less than $k+\frac12$. When $a\le k\lt b$, the expectation is $b$ instead of $\frac{a+b}2$; that is, an excess of $\frac{b-a}2$. This strategy increases the expected value by $$ \begin{align} \Delta(k) &=\sum_{1\le a\le k\lt b}\frac{b-a}2P(a,b)\\[3pt] &\ge0\tag3 \end{align} $$

---

If $P(a,b)=0$ when $a\le k\lt b$, then the strategy above does not help, but it does not hurt; that is, $\Delta(k)=0$. To guarantee an increase, we employ coin tosses. $(1)$ implies that for some $a\lt b$, we must have $P(a,b)\gt0$, and then for $a\le k\lt b$, $\Delta(k)\gt0$.

The probability that it takes $k$ tosses to obtain heads is $2^{-k}$. Therefore, by employing the coin tosses, we get an expected increase of $$ \sum_{k=1}^\infty2^{-k}\Delta(k)\gt0\tag4 $$ That is, the expected value increases.

Answer 5

I believe the other posts are correct when they say the solution manual is correct.

To address the other concerns about the tossing of a coin having nothing to do with the contents of the envelopes etc, I can offer this:

In the question, the friend suggests coin flipping. Instead of the coin flipping scenario, he could have suggested that if you get an envelope with one dollar in it, then change envelopes. This is always correct and will increase above 1/2 your probability of ending up with the envelope with the larger amount. I think this is all the coin tossing does.

Answer 6

Here's a technicality that explains why the coin toss method always works while choosing the number of leaves on a tree or always trading if your envelope contains one dollar won't necessarily work:

The amounts in the envelopes are taken from some unspecified range of numbers. Note that any number chosen within that range will increase the probability of winning.

The coin toss can, with some probability >0, choose a number in any possible range. Therefore, it always works.

The problem with choosing the number of leaves on a tree, or always trading when your envelope contains one dollar, or choosing a number using a variety of other methods, is that it doesn't guarantee that the number chosen will fall within the range that the amounts in the envelopes are taken from.

For example, if the chosen tree has 3,000 leaves and the range from which the amounts in the envelope are taken is from 4,000 to 100,000, then neither choosing the number of leaves nor trading when your envelope has one dollar will improve your chance of winning.

Answer 7

I agree with you @Spine Feast. Those lines in the solution manual applying the total probability theorem are not right. For example, it says

P(W|A) = $\frac{1}{2}$(P(W|notA) + P(W|A))

The above implies that P(A) = P(notA) = 1/2. The same logic applies for P(W|C), so

P(C) = P(notC) = 1/2.

With both equations above, and P(A) + P(B) + P(C) = 1, then

P(B) = 0

so

P(W) = 1/2

Which means no improvement at all!

The solution manual has fallen for the fallacy here!!!