Keep The Right One

Alright, time to finish off the stuff I've been writing about the two envelope paradox. The analysis last time showed that we had best assume that the smaller cheque is coming from a normalized distribution function P(x) with a finite expectation value (∫ xP(x)dx converges). Now, we must come up with a strategy on wether to keep the cheque or not, and this strategy can only be based on the value of the cheque that we see (known as A). Let us choose to accept the switch when cheque A has a value x with probability S(x). S(x) must be a function from the positive reals to [0,1], but is otherwise arbitrary. Now, we know that the expected gain from switching is E(B|A=x)-x (from last time), times Q(x)=(P(x)+P(x/2)/2)/2 (the distribution function on the cheque A), times S(x) (the chance we actually take the switch). So, the expected gain is
∫(E(B|A=x)-x) Q(x) S(x) dx
=1/2 ∫(xP(x)-x/4P(x/2))S(x) dx
=1/2 ∫xP(x)S(x)dx-1/2∫x/2P(x/2)S(x)d(x/2)

The split into two integrals is valid this time as ∫ xP(x)dx converges and the bounded function S(x) is not going to make that any worse. Now, change variables x/2 -> x in the second integral and recombine to get
=1/2∫xP(x)(S(x)-S(2x))dx

So we see that as long as S(x)-S(2x) is positive, we will have a positive expected gain for any distribution function P(x). Specifically you may choose any decreasing function to get this effect, like S(x)=1-tanh(x). In effect, this means that you are more likely to keep a larger valued cheque than a smaller cheque. This sort of solution also solves a similar game where I write down any two random numbers (from some probability distribution) on cheques and offer you a "keep or switch" scenario.

Anyway, one can also find that the optimal choice of S(x) is to set it to 1 whenever P(x)-1/4P(x/2)>0 and 0 whenever P(x)-1/4P(x/2)<0 (when P(x)-1/4P(x/2)=0, choose S(x) arbitrarily, it doesn't matter), however this assumes that you know the function P.

Wanting Too Much

Alright, time to go into a bit of detail about the two envelope paradox. Much of this analysis I actually originally read on a paper by David Chalmers. Anyway, the first thing to realize is that this paradox can show up even if the amount of money in the first envelope is taken from a well defined probability distribution. That is, suppose the smaller cheque has value between x and x+dx with probability P(x)dx, and the larger cheque is exactly twice the smaller one. Now, we have to ask the following thing: given that we have opened an envelope with value between y and y+dy, what are the odds that it is the smaller cheque? Well, if it is the smaller cheque, then there was a P(y)dy chance of it being written down, but if it is the larger cheque, then there was a P(y/2)d(y/2)=1/2 P(y/2)dy chance of it happening. Thus the ratio of probabilities is 2P(y):P(y/2), though one might naively have expected P(y):P(y/2). In particular, if the first cheque is randomly chosen from 0 to 10 with uniform distribution, and you see a cheque of value 2, then it is twice as likely that the other cheque has 4 than it has 1. This may seem nonintuitive, but this must occur in order to balance out the case that if you see a cheque with value over 10 and then the other cheque must be smaller. Note that this actually will make the initial paradox somewhat worse.
Now we can see that if the distribution function for the smaller cheque is P(x), then the distribution function for a random cheque will be Q(x)=(P(x)+P(x/2)/2)/2. The relative ratio between the two terms was derived last paragraph, and the overall factor of 1/2 comes from normalizing Q(x) assuming P(x) already was properly normalized. Let the first cheque be given a value A and the unknown cheque a value B (B=2A or B=A/2 always). Let E() be the expectation value operator, so that E(B) denotes the expectation value of B, and E(B|A=x) will denote the expectation value of B given that A is the specific value x. The paradox will be at its strongest if E(B|A=x) is greater than x for all values of x (and the paradox will still exist if that had been true on average). Now lets calculate how much money we expect to get by switching blindly without even looking at the value of the first cheque by integrating over the distribution function for the first cheque Q(A). The specific value of E(B|A=x) is (2xP(x)+x/2P(x/2)/2)/(P(x)+P(x/2)/2) being (value if B is larger)(chance B is larger)+(value if B is smaller)(chance B is smaller) divided by normalization, so E(B|A=x) = x/2(8P(x)+P(x/2))/(2P(x)+P(x/2)). Now, the expected gain for switching cheques blindly is:
∫ (E(B|A=x)-x) Q(x)dx
=∫ (x/2(8P(x)+P(x/2))/(2P(x)+P(x/2))-x)(2P(x)+P(x/2))/4 dx
=∫ (x(4P(x)+P(x/2)/2-2P(x)-P(x/2))/4) dx
=1/2 ∫ (xP(x)-x/4P(x/2)) dx

Next is the trick that I really appreciate about this entire thing, assuming that the integral ∫ xP(x) dx converges, we may break this up into two integrals to find
=1/2 ∫ xP(x)dx-1/2 ∫ x/2P(x/2)d(x/2)

Which is simply zero. Note that if P(x) was something like 1/x^2 from 1 to infinity, it will be a properly normalized distribution function, but the paradox will still arise. In order to avoid the paradox, the first cheque needs to have a finite expectation value, otherwise the paradox that E(B) is greater than E(A) isn't really a problem.
More simply put, given infinite expectations, any finite value is disappointing.
Anyway, back to the puzzle I posted last time, you may further assume that the distribution function that the cheques are chosen from have finite expectation value, there is still a strategy that works.

Two Envelopes

So, this time I have a logic puzzle wrapped in a paradox. I'll introduce the paradox first, then the puzzle, then sometime over the next few weeks I'll resolve the paradox. Here is the setup:
A rich man has decided to give away some money to you. He selects a number, and writes a cheque for that amount of money and puts it in an envelope. Then he writes a cheque for twice as much money and puts that in another envelope. He shuffles up the envelopes and hands one to you. You look inside and see $100. Then he offers you the chance to switch envelopes. You know that you got the smaller or larger envelope with 50/50 chance, and the other envelope contains either $200 or $50, thus on average it has $125, therefore, you should switch. However, you can reach the conclusion that you should switch without even looking in the first envelope, as the other envelope contains 5/4 times as much, on average.

Clearly something is wrong here, one can find some time exploring to find out what the deal is. It basically comes down to the problem of saying "he selects a number", you cannot select a random real number without specifying a probability distribution. I'll go more into that later, but for now:
Assuming the initial amount of money is selected from a well defined (but unknown) probability distribution, there is a strategy that guarantees more money than one would get by just simply keeping the first envelope or by just switching blindly. What is the strategy?

Certainly the strategy must work for any choice of probability distribution, its sort of neat to know that it can exist.