# "A two-envelopes puzzle"

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.

• Well... they can't be independently generated since they aren't allowed to be equal. Regardless, I agree with the book's solution. Make yourself a tree diagram and remember that your original selection is equally likely to be the larger envelope as it is the smaller envelope and recognize that the chance to swap is different for each. May 15, 2017 at 18:57
• This wikipedia article should provide a good deal more information to a slightly altered problem. The main point to take away from it is that the chance to switch is dependent (not independent) on the amount of money in the envelope you looked in. "Tossing a coin has nothing to do with the contents of the envelopes" but answering whether you tossed more times than the amount in the envelope does have something to do with the contents. May 15, 2017 at 19:06
• I've seen this one where the person handing you the envelopes is an intelligent adversary who knows the algorithm you are going to use and is permitted to manipulate the numbers and the order of the envelopes to try to cause you as much trouble as possible. The technique still works. May 15, 2017 at 20:40
• The only reason why counting the leaves on a nearby tree might not work just as well as the coin tossing is if we think it is possible that there is some number $N$ such that the amount in either envelope can never be less than $N$ but the tree cannot have $N$ or more leaves. In that case the answer doesn't work. The advantage of coin tossing is there is no $N$ such that the number of tosses cannot be $N$ or more. May 15, 2017 at 21:57
• @JMoravitz: I think this is actually closer to the dowry problem than the two-envelopes problem. en.wikipedia.org/wiki/Secretary_problem May 15, 2017 at 23:17

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.

• I think you can "generate $X$ any way you want" just as long as the support of the distribution of $X$ is enough to justify the assumption that one number could be below $X$ and the other above $X$. The coin tosses give a support that includes $n+\frac12$ for every positive integer $n,$ which is sufficient. I believe it is OK for the support to have larger gaps than that, but not for it to be bounded. May 15, 2017 at 22:02
• @DavidK: if it has larger gaps than that and the person filling the envelopes knows your strategy he can leave you with just a $\frac 12$ chance. If there is no chance $2 \lt X \lt 3$ he could put $2$ and $3$ in the envelopes. A bounded distribution works the same way. He could just put two numbers above the bound. May 16, 2017 at 1:26
• My mistake was that I thought this was the two-envelope problem in which one envelope contains twice as much money as the other. Re-reading the question, I see that the amounts are merely required to be two different integers, so the support of $X$ must include one number between each pair of positive integers. May 16, 2017 at 1:32
• @anonuser01: no, it does not except to rely on the fact that they are different, which we are given. We just need a positive probability of generating a number between any pair of positive integers. May 2, 2021 at 16:32
• I think the best way to think about it is what I said last comment. If $X$ is outside $(a,b)$ you make a random selection and win with probability $\frac 12$. If $X$ is inside you win all the time. The $0.5+0.5P(B)$ spends half of the $1$ for being inside to complete the leading $0.5$, then has $0.5P(B)$ left over so shows that. May 3, 2021 at 1:51

Actually it seems logical to me.

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

• This is a good way to understand the result. Any algorithm that results in a higher probability that you will change envelopes if you have the envelope with the smaller amount in it will increase your expected return. May 15, 2017 at 21:06

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.

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.

• If the amounts in the envelopes are chosen by the same coin tossing algorithm, then $P(a,b)=\frac{3\,[0\lt a\lt b]}{2^{a+b}}$, and this strategy raises the expected value from $\frac73$ to $3$, which is pretty good since the average high envelope is $\frac{10}3$.
– robjohn
Jan 30, 2020 at 11:54

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!!!

• What are A,B, C, W here?
– 24n8
May 2, 2021 at 17:09

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.