Does the following fact have a name?
Theorem 1 Suppose are a countable collection of 0/1 random variables over a probability space such that for every integer and bits the event
Proof: Intuitively, we want to say that by linearity of expectation we have and so by Markov’s inequality
Just to make sure that this can be made rigorous, let’s belabor the proof step by step, doing everything completely from first principles.
First of all, the event
is measurable, because it is the countable intersection over all of the events , which are measurable because each of them is the countable union over all of the events . So suppose towards a contradiction that its probability is not zero, then there is such that
In particular, for every ,
But, by linearity of expectation, Markov’s inequality, and our assumption, we have that for every and every
which is a contradiction if we choose .
Maybe we should also justify . Define the disjoint events as