Last time I mentioned the paradoxical-sounding situation in which I said “pick a number at random under some given continuous probability distribution over the reals, and call this number ”. But what was the probability of choosing ? Well, a quick exercise shows that of course it would have to be zero. In measure theory this can be stated as: The event has Lebesgue (or probability) measure 0.

Ok, so there was no chance that I could have chosen and yet somehow I did? Whaaaaaaattt?!?

The answer is a good thing to know, but is also somewhat boring. There is just an abuse of terminology going on. We should always be relating things back to measurable events. So saying “ is between and with positive probability” really translates to “the event described by { : is between and } has positive measure.” And so although (as we will show) we do not lose anything by asserting that we have chosen an explicit and are comparing it to and , we are actually describing much larger events and waving our hands that they are the same.

So why is this abuse so prevalent? Anytime you make such a choice and work with it, such as by comparing to and , there are always more detailed events and probability spaces somewhere in the background. But when you use them explicitly then suddenly the problem becomes much less intuitive and far more difficult. (This example isn’t even as bad as many are.) So it is often easier and natural to ignore these “details”.

To make this explicit, below I typed out (somewhat thoroughly) what the very simple argument from last time would look like if you were really trying to make things analytically rigorous (=computationally annoying and boring). But, it is good for the soul to see this once before you forget it forever.

Let and be two probability distributions on and let be independent random variables such that and . For an explicit model let and be the identity map. Then the event that you win given the algorithm from last time is

So the goal is to estimate the probability

Using the obvious fact that we also have,

Now assuming that has a continuous distribution and using Fubini’s theorem we find,

Finally, if we assume that , which we did by our choice of probability distribution (e.g. the normal distribution works), then for all real and distinct and , we find that

So there you have it. Math lives another day. It is consistent and even much better to sweep these details under the rug. So for these standard abuses, just go ahead and do’em without thinkin and yall’ll be juuuust fine.

Pingback: Introduction to Randomized Algorithms; Part 1 | whateversuitsyourboat