Ugly Subsets: Weirdness Within the Axioms of Probability Theory

I'm watching this video now, and at $36:53$ John Tsitsiklis mentions that for some sets there is no way to assign probabilities to events which occur in them. I'm wondering what sets he is talking about. Tsitsiklis says that one will only encounter them doing doctoral work, but I imagine that the "theoretical aspects of probability theory" are more tangible than Tsitsiklis makes them out to be.

-
Well shouldn't be all events in your $\sigma$-Algebra whenever you talk about probalities? I don't know if he really is talking about non measurable sets because I guess if you have events that are not in your $\sigma$-algebra you failed to model your problem correctly –  Dominic Michaelis Aug 21 '13 at 4:24
Fortunately JT does not use the word "event" for these sets since "event" means "subset to which one can (and does) assign a probability". –  Did Aug 21 '13 at 6:12

The question is what does it mean to be tangible.

The sets that Tsitsiklis mentions are "non measurable sets" and they exist as a consequence of the axiom of choice. However it is consistent with the failure of the axiom of choice that no such set exists, and that we can - in fact - assign probabilities to all the subsets of the real line/plane/etc.

Example for such sets are:

1. Vitali sets (inverse function for $\Bbb R/G$ where $G$ is a dense subgroup, e.g. $\Bbb Q$).
2. Ultrafilters (we can encode subsets of $\Bbb N$ as real numbers, and then ultrafilters over $\Bbb N$ are subsets of $\Bbb R$. Many of those are non-measurable).
3. Discontinuous solutions to the Cauchy functional equations (discontinuous solutions to $f(x+y)=f(x)+f(y)$).

And there are more.

-

The foundation for professional grade probability theory is measure theory. It turns out you can't coherently assign a notion of measure (length, area, volume, etc) to every subset of $\mathbb R$ (or $\mathbb R^n$ or most other spaces), so you make do with a subset of these sets. The class of measurable sets is still quite large, and the fact that you can't measure some sets doesn't pose any practical problems.