Recitation of Apr. 30, 2013

We discussed Problem 10.11 on the Pigeonhole principe. This is the Dirichlet's original application. The same kind of proof (or a consequence of our proof) will lead to Dirichlet's approximation theorem which tells us that an irrational number can be approximated by a rational number whose denominator is not too large.

The statement of this approximation theorem as I wrote it on the board is wrong, I apologize for this. What you can say is that given a real number x and a natural number n, there is a rational approximation p / q to x with denominator q ≤ n (I wrote essentially q = n on the board), such that |p/q - x| ≤ 1/((n + 1)q). The statement of Problem 10.11 and its solution remains correct, of course.

We then went on to solve Problem 9.4 . There was a lot of confusion regarding the difference between saying A ∩ B = ∅ , and P(A ∩ B) = 0 . They are equivalent in the finite setting, but in general, the former is stronger: you could have two events that are not disjoint but whose intersection still happens with probability zero... The problem is that you could have non-empty events which have probability zero of happening (c.f. the example of the uniform distribution on [0,1] in the notes: the probability of {x} happening is zero for any x ∈ [0,1]).

Since in this course, we consider only the finite case, you shouldn't worry too much about this.