Exercise 6.1. This exercise asks you to recast previously established results

in terms of probability theory.

(a) Let k ≥ 2 be an integer, and suppose an integer n is chosen at random

from among all k-bit integers. Show that the probability that n is

prime is ˜(1/k).

(b) Let n be a positive integer, and suppose that a and b are chosen

at random from the set {1, . . . , n}. Show that the probability that

gcd(a, b) = 1 is at least 1/4.

(c) Let n be a positive integer, and suppose that a is chosen at random

from the set {1, . . . , n}. Show that the probability that gcd(a, n) = 1

is „¦(1/ log log n).

6.2 Conditional probability and independence 99

Exercise 6.2. Suppose A, B, C are events such that A © C = B © C. Show

that |P[A] ’ P[B]| ¤ P[C].

Exercise 6.3. Generalize equation (6.3) by proving the inclu-

sion/exclusion principle: for events A1 , . . . , An , we have

P[A1 ∪ · · · ∪ An ] = P[Ai ] ’ P[Ai © Aj ] +

i i<j

P[Ai © Aj © Ak ] ’ · · · + (’1)n’1 P[A1 © · · · © An ]

i<j<k

n

’1

P[Ai1 © · · · © Ai ].

= (’1)

i1 <···<i

=1

Exercise 6.4. Show that for events A1 , . . . , An , we have

P[A1 ∪ · · · ∪ An ] ≥ P[Ai ] ’ P[Ai © Aj ].

i i<j

Exercise 6.5. Generalize inequality (6.5) and the previous exercise by prov-

ing Bonferroni™s inequalities: for events A1 , . . . , An , and de¬ning

m

’1

em := P[A1 ∪ · · · ∪ An ] ’ P[Ai1 © · · · © Ai ]

(’1)

i1 <···<i

=1

for m = 1, . . . , n, we have em ¤ 0 for odd m, and em ≥ 0 for even m.

6.2 Conditional probability and independence

Let D = (U, P) be a probability distribution.

For any event B ⊆ U with P[B] = 0 and any u ∈ U, let us de¬ne

P[u]/P[B] if u ∈ B,

P[u | B] :=

0 otherwise.

Viewing B as ¬xed, we may view the function P[· | B] as a new probability

function on the sample space U, and this gives rise a new probability distri-

bution DB := (P[· | B], U), called the conditional distribution given B.

Intuitively, DB has the following interpretation: if a random experiment

produces an outcome according to the distribution D, and we learn that the

event B has occurred, then the distribution DB assigns new probabilities to

all possible outcomes, re¬‚ecting the partial knowledge that the event B has

occurred.

100 Finite and discrete probability distributions

As usual, we extend the domain of de¬nition of P[· | B] from outcomes to

events. For any event A ⊆ U, we have

P[A © B]

P[A | B] = P[u | B] = .

P[B]

u∈A

The value P[A | B] is called the conditional probability of A given B.

Again, the intuition is that this is the probability that the event A occurs,

given the partial knowledge that the event B has occurred.

For events A and B, if P[A © B] = P[A] · P[B], then A and B are called

independent events. If P[B] = 0, a simple calculation shows that A and B

are independent if and only if P[A | B] = P[A].

A collection A1 , . . . , An of events is called pairwise independent if

P[Ai © Aj ] = P[Ai ]P[Aj ] for all i = j, and is called mutually independent

if every subset Ai1 , . . . , Aik of the collection satis¬es

P[Ai1 © · · · © Aik ] = P[Ai1 ] · · · P[Aik ].

Example 6.9. In Example 6.6, suppose that Alice tells Bob the sum of

the two dice before Bob makes his guess. For example, suppose Alice tells

Bob the sum is 4. Then what is Bob™s best strategy in this case? Let Sz be

the event that the sum is z, for z = 2, . . . , 12, and consider the conditional

probability distribution given S4 . This is the uniform distribution on the

three pairs (1, 3), (2, 2), (3, 1). The numbers 1 and 3 both appear in two

pairs, while the number 2 appears in just one pair. Therefore,

P[C1 | S4 ] = P[C3 | S4 ] = 2/3,

while

P[C2 | S4 ] = 1/3

and

P[C4 | S4 ] = P[C5 | S4 ] = P[C6 | S4 ] = 0.

Thus, if the sum is 4, Bob™s best strategy is to guess either 1 or 3.

Note that the events A1 and B2 are independent, while the events A1 and

S4 are not. 2

Example 6.10. Suppose we toss three fair coins. Let A1 be the event that

the ¬rst coin is “heads,” let A2 be the event that the second coin is “heads,”

and let A3 be the event that the third coin is “heads.” Then the collection

of events {A1 , A2 , A3 } is mutually independent.

Now let B12 be the event that the ¬rst and second coins agree (i.e., both

“heads” or both “tails”), let B13 be the event that the ¬rst and third coins

6.2 Conditional probability and independence 101

agree, and let B23 be the event that the second and third coins agree. Then

the collection of events {B12 , B13 , B23 } is pairwise independent, but not mu-

tually independent. Indeed, the probability that any one of the events occurs

is 1/2, and the probability that any two of the three events occurs is 1/4;

however, the probability that all three occurs is also 1/4, since if any two

events occur, then so does the third. 2

Suppose we have a collection B1 , . . . , Bn of events that partitions U, such

that each event Bi occurs with non-zero probability. Then it is easy to see

that for any event A,

n n

P[A © Bi ] = P[A | Bi ] · P[Bi ].

P[A] = (6.7)

i=1 i=1

Furthermore, if P[A] = 0, then for any j = 1, . . . , n, we have

P[A © Bj ] P[A | Bj ]P[Bj ]

P[Bj | A] = = . (6.8)

n

| Bi ]P[Bi ]

P[A] i=1 P[A

This equality, known as Bayes™ theorem, lets us compute the conditional

probability P[Bj | A] in terms of the conditional probabilities P[A | Bi ].

The equation (6.7) is useful for computing or estimating probabilities by

conditioning on speci¬c events Bi (i.e., by considering the conditional prob-

ability distribution given Bi ) in such a way that the conditional probabilities

P[A | Bi ] are easy to compute or estimate. Also, if we want to compute a

conditional probability P[A | C], we can do so by partitioning C into events

B1 , . . . , Bn , where each Bi occurs with non-zero probability, and use the

following simple fact:

n

P[A | C] = P[A | Bi ]P[Bi ]/P[C]. (6.9)

i=1

Example 6.11. This example is based on the TV game show “Let™s make

a deal,” which was popular in the 1970™s. In this game, a contestant chooses

one of three doors. Behind two doors is a “zonk,” that is, something amusing

but of little or no value, such as a goat, and behind one of the doors is a

“grand prize,” such as a car or vacation package. We may assume that

the door behind which the grand prize is placed is chosen at random from

among the three doors, with equal probability. After the contestant chooses

a door, the host of the show, Monty Hall, always reveals a zonk behind one

of the two doors not chosen by the contestant. The contestant is then given

a choice: either stay with his initial choice of door, or switch to the other

unopened door. After the contestant ¬nalizes his decision on which door

102 Finite and discrete probability distributions