the probability that a particular m heads get their own hats back is

(n ’ m)!

.

n!

n

There are m di¬erent ways we can choose m heads out of n. Hence

the mth group of terms contributes

(n ’ m)!

n 1

· =

m n! m!

to the alternating sum. Thus

1 1 1 1

Pr[p1 ∨ p2 ∨ . . . ∨ pn ] = 1 ’ + ’ +...± ,

2! 3! 4! n!

where the + sign is chosen if n is odd and the ’ sign if n is even. In

Figure 4.2, these numbers are given for the ¬rst few values of n.

It can be shown that, as the number of hats increases, the proba-

bilities approach a number 1 ’ (1/e) = .632121 . . ., where the number

e = 2.71828 . . . is a number that plays an important role in many

branches of mathematics.

Exercises

1. What odds should you be willing to give on a bet that at least

two people in the United States Senate have the same birthday?

[Ans. 3, 300, 000 : 1.]

102 CHAPTER 4. PROBABILITY THEORY

Figure 4.2: ™¦

2. What is the probability that in the House of Representatives at

least two men have the same birthday?

3. What odds should you be willing to give on a bet that at at least

two of the Presidents of the United States have had the same

birthday? Would you win the bet?

[Ans. More than 4 : 1; Yes. Polk and Harding were born on

Nov. 2.]

4. What odds should you be willing to give on the bet that at least

two of the Presidents of the United States have died on the same

day of the year? Would you win the bet?

[Ans. More than 2.7 : 1; Yes. Je¬erson, Adams, and Monroe all

died on July 4.]

5. Four men check their hats. Assuming that the hats are returned

at random, what is the probability that exactly four men get their

own hats? Calculate the answer for 3, 2, 1, 0 men.

1

; 0; 1 ; 1 ; 8 .]

3

[Ans. 24 43

6. A group of 50 knives and forks a dance. The partners for a dance

are chosen by lot (knives dance with forks). What is the approx-

imate probability that no knife dances with its own fork?

103

4.4. TWO NONINTUITIVE EXAMPLES

7. Show that the probability that, in a group of r people, exactly

one pair has the same birthday is

r 365 · 364 . . . (365 ’ r + 2)

tr = .

365r

2

r qr

8. Show that tr = 2 366’r , where tr is de¬ned in Exercise 7, and qr

is the probability that no pair has the same birthday.

9. Using the result of Exercise 8 and the results given in Figure 4.1,

¬nd the probability of exactly one pair of people with the same

birthday in a group of r people, for r = 15, 20, 25, 30, 40, 50.

[Ans. .22; .32; .38; .38; .26; .12.]

10. What is the approximate probability that there has been exactly

one pair of Presidents with the same birthday?

Supplementary exercises.

11. Find a formula for the probability of having more than one coin-

cidence of birthdays among n people, i.e., of having at least two

pairs of identical birthdays, or of three or more people having

the same birthday. [Hint: Take the probability of at least one

coincidence, and subtract the probability of having exactly one

pair.]

12. Compute the probability of having more than one coincidence of

birthdays when there are 20, 25, 30, 40, or 50 people in the room.

13. What is the smallest number of people you need in order to have

a better than even chance of ¬nding more than one coincidence

of birthdays?

[Ans. 36.]

14. Is it very surprising that there was more than one coincidence of

birthdays among the dates on which Presidents died?

15. A game of solitaire is played as follows: A deck of cards is shu¬„ed,

and then the player turns the cards up one at a time. As the

player turns the cards, he or she calls out the names of the cards

104 CHAPTER 4. PROBABILITY THEORY

in a standard order”say “two of clubs”, “three of clubs”, etc.

The object of the game is to go through the entire deck without

once calling out the name of the card one turns up. What is the

probability of winning? How does the probability change if one

uses a single suit in place of a whole deck?

4.5 Conditional probability

Suppose that we have a given U and that measures have been assigned

to all subsets of U . A statement p will have probability Pr[p] = m(P ).

Suppose we now receive some additional information, say that state-

ment q is true. How does this additional information alter the proba-

bility of p?

The probability of p after the receipt of the information q is called its

conditional probability, and it is denoted by Pr[p|q], which is read “the

probability of p given q”. In this section we will construct a method of

¬nding this conditional probability in terms of the measure m.

If we know that q is true, then the original possibility set U has

been reduced to Q and therefore we must de¬ne our measure on the

subsets of Q instead of on the subsets of U . Of course, every subset X

of Q is a subset of U , and hence we know m(X), its measure before q

was discovered. Since q cuts down on the number of possibilities, its

new measure m (X) should be larger.

The basic idea on which the de¬nition of m is based is that, while

we know that the possibility set has been reduced to Q, we have no

new information about subsets of Q. If X and Y are subsets of Q, and

m(X) = 2 · m(Y ), then we will want m (X) = 2 · m (Y ). This will

be the case if the measures of subsets of Q are simply increased by a

proportionality factor m (X) = k · m(X), and all that remains is to

determine k. Since we know that 1 = m (Q) = k · m(Q), we see that

k = 1/m(Q) and our new measure on subsets of U is determined by

the formula

m(X)

m (X) = . (4.1)

m(Q)

How does this a¬ect the probability of p? First of all, the truth set

of p has been reduced. Because all elements of Q have been eliminated,

the new truth set of p is P © Q and therefore

m(P © Q) Pr[p § q]

Pr[p|q] = m (P © Q) = = . (4.2)

m(Q) Pr[q]

105

4.5. CONDITIONAL PROBABILITY

Note that if the original measure m is the equiprobable measure, then

the new measure m will also be the equiprobable measure on the set

Q.

We must take care that the denominators in 4.1 and 4.2 be di¬erent

from zero. Observe that m(Q) will be zero if Q is the empty set, which

happens only if q is self-contradictory. This is also the only case in

which Pr[q] = 0, and hence we make the obvious assumption that our

information q is not self-contradictory.

Example 4.7 In an election, candidate A has a .4 chance of winning,

B has .3 chance, C has .2 chance, and D has .1 chance. Just before the

election, C withdraws. Now what are the chances of the other three

candidates? Let q be the statement that C will not win, i.e., that A or B

or D will win. Observe that Pr[q] = .8, hence all the other probabilities

are increased by a factor of 1/.8 = 1.25. Candidate A now has .5 chance

™¦

of winning, B has .375, and D has .125.

Example 4.8 A family is chosen at random from the set of all families

having exactly two children (not twins). What is the probability that

the family has two boys, if it is known that there is a boy in the family?

Without any information being given, we would assign the equiprobable

measure on the set U = {BB, BG, GB, GG}, where the ¬rst letter of

the pair indicates the sex of the younger child and the second that of

the older. The information that there is a boy causes U to change to

{BB, BG, GB}, but the new measure is still the equiprobable measure.

Thus the conditional probability that there are two boys given that

1

there is a boy is 3 . If, on the other hand, we know that the ¬rst

child is a boy, then the possibilities are reduced to {BB, BG} and the

1

™¦

conditional probability is 2 .

A particularly interesting case of conditional probability is that in

which Pr[p|q] = Pr[p]. That is, the information that q is true has no

e¬ect on our prediction for p. If this is the case, we note that

Pr[p § q] = Pr[p]Pr[q]. (4.3)

And the case Pr[q|p] = q leads to the same equation. Whenever equa-

tion 4.3 holds, we say that p and q are independent. Thus if q is not a

self-contradiction, p and q are independent if and only if Pr[p|q] = Pr[p].

106 CHAPTER 4. PROBABILITY THEORY

Example 4.9 Consider three throws of an ordinary coin, where we

consider the eight possibilities to be equally likely. Let p be the state-

ment “A head turns up on the ¬rst throw” and q be the statement,

“A tail turns up on the second throw”. Then Pr[p] = Pr[q] = 1 and 2

1

Pr[p § q] = 4 and therefore p and q are independent statements. ™¦

While we have an intuitive notion of independence, it can happen

that two statements, which may not seem to be independent, are in

fact independent. For example, let r be the statement “The same side

turns up all three times”. Let s be the statement “At most one head

occurs”. Then r and s are independent statements (see Exercise 10).

An important use of conditional probabilities arises in the following

manner. We wish to ¬nd the probability of a statement p. We observe

that there is a complete set of alternatives q1 , q2 , . . . , qn such that the

probability Pr[qi ] as well as the conditional probabilities Pr[p|qi ] can be

found for every i. Then in terms of these we can ¬nd Pr[p] by

Pr[p] = Pr[q1 ]Pr[p|q1 ] + Pr[q2 ]Pr[p|q2 ] + . . . + Pr[qn ]Pr[p|qn ].

The proof of this assertion is left as an exercise (see Exercise 13).

Example 4.10 A psychology student once studied the way mathe-

maticians solve problems and contended that at times they try too

hard to look for symmetry in a problem. To illustrate this she asked a

number of mathematicians the following problem: Fifty balls (25 white

and 25 black) are to be put in two urns, not necessarily the same num-

ber of balls in each. How should the balls be placed in the urns so as

to maximize the chance of drawing a black ball, if an urn is chosen at

random and a ball drawn from this urn? A quite surprising number of

1

mathematicians answered that you could not do any better than 2 by

the symmetry of the problem. In fact one can do a good deal better by

putting one black ball in urn 1, and all the 49 other balls in urn 2. To

¬nd the probability in this case let p be the statement “A black ball is

drawn”, q1 the statement “Urn 1 is drawn” and q2 the statement “Urn

2 is drawn”. Then q1 and q2 are a complete set of alternatives so

Pr[p] = Pr[q1 ]Pr[p|q1 ] + Pr[q2 ]Pr[p|q2 ].

1 24

But Pr[q1 ] = Pr[q2 ] = and Pr[p|q1 ] = 1, Pr[p|q2 ] = . Thus

2 49

1 1 24 73

·1+ ·

Pr[p] = = = .745.

2 2 49 98

107

4.5. CONDITIONAL PROBABILITY

When told the answer, a number of the mathematicians that had said

1

replied that they thought there had to be the same number of balls

2

in each urn. However, since this had been carefully stated not to be

necessary, they also had fallen into the trap of assuming too much

™¦

symmetry.

Exercises

1. A card is drawn at random from a pack of playing cards. What

is the probability that it is a 5, given that it is between 2 and 7

inclusive?

2. A die is loaded in such a way that the probability of a given

number turning up is proportional to that number (e.g., a 6 is

three times as likely to turn up as a 2).

(a) What is the probability of rolling a 3 given that an odd

number turns up?

1

[Ans. .]

3

(b) What is the probability of rolling an even number given that

a number greater than three turns up?

2

[Ans. .]

3

3. A die is thrown twice. What is the probability that the sum of

the faces which turn up is greater than 10, given that one of them

is a 6? Given that the ¬rst throw is a 6?

31

[Ans. ; .]

11 3

4. Referring to Exercise 9, what is the probability that the students

selected studies German if

(a) He or she studies French?

(b) He or she studies French and Russian?

(c) He or she studies neither French nor Russian?

5. In the primary voting example of Section 2.1, assuming that the

equiprobable measure has been assigned, ¬nd the probability that

A wins at least two primaries, given that B drops out of the

Wisconsin primary.

108 CHAPTER 4. PROBABILITY THEORY

7

[Ans. .]

9

1 1

and Pr[q|p] = 2 , what is Pr[p § q]?

6. If Pr[¬p] = 4

3

[Ans. .]

8

7. A student takes a ¬ve-question true-false exam. What is the

probability that the student will get all answers correct if

(a) The student is only guessing?

(b) The student knows that the instructor puts more true than

false questions on his or her exams?

(c) The student also knows that the instructor never puts three

questions in a row with the same answer?

(d) The student also knows that the ¬rst and last questions must

have the opposite answer?

(e) The student also knows that the answer to the second prob-

lem is “false”?

8. Three persons, A, B, and C, are placed at random in a straight

line. Let r be the statement “B is to the right of A” and let s be

the statement “C is to the right of A”.

(a) What is the Pr[r § s]?

1

[Ans. .]

3

(b) Are r and s independent?

[Ans. No.]

9. Let a deck of cards consist of the jacks and queens chosen from a

bridge deck, and let two cards be drawn from the new deck. Find

(a) The probability that the cards are both jacks, given that one

is a jack.

3

[Ans. = .27.]

11

(b) The probability that the cards are both jacks, given that one

is a red jack.

5

[Ans. = .38.]

13

109

4.5. CONDITIONAL PROBABILITY

The probability that the cards are both jacks, given that one

is the jack of hearts.

3

[Ans. = .43.]

7

10. Prove that statements r and s in Example 4.9 are independent.

11. The following example shows that r may be independent of p and

q without being independent of p § q and p ∨ q. We throw a

coin twice. Let p be “The ¬rst toss comes out heads”, q be “The

second toss comes out heads”, and r be “The two tosses come out

the same”. Compute Pr[r], Pr[r|p], Pr[r|q], Pr[r|p § q], Pr[r|p ∨ q].

111

, , , 1, 1 .]

[Ans. 222 3

12. Prove that for any two statements p and q,

Pr[p] = Pr[p § q] + Pr[p § ¬q].

13. Let p be any statement and q1 , q2 , q3 be a complete set of alter-

natives. Prove that

Pr[p] = Pr[q1 ]Pr[p|q1 ] + Pr[q2 ]Pr[p|q2 ] + Pr[q3 ]Pr[p|q3 ].

14. Prove that the procedure given in Example 4.10 does maximize

the chance of getting a black ball. [Hint: Show that you can

assume that one urn contains more black balls than white balls

and then consider what is the best that could be achieved, ¬rst

in the urn with more black than white balls, and then in the urn

with more white than black balls.]

Supplementary exercises.

15. Assume that p and q are independent statements relative to a

given measure. Prove that each of the following pairs of state-

ments are independent relative to this same measure.

(a) p and ¬q.

(b) ¬q and p.

(c) ¬p and ¬q

110 CHAPTER 4. PROBABILITY THEORY