[pzhon]

I don't like the idea that explaining why always switching is equivalent to always not switching is a solution. It's not complete. As bigpooch mentioned in the other thread (and others have mentioned in past threads), you can do better than either always switching or always not switching. This should be added to the statement that you can't assume the conditional expectation is 1/2.

Choose a value t. If you see an amount less than t, switch. If you see an amount greater than t, don't switch. Conditioned on the case that both amounts are less than t, you break even compared with either always switching or never switching. Conditioned on the case that both amounts are greater than t, you break even again. However, if one amount is greater than t, and one amount is less than t, you always end up with the greater amount. If this happens with positive probability, switching with threshold t beats both the strategy of always switching and the strategy of never switching.

Instead of letting t be constant, you can let t be a positive real random variable with positive probability on each interval [x,2x]. Another way to describe this is that you switch probabalistically, with the probability of switching strictly lower at 2x than x, with limits of 0 and 1 as x goes to infinity and 0, respectively. This random threshold will have a positive probability of being between the two amounts no matter what distribution is chosen, and this will beat the strategy of always switching or never switching, even though you can't be sure by how much it will be better.

In fact, you can describe the strategy of always switching as using a threshold of +infinity, and you can describe the strategy of never switching as using a threshold of 0. You can see these thresholds have 0 probability of being between the amounts.

Mike Caro got this wrong, and the Wikipedia article doesn't mention that you can do better than either.