"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.

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.

Actually it seems logical to me.

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

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.