I have mentioned USENET before in these pages. By way of reminder, USENET is the world's largest network of computers; USENET email connects several million people with an average tmnsniission delay of 8 hours; USENET news contains several million characters per day and covers hundreds of topics; USENET is totally anarchic.
I maintain a USENET rec.puzzles Frequently Asked Questions List (FAQL). Rec.puzzles is the USENIET news group for recreational puzzles. As might be expected, puzzles come in waves, with certain topics becoming fashionable. For example, the Monty Hall problem was big on the net at the same time Marilyn was getting all her publicity with the problem.
Recently, the classic "two envelope" problem has been hot:
I show you two sealed envelopes and say that one envelope has x dollars and the other has 2x but don't say what x is. It is not possible to determine which envelope has the larger amount without opening them. I hand you one envelope (at random - whatever that means) and say that you have two options:
(1) Open the envelope that you have and keep whatever you find.
(2) Exchange envelopes with me, open the envelope that you receive from the exchange, and keep the amount you find. End of game.
You analyze: I have an unknown amount y in my hand. If I exchange I get y/2 or 2y with equal probability. The expected value of the exchange is (1/2)((y/2) + (2y)) or 1.25y. Expected value from not exchanging is y. Therefore it is better to exchange.
T'his is clearly wrong. What is wrong? It is not sufficient to answer that the right analysis is something else. The question is what is wrong with the above.
Let's follow the argument carefully, substituting real numbers for variables, to see where we went wrong. In the following, we will assume the envelopes contain $100 and $200. We will consider the two equally likely cases separately, then average the results.
First, take the case that y=$100.
"I have $100 in my hand. If I exchange I get $200. The value of the exchange is $200. The value from not exchanging is $100. Therefore, I gain $100 by exchanging."
Second, take the case that y=$200.
"I have $200 in my hand. If I exchange I get $100. The value of the exchange is $100. The value from not exchanging is $200. Therefore, I lose $100 by exchanging."
Now, averaging the two cases, I see that the expected gain is zero.
So where is the slip up? In one case, switching gets y/2 ($100), in the other case, switching gets 2y ($200), but y is different in the two cases, and I can't simply average the two different y's to get 1.25y. I can average the two numbers ($100 and $200) to get $150, the expected value of switching, which is also the expected value of not switching, but I cannot under any circumstances average y/2 and 2y.
However, a lot of people simply do not relate to this answer. They want an answer involving the probability density function (pdf) of the amount in the envelope. Consider the following solution submitted by Richard Harter:
Let us suppose, per the problem, that we draw a sample L using a given pdf. We place in one envelope the amount $L and in a second $2L. One of the envelopes is picked at random (with selection probabilities of .5) and is opened to reveal that it contains $x. What is the expected value of the other envelope?
Now, given the above information, the other envelope contains either $X/2 or $2x. In the first case L was x/2; in the second it was L. Let d(L) be the pdf in question. Then the probabilities are:
Pr(L=x/2) = d(x/2)/(d(x) + d(x/2)) Pr(L=x) = d(x)/(d(x) + d(x/2))
According the expectation of the contents of the other envelope is
E(other) = Pr(L=x/2)*($x/2) + Pr(L=x)*($x)
And the expected gain from switching is
E(switch) = Pr(L=x)*x - Pr(L=x/2)*(x/2)
Now comes the switcheroo. We do not know what these probabilities are because we do not know what the pdf is. However we do know that the mean of these probabilities is each 1/2. (Follows from condition of the problem.) So we argue that we can replace the unknown probabilities by their means to get
E(switch) = .5*$x - .5*$(x/2) =.25*$x.
Conclusion 1: In any particular instance the claim is not valid because the probabilities for L, although unknown, are not 50%. The observation that the chosen envelope contains $x gives us information, even though we do not know what the information was.
But why is it not correct, on average, to replace the unknown probabilities by their mean values? To do so amounts to the claim that
Mean(Eswitch) = Mean (Pr(L=x)*x) - Mean(Pr(L=x/2)*(x/2))
= Mean(Pr(L--x))*Mean(x) - Mean(Pr(L=x/2)*Mean(x/2)
= .5*Mean(x) -.5*Mean(x/2)
= .25*Mean(x)
The error lies in the second step where the mean of a product is replaced by the product of means.
Conclusion 2: The claim [is] in error on average because it makes the implicit assumption that the mean of a product is the product of means.
Remark: There are a number of interesting results associated with this problem. For example, for a given pdf, there is a number x0 such that it pays to switch if the sample x is less than x0 and not switch if it is greater. For extra credit determine whether x0 is always less than the mean of the pdf, greater than the mean, or dependent on the particular pdf.
As a result of these discussions, I have come to the conclusion that the envelope problem is really four problems rolled into one. Let's consider the cases:
1. You do not know the probability density function (pdf) of the envelope values nor your particular envelope value. Clearly in this case it is irrational to switch, because you have not sampled the envelope and have nothing to go on to decide if the other envelope is likely to be more.
2. You do know the envelope pdf, but not the current contents. Without sampling the envelope, any knowledge about the pdf is useless. After all, what can the pdf tell you about whether you chose the larger or smaller value?
3. You do get to look into the envelope, but you do not know the pdf of the envelope values. You cannot decide whether to switch, because some pdf's would tell you to switch and some would not, and you don't know which kind of pdf you are looking at. You could perhaps perform a lot of experiments to try to estimate the pdf, but on the first try you don't know enough to conclude anything.
4. You do get to look into the envelope and you do know the pdf of the envelope values. Then you can compute an optimal strategy for switching. For example, suppose the envelopes contain $100 and $200. If yours contains $100, you should switch. Otherwise, not.