<< . .

. 11
( : 20)

. . >>

their own hats there are only (n ’ m)! ways that it can be done. Hence
the probability that a particular m heads get their own hats back is

(n ’ m)!
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.

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.]

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.
; 0; 1 ; 1 ; 8 .]
[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?

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 = .

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

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

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) = . (4.1)
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]

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
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
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
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].

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
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
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

When told the answer, a number of the mathematicians that had said
replied that they thought there had to be the same number of balls
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

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

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?
[Ans. .]

(b) What is the probability of rolling an even number given that
a number greater than three turns up?
[Ans. .]

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?

[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.

[Ans. .]

1 1
and Pr[q|p] = 2 , what is Pr[p § q]?
6. If Pr[¬p] = 4

[Ans. .]

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]?
[Ans. .]

(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.
[Ans. = .27.]

(b) The probability that the cards are both jacks, given that one
is a red jack.
[Ans. = .38.]

The probability that the cards are both jacks, given that one
is the jack of hearts.
[Ans. = .43.]

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].

, , , 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

<< . .

. 11
( : 20)

. . >>