Finding Coins

Alright, time to finish off the envelope puzzle from last time. This post is going to wind up getting into Bayes' theorem, which has never come up before in my blogging, to my surprise. I suppose I might as well also give a little proof and statment of Bayes' theorem while I'm at it, since its sort of cool.

First though, I want to explicitly demonstrate the solution to the follow-up problem of last time, then I will give a more general derivation using Bayes' theorem. The first thing to remember here, and the general theme of this post actually, is that Bob gained information when he selected a random envelope and found a coin. The explicit two envelope solution of last time served as a good example of this, but it is important enough that I want it stated explicitly. When Bob found a coin in a random envelope, he has to reevaluate his stance on how Alice put coins in envelopes. At first he thought it was 50-50 of zero or two coins, but after finding one, he knew there were two and not zero.

So, I'm going to just give the answer to the follow-up puzzle and then show that it is, in fact, an answer (I will later show that it is 'the' answer). It is for N=4 the scenario is consistent. Before opening an envelope, the cases k=0,1,2,3,4 are all equally likely, and so the expectation of a random envelope is 1/5(0/4)+1/5(1/4)+1/5(2/4)+1/5(3/4)+1/5(4/4)=1/2. A random envelope is worth $1/2, not very surprising. Next, when Bob finds a coin, he knows that k=0 is impossible, and if k had been 1 there would have been only a 1/4 chance of finding a coin, while if k was 4 he was certian, thus it is 4 times more likely that k=4 than k=1. Thus, Bob thinks the values k=0,1,2,3,4 have the relative likleyhoods of 0:1:2:3:4, meaning k=0 has probablity 0, k=1 probablity 1/10, k=2 probability 2/10, k=3 probability 3/10 and k=4 probability 4/10. for a given k, now that a coin has been removed, the expectation value of an envelope is (k-1)/4, so a random envelope now has expectation value 0/4(1/10)+1/4(2/10)+2/4(3/10)+3/4(4/10)=1/2. So we can see N=4 is a solution.

To prove N=4 is the only solution, and to sort of derive it in the first place, we need Bayes' theorem. Suppose we have some an experiment that we are doing, and there are events that can occur, call the events A,B,C... and so on. Now, we can talk about the probabilty of an event A, we call that P(A), and we can talk about the probabilty of an event A given that some other event B has occured, we call that P(A|B). We can of course talk about the probablity that both A and B occur, P(A and B) and such things. It can be seen that the probabilty that both A and B occur is equal to the probabilty that A occurs times the probabilty that B occurs given that A already occured, so we can say:

P(A and B)=P(A)P(B|A)

Of course I could switch A and B in that statement to get:

P(A and B)=P(B)P(A|B)

Giving us that

P(A|B)P(B)=P(B|A)P(A)
P(A|B)=P(B|A)P(A)/P(B)

This last line is the statement of Bayes' Theorem.

So, this theorem can be used to tell us how likely is was that 'Alice put k coins in the envelopes' given that 'Bob found one at random' as long as we can calculate the chance that 'Bob found one at random' given that 'Alice put k coins in the envelopes'. That second one sounds pretty easy to calculate. This is the use of Bayes' theorem, it allows us to switch the order of conditionals which can often make it easier to calculate.

In most practical cases, we have a list of mutually exclusive events A_i and another list of mutually exclusive events B_i such that exactly one A_i and one B_i must occur. Of course, for particular i and j, we can read off Bayes' theorem as:

P(A_i|B_j)=P(B_j|A_i)P(A_i)/P(B_j)

and to find P(B_j) we can find P(B_j|A_k) for each k and then multiply by P(A_k) and sum over k. Essentially we can see that in this case the denominator is serving as a normalizing constant (constant for each choice of j, that is) and that summing both sides of that last equation with resepct to i will give 1 (since exactly one of the A_i must happen).

Now lets try to use Bayes' theorem to solve the follow-up problem. Alice has N envelopes, placed coins in k of them, Bob found a coin. So for our purposes let the event A_i be 'Alice placed coins in exactly i envelopes', and the events B₀ and B₁ are 'Bob didn't find a coin' and 'Bob found a coin', respectively. So we have

P(A_i|B₁)=P(B₁|A_i)P(A_i)/P(B₁)

P(B₁|A_i) is easy, its i/N, and P(A_i) is just 1/(N+1). P(B₁), the chance Bob found a coin, is the numerator summed over i, it is Σ i/(N(N+1)), which is just 1/2. So we have

P(A_i|B₁)=2i/(N(N+1))

Now, what is the expectation value of an envelope given that Bob found and then removed a coin? It is

Σ (i-1)/N 2i/(N(N+1))

Which is the chance of finding one of the remaining i-1 coins time the chance there were i coins (given that Bob found one) summed over i. We can rewrite this as

2/(N²(N+1))Σ (i²-i)

That sum evaluates to N³/3-N/3, so we now have

2(N-1)/3N

as the expectation value of a random envelope given that Bob has found a coin. If we set this to 1/2 we get N=4. Somewhat interesting is that in the limit of large N this tends to 2/3, so which is the statement that Bob pushes his expectation of a random envelope upward quite a bit if he found a coin, when N is large the act of removing one is pretty harmless, he probably won't pick that envelope again anyway.

Alright, that was fun, and in my mind was the end of the puzzle, however, in the comments of the initial post somebody showed me that you can classify all the solutions to the puzzle, so lets do that now (because its actually really cool).

First, note that the list of probabilites P(A_i) completely specifies Alices strategy. Once she has placed coins in the envelopes and shuffles them, the only information that matters is how many envelopes have coins in them. She can use whatever method she wants to place coins, but she might as well just whisper to Bob the list P(A_i), that is the only thing that matters. Alright, so we have already seen that

P(A_i|B₁)=P(B₁|A_i)P(A_i)/P(B₁)

P(B₁|A_i) is still i/N, but now P(A_i) is encapsulating Alices strategy. P(B₁) is still the sum of the numerator, that is

P(B₁)=Σ i/N P(A_i)

Actually, thats the average value of the number of envelopes that Alice put coins in divided by N (sort of obviously), we will call this K/N.

So we have

P(A_i|B₁)=i P(A_i)/K

Alright, after having found a coin, the expectation value of a random envelope is now (i-1)/N times the chance there are i coins, summed over i, so that is

Σ (i-1) i P(A_i)/(K N)

If we want this to be equal to the expectation of an envelope before Bob selected one the first time, we must set this equal to K/N, meaning we now have

K²=Σ (i-1) i P(A_i)
=Σ i² P(A_i) - Σ i P(A_i)

That second term on the right is just K and the first term on the right is the expectation of the number of coins in envelopes, squared. Some rearranging gives us

K=Σ i² P(A_i)-K²

The right side is the expectation of coins squared minus the expectation of coins, squared. This is the standard deviation of Alices strategy squared. So a strategy for Alice is a solution to this puzzle if and only if: the expectation value of the number of coins Alice places in envelopes is equal to the standard deviation squared of the number of coins Alice places in envelopes. Neat.

You can confirm explicitly that the 50-50, 0,2 strategy and the 0,1,2,3,4 strategy both have this feature. Anyway, thats basically it for this.

Half And Half

So, I wasn't sure if I should put up a complete solution to the envelope puzzle from last time or just post a partial solution and have follow-up questions, but I have since decided on the latter.

Anyway, a solution to the puzzle (which was also given in the comments, but was my "intended easy solution") is: Alice has two envelopes and flips a coin, filling both envelopes with coins on heads and neither of them on tails. With this, the expected value of a random envelope is $1/2. After Bob finds a removes a coin he knows for a fact the other envelope has a coin, so the expected value of an envelope is again $1/2.

Next a follow-up problem:

Suppose instead of Alice whispering her strategy, you overheard her say "I selected an integer k from 0 to N uniformly at random and placed coins in k of the envelopes." What is the value of N so that the scenario is possible?

Its funny how our brains can work, I was again convinced that this was just impossible, even after knowing the earlier answer, but there is a way to solve this. It even has a unique answer.

Random Envelopes

So, apparently I misread that snake puzzle from last time, the intention was to get to a position where there is only one type of snake, rather than one where there are equal numbers of all snakes. The solution is basically the same, but the "brute force" method of applying AⁿB^mC^k is slightly less effective, since you must prove that you cannot reach any of 45-0-0, 0-45-0, 0-0-45, so hitting on the mod 3 solution is more needed.

Anyway, I found a new puzzle on the xkcd forums, I thought it was sort of cool:

Alice and Bob are having a conversation that you are overhearing. Alice has a collection of N envelopes and says to Bob, "for each of these envelopes, it contains either a dollar coin or nothing, I chose to fill the envelopes at random, what is the expected value of the contents of a random envelope?"

Bob responds, "It depends on the method you used to decide to fill the envelopes. You could have flipped a coin for each one, filling it if you got heads and not if you got tails, in that case the expected value of an envelope is $1/2."

Alice decides to tell Bob the method she used to fill the envelopes, she whispers it to him. "I see," Bob replies, "I will purchase a random envelope from you for the expected monetary value, then." Alice agrees, Bob hands her some money and selects an envelope. Bob finds that the envelope does contain a coin and pockets it.

Alice takes the now-empty envelope from Bob and shuffles it back in with the other envelopes. Alice says to Bob, "what is the expected value of a random envelope now?" To which Bob replies, "it is the same as before my purchase."

What is a possible value for N and random method that Alice could have used to make this scenario possible?

When I first read this puzzle, I was certain it was impossible. There is no way that Bob could have taken a coin away and not changed the expected value of a random envelope. However I was missing something. Obviously not something stupid like "Bob can see which envelope he opened earlier because it is now torn" or something like that, that would hardly make an interesting puzzle. There is a well-defined method that Alice can use to make it so that after Bob finds and removes a coin the expected value of a random envelope has not changed.

There are actually many possible solutions, so when I do post the solution next time it will by no means be a complete listing of all possibilities (there are far too many), try to see if you can come up with at least one possible solution though.

Alice Wins?

I guess I should put up the solution to the second two numbers problem. The fact that I ask for an equilibrium strategy sort of gives something away I suppose, because in the first one there is no equilibrium strategy (Alice can make Bobs winning chance 1/2+ε for any positive ε so there is no optimal one). To begin, what is the strategy space for Bob? Bob sees a number, x, and must decide if that number is larger or smaller based simply on that number. All Bob can do is select a function f(x) to give him the probability that he says x is the larger number. The solution to the last puzzle strongly suggests that f(x) should be a strictly increasing function, but it is worth noting that if f(x) is simply 1/2 everywhere, then Bob is certain to get 50% on this game, so there is no way Alice can push him lower than that.

Suppose Alice is given f(x) (Bobs strategy) and is given the two numbers y and z from (0,1) (also, we may as well assume z>y). Now, if Alice chooses to show Bob y, Bob has a 1-f(y) chance to win, and if Alice chooses to show z, Bob has a f(z) chance to win. Thus Bobs chance to win (if Alice knows f(x)) is given as:

min(1-f(y),f(z))

Now we must integrate this over all space of y and z. The natural integral would be ∫ ∫ dy dz with both going over (0,1), but this does not work because we have already assumed z is the larger of the two numbers. We should simply restrict the integral to z ∈ (0,1) and y ∈ (0,z) and multiply by 2 to take care of the other half of the region where y happens to be larger. Bobs chance to win is given as

2 ∫ ∫ min(1-f(y),f(z)) dy dz

with y from 0 to z and z from 0 to 1.

The next thing to know is that Bob is trying to maximize this integral. We must select an f(x) to make this as large as possible. Remember we already know that with f(x)=1/2, we trivially get 1/2 for the answer, so really we need only ask if we can make it larger than 1/2. You can try some functions out for a while, but in the end you will see that nothing will integrate to more than 1/2.

We can prove that Bob cannot get better than 1/2 by using 2 features about the min and max functions:

1.min(a,b)+max(a,b)=a+b
2.min(a,b) ≤ max(a,b)

Now we define

P=2 ∫ ∫ min(1-f(y),f(z)) dy dz
Q=2 ∫ ∫ max(1-f(y),f(z)) dy dz

integrated over y from 0 to z and z from 0 to 1 as before. We seek to prove that P ≤ 1/2 for all choices of f.

Fact 2 from before shows us right away that P ≤ Q, and fact 1 gives us

P+Q=2 ∫ ∫ (1-f(y)+f(z)) dy dz
=2 (∫ ∫ 1 dy dz - ∫ ∫ f(y) dy dz + ∫ ∫ f(z) dy dz)

The first integral is simply 1/2 (the area of integration) and in the third integral you can do the y integral separately to get ∫ zf(z) dz integrated from 0 to 1. For the second integral we simply rewrite the integration region from y ∈ (0,z) and z ∈ (0,1) to z ∈ (y,1) and y ∈ (0,1) so we can do the z integral first to get ∫ (1-y)f(y) dy integrated from 0 to 1. We currently have

P+Q=1 - ∫ (1-y)f(y)dy + ∫ zf(z)dz

But using the substitution z=1-y the two integrals are trivially identical for any f(x). Therefore,

P+Q=1

Now since P ≤ Q we have (by adding P to both sides) 2P ≤ P+Q so 2P ≤ 1 therefore P ≤ 1/2 as we sought.

OK great, so if Alice knows Bobs f(x), there is no way Bob can choose an f(x) that guarantees to get any better than 1/2. So if there is an equilibrium strategy, it must be 50/50. But is there one? Can we construct a strategy for Alice that makes sure Bob cannot get better than 1/2 even if we have no idea what f(x) he chose? We can, and its actually what one would instinctively do if one were playing this game.

Consider you are Alice and you are handed the numbers 0.1 and 0.5, which one would you show Bob? The obvious choice is 0.5, 0.1 looks too obviously the low one. How about 0.8 and 0.4? Less obvious, but it would seem the rational guess is 0.4. How about 0.7 and 0.4? again 0.4, 0.7 has less space above it than 0.4 has below it. How about 0.8 and 0.6? 0.6 is pretty clearly better. How about 0.7 and 0.3? now it seems they are symmetric, no good way to choose. How about 0.6 and 0.4? again symmetric.

See what the strategy is? Just show Bob whichever number happens to be closest to 0.5. Now, if we obey this strategy, what is Bobs chance of winning? First let us rescale the numbers down by 0.5 so that the two numbers, y and z, range from -1/2 to 1/2 and we show Bob whichever one is closer to zero.

Consider the y-z plane in the box y ∈ (-1/2,1/2) z ∈ (-1/2,1/2). The numbers we get select a point in this region. Which number is y and which is z doesn't matter here, select which is which at random.

Divide up the region into 4 pieces using the lines y=z (from bottom left to top right) and the line y=-z (from top left to bottom right). The 4 regions are "top" (where z>0 and y is between -z and z) "bottom" (where z<0 -y="" -z="" and="" between="" is="" left="" right="" where="" y="" z="">0 and z is between -y and y). If our two numbers put the point in either "top" or "bottom" we show Bob y. If the point is in "left" or "right", we show Bob z.

Suppose we have a point in "top". We show Bob y and he has to guess that y is the smaller number. The chance of him doing so is 1-f(y). For all points in "top", we would integrate this to get the total probability of Bob winning, given a point in "top". That is, when the point lands in "top", Bobs chance of winning is ∫ 1-f(y) integrated over "top". In "bottom" we show Bob y and he must guess it is the larger number. He does this with probability f(y) so, 1/4 of the time, Bobs chance of winning is ∫ f(y) integrated over "bottom". Note that ∫ f(y) in "top" is the same as ∫ f(y) in "bottom", since they both have the same y values.

Using the same argument for "left" and "right" we get Bobs chance of winning is (∫ 1-f(y) over "top")+(∫ f(y) over "bottom")+(∫ 1-f(z) over "right")+(∫ f(z) over "bottom"). The integrals of unknown functions all cancel, leaving ∫ 1 over "top"+∫ 1 over "bottom" giving 1/4 each (their areas) for a total of 1/2.

Simply put, if Alice shows Bob 0.3 (say), and Bob knows this number is the one that is closer to 1/2, then the other number is equally likely to be in (0,0.3) or (0.7,1) and Bob cannot tell those apart.

Thus if Alice follows the strategy "show Bob whichever number is closer to 1/2", then Bob cannot do better than 1/2 no matter what f(x) he chooses. If Bob uses the strategy f(x)=1/2 (so, "flip a coin") Bob cannot do worse than 1/2 no matter how Alice chooses the number to show. So this gives the equilibrium strategy (or, at least, an equilibrium strategy).

I find it funny that if you do this game with real people, the Alice player will probably typically hit on the correct strategy naively, even though they will then likely try to follow it up by "out-thinking" the other player, because thats just what humans do.

Two More Numbers

Alright, now that the two numbers puzzle is out of the way, time for the follow-up. I first learned this puzzle in a paper called "Games People Don't Play" which I found on the comments at the xkcd blag:

Two numbers are selected uniformly at random from the interval (0,1) and shown to Alice. Alice must select one of these two numbers and show it to Bob. Bob must then guess if Alice has shown him the larger of the two or the smaller of the two. What is the optimal (equilibrium) strategy for the players?

This time Alice does not get control of the two numbers, and Bob is aware of the distribution, but Alice gets to choose what number Bob sees, so who gains the advantage from those changes?

Only A Little

Time for the solution to the Two Numbers problem. I suppose I could just state the solution right away, but I like to do something of a derivation first.

First of all, consider the results of the following strategy for Bob:

If the number you see is greater than zero, guess it is larger, if the number is less than zero, guess it is smaller

Easy enough to implement, if both numbers that Alice wrote down are positive, then you are still 50/50. If they are both negative then you are again 50/50, but if one number was positive and one was negative, then you are guaranteed to win.

Alright, thats all well and good, naturally if Alice knows you are doing this, then she won't ever write down a positive and negative number together of course, so this is not actually guaranteed to give you a better than 50% chance of winning the game. Now, instead of greater than/less than zero, why not use a random number K. Perform the following strategy:

Select a nonzero probability distribution over the reals f(z). After Alice writes down the numbers, select a number K using f(z). If the number you see is greater than K guess it is the larger one, if the number you see is smaller than K then guess it is the smaller one.

By nonzero probability distribution I mean that f(z)>0 always and ∫f(z)dz = 1 when integrated over all the reals. Basically, the strategy is to assume that the unseen number is near K.

Suppose Alice writes down x and y with y>x, then if x>K or K>y you are simply 50/50, but if y>K>x you win the game 100%. The chance of you winning is therefore

∫f(z)dz+(1-∫f(z)dz)1/2
=1/2+1/2∫f(z)dz

Where the integral is between x and y (giving the chance K lands between x and y). Since f(z)>0 always, this is greater than 1/2 in all cases and is a valid solution. Naturally, if Alice knows f(z), she can make that integral as small as she likes, but she cannot make it non positive.

One can make a slightly more general (but not actually any better) solution as well. Consider that Bob looks at the number before choosing K. Then the chance that K will be less than x (and thus guess x is larger) is ∫f(z)dz integrated from -∞ to x. Let p(x) be that number (the probability that we say x is larger). Clearly we have p(x) positive, increasing, and 0 at -∞ and 1 at +∞.

Let Alice choose number x and y with y>x. Now the chance Bob wins given some function p(x) is 1/2 (the chance he is given y) times p(y) (the chance he says y is larger) plus 1/2 (the chance he is given x) times 1-p(x) (the chance he says x is smaller). thus giving

1/2 p(y)+1/2(1-p(x))
=1/2+1/2(p(y)-p(x))

Not surprising given that p is the integral of f from before.

Anyway, the only thing that we need to demand of p(x) is that is be strictly increasing and bounded between 0 and 1. It does not matter that it goes to 0 at -∞ or 1 at +∞ (though, I guess it might as well). So the strategy of saying the number you see, x, is greater with probability p(x) is more general than the strategy of picking K from f(x) (though not any better, even if it is more general). Again, given p(x) Alice has the power to make p(y)-p(x) as small as she wants, but she can never stop it from being positive.

Two Numbers

So, about a year ago, I posted a puzzle based on the two envelope paradox. I had intended to finish that one off with another puzzle, but then I guess I forgot to. Now I have learned about a follow up to that puzzle, but I can't exactly post i until I have posted the original. Anyway, here we go:

Alice writes down two distinct real numbers and puts them into two separate envelopes. Bob then selects one of the envelopes to open randomly (50-50 chance) and looks at the number. Bob must then guess whether the number he is looking at is the larger of the two or the smaller of the two. Find a strategy for Bob that is guaranteed to succeed more than 50% of the time, no matter what numbers Alice chooses.

Its very similar to the final problem I posted a year ago, so I'll give the solution out in the next few days so we can move on to the real problem. Its trivial for Bob to do 50% simply by flipping a coin to decide his answer, but doing better just seems crazy. If you need, feel free to assume Alice is choosing her numbers from an unknown but well defined distribution over the reals.

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.