Mathematics for Computer Science

19.7. Really Great Expectations 835

Problem 19.32.
An infinite version of Murphy’s Law is that if an infinite number of mutually inde-
pendent events are expected to happen, then the probability that only finitely many
happen is 0. This is known as the firstBorel-Cantelli Lemma.

(a)LetA 0 ;A 1 ;:::be any infinite sequence of mutually independent events such
that X

n 2 N

PrŒAnçD1: (19.28)

Prove that PrŒnoAnoccursçD 0.

Hint:Bkthe event that noAnwithnkoccurs. So the event that noAnoccurs is

BWWD

\

k 2 N

Bk:

Apply Murphy’s Law, Theorem 19.6.4, toBk.

(b)Conclude that PrŒonly finitely manyAn’s occurçD 0.

Hint:LetCkbe the event that noAnwithnkoccurs. So the event that only
finitely manyAn’s occur is
CWWD

[

k 2 N

Ck:

Apply part (a) toCk.

Problems for Section 19.7

Practice Problems

Problem 19.33.
LetRbe a positive integer valued random variable such that

PDFR.n/D

1

cn^3

;

where

cWWD

X^1

nD 1

1

n^3

:

(a)Prove that ExŒRçis finite.