Does This Fact Have a Name?

Does the following fact have a name?

Theorem 1 Suppose {X_1,\ldots,X_n,\ldots} are a countable collection of 0/1 random variables over a probability space {(\Omega, {\cal B}, \mathop{\mathbb P})} such that for every integer {n} and bits {b_1,\ldots,b_n} the event

\displaystyle  X_1 = b_1 \wedge \cdots \wedge X_n = b_n

is measurable.

Suppose that

\displaystyle  \sum_{i=1}^\infty \mathop{\mathbb E} X_i \ \ \ {\rm converges}

Then

\displaystyle  \mathop{\mathbb P} \left[ \sum_i X_i = \infty \right] = 0

Proof: Intuitively, we want to say that by linearity of expectation we have {\mathop{\mathbb E} [ \sum_{i=1}^\infty X_i ] = O(1)} and so by Markov’s inequality

\displaystyle  \mathop{\mathbb P} \left[ \sum_{i=1}^\infty X_i = \infty\right] \leq \frac{O(1)}{\infty} = 0

Just to make sure that this can be made rigorous, let’s belabor the proof step by step, doing everything completely from first principles.

Let {c:= \sum_{i=1}^\infty \mathop{\mathbb E} X_i}.

First of all, the event

\displaystyle  \sum_{i=1}^\infty X = \infty

is measurable, because it is the countable intersection over all {t} of the events {\sum_{i=1}^\infty X \geq t}, which are measurable because each of them is the countable union over all {n} of the events {\sum_{i=1}^n X_i \geq t}. So suppose towards a contradiction that its probability is not zero, then there is {\epsilon >0} such that

\displaystyle  \mathop{\mathbb P} \left[ \sum_{i=1}^\infty X_i = \infty\right] = \epsilon

In particular, for every {t},

\displaystyle  \mathop{\mathbb P} \left[ \sum_{i=1}^\infty X_i \geq t \right] \geq \epsilon

But, by linearity of expectation, Markov’s inequality, and our assumption, we have that for every {n} and every {t}

\displaystyle  \mathop{\mathbb P} \left[ \sum_{i=1}^n X_i \geq t \right] \leq \frac {\mathop{\mathbb E} \sum_{i=1}^n X_i}{t} = \frac{\sum_{i=1}^n \mathop{\mathbb E} X_i}{t} \leq \frac ct

Now,

\displaystyle  \epsilon \leq \mathop{\mathbb P} \left[ \sum_{i=1}^\infty X_i \geq t \right] = \lim_{n\rightarrow \infty} \mathop{\mathbb P} \left[ \sum_{i=1}^n X_i \geq t \right] \leq \frac ct

which is a contradiction if we choose {t > c/\epsilon}.

Maybe we should also justify {\mathop{\mathbb P} \left[ \sum_{i=1}^\infty X_i \geq t \right] = \lim_{n\rightarrow \infty} \mathop{\mathbb P} \left[ \sum_{i=1}^n X_i \geq t \right]}. Define the disjoint events {E_1,\ldots,E_n,\ldots} as

\displaystyle  E_n := \left( \sum_{i=1}^n X_i \geq t \right) \wedge \left( \sum_{i=1}^{n-1} X_i < t \right)

Then

\displaystyle  \mathop{\mathbb P} \left[ \sum_{i=1}^\infty X_i \geq t \right] = \mathop{\mathbb P} \left [ \bigcup_{i=1}^\infty E_i \right] = \sum_{i=1}^\infty \mathop{\mathbb P} [ E_i ]

and

\displaystyle  \lim_{n\rightarrow \infty} \mathop{\mathbb P} \left[ \sum_{i=1}^n X_i \geq t \right] = \lim_{n\rightarrow \infty} \mathop{\mathbb P} \left[ \bigcup_{i=1}^n E_i \right]= \lim_{n\rightarrow \infty} \sum_{i=1}^n \mathop{\mathbb P}[ E_i] = \sum_{i=1}^\infty \mathop{\mathbb P}[E_i]

\Box

12 thoughts on “Does This Fact Have a Name?

  1. I needed something very similar in a recent paper, and we showed it followed directly from the central limit theorem (we used a version for independent non-identically distributed random variables, see pg 176 in Grimmett “Probability and random processes”).

  2. Thanks, commenter.

    Batz, note that the statement is true even if you don’t have independence, which makes it much more versatile.

    Harrison: yes, after posting it here it occurred to me that mathoverflow would have been a better place. But I still got an answer in 27 minutes.

  3. Indeed, Borel-Cantelli.

    Moreover, your proof seems needlessly complicated. All you need to show is
    that

    E[ \sum_i X_i] < infinity,

    which would immediately rule out the possibility that \sum_i X_i = infinity
    with positive probability. But this follows right away from interchanging sum
    and expectation; the interchange can be easily justified since each X_i is nonnegative.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s