“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. – JMoravitz May 15 '17 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. – JMoravitz May 15 '17 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. – Cort Ammon May 15 '17 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. – David K May 15 '17 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 – Eric Lippert May 15 '17 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. – David K May 15 '17 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. – Ross Millikan May 16 '17 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. – David K May 16 '17 at 1:32
• @DavidK: I have added a bit to clarify. Thanks. – Ross Millikan May 16 '17 at 2:16

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. – David Schwartz May 15 '17 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.