Posted by: yanzhang | August 1, 2008

Here is another Matryoshka problem – well not really, since I can’t prove that the second problem is “strictly harder” than the first in any meaningful way, but it does have the property that the most intuitive trick needed to solve the first one fails on the second one:

Timothy Gowers posted a fairly classical “paradox” in probability involving two boxes:

original post

My analysis:

Note that the guy who gives you the box must pick (a, 2a) with equal probability for every a – i.e., he needs to be able to pick a real number uniformly. Unfortunately, this is impossible.

This is actually a common sleight of hand that many probability “paradoxes” use at some level. You can increase your “defense against probability paradoxes” by adding this to the list of things to check against every time you find a strange probability situation, in the same way that recognizing Russell’s Paradox counters many logic “paradoxes.”

Now the inner doll. Prof. Gowers attributes this one to Noga Alon:

These two problems are similar in spirit. However, the trick that works for the first one no longer works here: we have a very well-defined distribution! So we have to dig a little deeper. Here is my take:

In the paradox, we considered the random variable of the values of the two envelopes (call them $X$ and $Y$, and proceeded to divide the probability space into a series of sums x_i (where $\sum P(x_i) = 1$), seeing that $E(x_i|X)P(x_i) > E(x_i|Y) P(x_i)$ for all i. Then we did an implicit sum of all of these equations to conclude that $E(X) > E(Y)$.

The problem is in the sum – we cannot do this summation when the expectation of X and Y are infinite (we can easily check, by the way, that $E(X)$ and $E(Y)$ are both infinite), so we cannot conclude that one is larger than the other. Here is a clearer example: consider the list of inequalities $1 > 0$, $2 > 1$, $3 > 2$… each one of these statements is true, but it makes no sense to then argue that $1 + 2 + \ldots > 0 + 1 + 2 + \ldots = 1 + 2 + \ldots$, because the sums diverge and cannot be defined. If you track the list of inequalities in the problem, you will notice the exact analogous chicanery going on, just with different numbers.

The cool lesson form this M-2 pair is that I am reminded again to appreciate why math books always mention “boundary cases” like infinity and deal with them very carefully. Usually we see them as just stupid limitations for corner cases, but this is a case where not thinking about the clauses on these border cases can mislead (to be honest, I never remember these boundary cases, like the algebra theorems that hold for every ring except the zero ring).

By the way, I bet there is some way to turn each one of these into a “paradox” in their respective fields. Probability is just riper for these conundrums since the problems offer more intuitive statements.

-Y

Source: Gowers’ Weblog