<<

. 3
( 6)



>>


as the number of distinct letters. The reader should verify this answer
™¦
by direct count.
It often happens that a counting problem can be formulated in a
number of di¬erent ways that sound quite di¬erent but that are in fact
equivalent. And in one of these ways the answer may suggest itself
readily. To illustrate how a reformulation can make a hard sounding
problem easy, we give an alternate method for solving the problem
considered in Exercise 13.
The problem is to count the number of ways that n indistinguishable
objects can be put into r cells. For instance, if there are three objects
75
3.8. TECHNIQUES FOR COUNTING

and three cells, the number of di¬erent ways can be enumerated as
follows (Using —¦ for object and bars to indicate the sides of the cells:

| —¦—¦—¦ | | |
| —¦—¦ | —¦ | |
| —¦—¦ | | —¦ |
| —¦ | —¦—¦ | |
| —¦ | —¦ | —¦ |
| | —¦—¦—¦ | |
| | —¦—¦ | —¦ |
| | —¦ | —¦—¦ |
| | | —¦—¦—¦ |

We see that in this case there are ten ways the task can be accomplished.
But the answer for the general case is not clear.
If we look at the problem in a slightly di¬erent manner, the answer
suggests itself. Instead of putting the objects in the cells, we imagine
putting the cells around the objects. In the above case we see that
three cells are constructed from four bars. Two of these bars must
be placed at the ends. The two other bars together with the three
objects we regard as occupying ¬ve intermediate positions. Of these
¬ve intermediate positions we must choose two of them for bars and
three for the objects. Hence the total number of ways we can accomplish
the task is 5 = 5 = 10, which is the answer we got by counting all
2 3
the ways.
For the general case we can argue in the same manner. We have r
cells and n objects. We need r + 1 bars to form the r cells, but two
of these must be ¬xed on the ends. The remaining r ’ 1 bars together
with the n objects occupy r ’ 1 + n intermediate positions. And we
must choose r ’ 1 of these for the bars and the remaining n for the
objects. Hence our task can be accomplished in

n+r’1 n+r’1
=
r’1 n

di¬erent ways.

Example 3.23 Seven people enter an elevator that will stop at ¬ve
¬‚oors. In how many di¬erent ways can the people leave the elevator if
we are interested only in the number that depart at each ¬‚oor, and do
not distinguish among the people? According to our general formula,
76 CHAPTER 3. PARTITIONS AND COUNTING

the answer is
7+5’1 11
= = 330.
7 7
Suppose we are interested in ¬nding the number of such possibilities in
which at least one person gets o¬ at each ¬‚oor. We can then arbitrarily
assign one person to get o¬ at each ¬‚oor, and the remaining two can
get o¬ at any ¬‚oor. They can get o¬ the elevator in
2+5’1 6
= = 15
2 2
™¦
di¬erent ways.

Exercises
1. The survey discussed in Exercise 8 has been enlarged to include
a fourth magazine D. It was found that no one who reads either
magazine A or magazine B reads magazine D. However, 10 per
cent of the people read magazine D and 5 per cent read both C
and D. What per cent of the people do not read any magazine?

[Ans. 5 per cent.]

2. A certain college administers three qualifying tests. They an-
nounce the following results: “Of the students taking the tests, 2
per cent failed all three tests, 6 per cent failed tests A and B, 5
per cent failed A and C, 8 per cent failed B and C, 29 per cent
failed test A, 32 per cent failed B, and 16 per cent failed C.” How
many students passed all three qualifying tests?

3. Four partners in a game require a score of exactly 20 points to
win. In how many ways can they accomplish this?
23
[Ans. .]
3

4. In how many ways can eight apples be distributed among four
boys? In how many ways can this be done if each boy is to get
at least one apple?

5. Suppose we have n balls and r boxes with n ≥ r. Show that the
number of di¬erent ways that the balls can be put into the boxes
which insures that there is at least one ball in every box is n’1 .
r’1
77
3.8. TECHNIQUES FOR COUNTING

6. Identical prizes are to be distributed among ¬ve boys. It is ob-
served that there are 15 ways that this can be done if each boy is
to get at least one prize. How many prizes are there?

[Ans. 7.]

7. Let p1 , p2 , . . . , pn be n statements relative to a possibility space
U . Show that the inclusion-exclusion formula gives a formula
for the number of elements in the truth set of the disjunction
p1 ∨ p2 ∨ . . . ∨ pn in terms of the numbers of elements in the truth
sets of conjunctions formed from subsets of these statements.

8. A boss asks his or her secretary to put letters written to seven
di¬erent persons into addressed envelopes. Find the number of
ways that this can be done so that at least one person gets his or
her own letter. [Hint: Use the result of Exercise 7, letting pi be
the statement “The ith person gets his or her own letter”.]

[Ans. 3186.]

9. Consider the numbers from 2 to 10 inclusive. Let A2 be the set of
numbers divisible by 2 and A3 the set of numbers divisible by 3.
Find n(A2 ∪ A3 ) by using the inclusion-exclusion formula. From
this result ¬nd the number of prime numbers between 2 and 10
(where a prime number is a number divisible only by itself and
by 1). [Hint: Be sure to count the numbers 2 and 3 among the
primes.]

10. Use the method of Exercise 9 to ¬nd the number of prime numbers
between 2 and 100 inclusive. [Hint: Consider ¬rst the sets A2 ,
A3 , A5 , and A7 .]

[Ans. 25.]

11. Verify that the following formula gives the number of elements in
the intersection of three sets.

n(A1 © A2 © A3 ) = n(A1 ) + n(A2 ) + n(A3 )
’ n(A1 ∪ A2 ) ’ n(A1 ∪ A3 ) ’ n(A2 ∪ A3 )
+ n(A1 ∪ A2 ∪ A3 ).
78 CHAPTER 3. PARTITIONS AND COUNTING

12. Show that if we replace © by ∪ and ∪ by © in formula 3.2, we
get a valid formula for the number of elements in the intersection
of n sets. [Hint: Apply the inclusion-exclusion formula to the
left-hand side of
˜ ˜ ˜
n(A1 ∪ A2 ∪ . . . ∪ An ) = n(U ) ’ n(A1 © A2 © . . . © An .]

13. For n ¤ m prove that
m n m n m n m n m+n
+ + +...+ =
0 0 1 1 2 2 n n n
by carrying out the following two steps:
(a) Show that the left-hand side counts the number of ways of
choosing equal numbers of men and women from sets of m
men and n women.
(b) Show that the right-hand side also counts the same number
by showing that we can select equal numbers of men and
women by selecting any subset of n persons from the whole
set, and then combining the men selected with the women
not selected.
14. By an ordered partition of n with r elements we mean a sequence
of r nonnegative integers, possibly some 0, written in a de¬nite
order, and having n as their sum. For instance, [1, 0, 3] and [3, 0, 1]
are two di¬erent ordered partitions of 4 with three elements. Show
that the number of ordered partitions of n with r elements is
n+r’1
.
n

15. Show that the number of di¬erent possibilities for the outcomes
of rolling n dice is n+5 .
n

Note. The next few exercises illustrate an important counting
technique called the re¬‚ection principle. In Figure 3.6 we show
a path from the point (0, 2) to the point (7, 1). We shall be
interested in counting the number of paths of this type where at
each step the path moves one unit to the right, and either one
unit up or one unit down. We shall see that this model is useful
for analyzing voting outcomes.
16. Show that the number of di¬erent paths leading from the point
(0, 2) to (7, 1) is 7 . [Hint: Seven decisions must be made, of
3
which three moves are up and the rest down.]
79
3.8. TECHNIQUES FOR COUNTING




Figure 3.6: ™¦

17. Show that the number of di¬erent paths from (0, 2) to (7, 1) which
touch the x-axis at least once is the same as the total number of
paths from the point (0, ’2) to the point (7, 1). [Hint: Show
that for every path to be counted from (0, 2) that touches the x-
axis, there corresponds a path from (0, ’2) to (7, 1) obtained by
re¬‚ecting the part of the path to the ¬rst touching point through
the x-axis. A speci¬c example is shown in Figure 3.7.]
18. Use the results of Exercises 16 and 17 to ¬nd the number of paths
from (0, 2) to (7, 1) that never touch the x-axis.

[Ans. 14.]

19. Nine votes are cast in a race between two candidates A and B.
Candidate A wins by one vote. Find the number of ways the
ballots can be counted so that candidate A is leading throughout
the entire count. [Hint: The ¬rst vote counted must be for A.
Counting the remaining eight votes corresponds to a path from
(1, 1) to (9, 1). We want the number of paths that never touch
the x-axis.]

[Ans. 14.]
(k)
20. Let the symbol nr stand for “the number of elements that are
(1)
in k or more of the r sets A1 , A2 , . . . , Ar ”. Show that n3 =
n(A1 ∪ A2 ∪ A3 ).
80 CHAPTER 3. PARTITIONS AND COUNTING




Figure 3.7: ™¦

21. Show that
(2)
= n((A1 © A2 ) ∪ (A1 © A3 ) ∪ (A2 © A3 ))
n3
= n(A1 © A2 ) + n(A1 © A3 ) + n(A2 © A3 ) ’ 2n(A1 © A2 © A3 )

by using the inclusion-exclusion formula. Also develop an inde-
pendent argument for the last formula.
22. Use Exercise 21 to ¬nd the number of letters that appear two or
more times in the three words TABLE, BASIN, and CLASP.
(1) (2)
23. Give an interpretation for n3 ’ n3 .
24. Use Exercise 23 to ¬nd the number of letters that occur exactly
once in the three words of Exercise 22.
25. Develop a general argument like that in Exercise 21 to show that
(2)
= n(A1 © A2 ) + n(A1 © A3 ) + n(A1 © A4 )
n4
+ n(A2 © A3 ) + n(A2 © A4 ) + n(A3 © A4 )
’ 2[n(A1 © A2 © A3 ) + n(A1 © A2 © A4 )
+ n(A1 © A3 © A4 ) + n(A2 © A3 © A4 )]
+ 3n(A1 © A2 © A3 © A4 )

26. Use Exercise 25 to ¬nd the number of letters used two or more
times in the four words of Example 3.22.
81
3.8. TECHNIQUES FOR COUNTING

27. From the formulas in Exercises 21 and 25 guess the general for-
mula for n(2) and develop a general argument to establish its
r
correctness.

Suggested reading.
Shapley, L. S., and M. Shubik, “A Method for Evaluating the Distribu-
tion of Power in a Committee System”, The American Political Science
Review 48 (1954), pp. 787“792.
Whitworth, W. A., Choice and Chance, with 1000 Exercises, 1934.
Goldberg, S., Probability: An Introduction, 1960.
Parzen, E., Modern Probability Theory and Its Applications, 1960.
82 CHAPTER 3. PARTITIONS AND COUNTING
Chapter 4

Probability theory

4.1 Introduction
We often hear statements of the following kind: “It is likely to rain
today”, “I have a fair chance of passing this course”, “There is an even
chance that a coin will come up heads”, etc. In each case our statement
refers to a situation in which we are not certain of the outcome, but we
express some degree of con¬dence that our prediction will be veri¬ed.
The theory of probability provides a mathematical framework for such
assertions.
Consider an experiment whose outcome is not known. Suppose that
someone makes an assertion p about the outcome of the experiment,
and we want to assign a probability to p. When statement p is consid-
ered in isolation, we usually ¬nd no natural assignment of probabilities.
Rather, we look for a method of assigning probabilities to all conceiv-
able statements concerning the outcome of the experiment. At ¬rst this
might seem to be a hopeless task, since there is no end to the state-
ments we can make about the experiment. However we are aided by a
basic principle:
Fundamental assumption. Any two equivalent statements will
be assigned the same probability. As long as there are a ¬nite number
of logical possibilities, there are only a ¬nite number of truth sets, and
hence the process of assigning probabilities is a ¬nite one. We proceed
in three steps: (l) we ¬rst determine U , the possibility set, that is, the
set of all logical possibilities, (2) to each subset X of U we assign a
number called the measure m(X), (3) to each statement p we assign
m(P ), the measure of its truth set, as a probability. The probability of
statement p is denoted by Pr[p].

83
84 CHAPTER 4. PROBABILITY THEORY

The ¬rst step, that of determining the set of logical possibilities,
is one that we considered in the previous chapters. It is important to
recall that there is no unique method for analyzing logical possibilities.
In a given problem we may arrive at a very ¬ne or a very rough analysis
of possibilities, causing U to have many or few elements.
Having chosen U , the next step is to assign a number to each sub-
set X of U , which will in turn be taken to be the probability of any
statement having truth set X. We do this in the following way.
Assignment of a measure. Assign a positive number (weight) to
each element of U , so that the sum of the weights assigned is 1. Then
the measure of a set is the sum of the weights of its elements. The
measure of the set … is 0.
In applications of probability to scienti¬c problems, the analysis of
the logical possibilities and the assignment of measures may depend
upon factual information and hence can best be done by the scientist
making the application.
Once the weights are assigned, to ¬nd the probability of a particular
statement we must ¬nd its truth set and ¬nd the sum of the weights
assigned to elements of the truth set. This problem, which might seem
easy, can often involve considerable mathematical di¬culty. The de-
velopment of techniques to solve this kind of problem is the main task
of probability theory.

Example 4.1 An ordinary die is thrown. What is the probability that
the number which turns up is less than four? Here the possibility set is
U = {1, 2, 3, 4, 5, 6}. The symmetry of the die suggests that each face
should have the same probability of turning up. To make this so, we
1
assign weight 6 to each of the outcomes. The truth set of the statement
“The number which turns up is less than four” is {1, 2, 3}. Hence the
probability of this statement is 3 = 1 , the sum of the weights of the
6 2
™¦
elements in its truth set.


Example 4.2 A gambler attends a race involving three horses A, B,
and C. He or she feels that A and B have the same chance of winning
but that A (and hence also B) is twice as likely to win as C is. What is
the probability that A or C wins? We take as U the set {A, B, C}. If we
were to assign weight a to the outcome C, then we would assign weight
2a to each of the outcomes A and B. Since the sum of the weights must
be l, we have 2a + 2a + a = 1, or a = 1 . Hence we assign weights 2 ,
5 5
21
, 5 to the outcomes A, B, and C, respectively. The truth set of the
5
85
4.1. INTRODUCTION

statement “Horse A or C wins” is {A, C}. The sum of the weights of
the elements of this set is 2 + 1 = 5 . Hence the probability that A or
3
5 5
3
™¦
C wins is 5 .


Exercises
1. Assume that there are n possibilities for the outcome of a given
experiment. How should the weights be assigned if it is desired
that all outcomes be assigned the same weight?

2. Let U = {a, b, c}. Assign weights to the three elements so that
no two have the same weight, and ¬nd the measures of the eight
subsets of U .

3. In an election Jones has probability 1 of winning, Smith has prob-
2
1 1
ability 3 , and Black has probability 6 .

(a) Construct U .
(b) Assign weights.
(c) Find the measures of the eight subsets.
(d) Give a pair of nonequivalent predictions which have the same
probability.

4. Give the possibility set U for each of the following experiments.

(a) An election between candidates A and B is to take place.
(b) A number from 1 to 5 is chosen at random.
(c) A two-headed coin is thrown.
(d) A student is asked for the day of the year on which his or
her birthday falls.

5. For which of the cases in Exercise 4 might it be appropriate to
assign the same weight to each outcome?

6. Suppose that the following probabilities have been assigned to the
possible results of putting a penny in a certain defective peanut-
1
vending machine: The probability that nothing comes out is 2 .
The probability that either you get your money back or you get
peanuts (but not both) is 1 .
3
86 CHAPTER 4. PROBABILITY THEORY

(a) What is the probability that you get your money back and
also get peanuts?
1
[Ans. .]
6

(b) From the information given, is it possible to ¬nd the proba-
bility that you get peanuts?
[Ans. No.]

7. A die is loaded in such a way that the probability of each face is
proportional to the number of dots on that face. (For instance, a
6 is three times as probable as a 2.) What is the probability of
getting an even number in one throw?

4
[Ans. .]
7


8. If a coin is thrown three times, list the eight possibilities for the
outcomes of the three successive throws. A typical outcome can
be written (HTH). Determine a probability measure by assigning
an equal weight to each outcome. Find the probabilities of the
following statements.

(a) r: The number of heads that occur is greater than the num-
ber of tails.
1
[Ans. .]
2

(b) s: Exactly two heads occur.
5
[Ans. .]
8

(c) t: The same side turns up on every throw.
1
[Ans. .]
4

9. For the statements given in Exercise 8, which of the following
equalities are true?

(a) Pr[r ∨ s] = Pr[r] + Pr[s]
(b) Pr[s ∨ t] = Pr[s] + Pr[t]
(c) Pr[r ∨ ¬r] = Pr[r] + Pr[¬r]
(d) Pr[r ∨ t] = Pr[r] + Pr[t]
87
4.2. PROPERTIES OF A PROBABILITY MEASURE

10. Which of the following pairs of statements (see Exercise 8) are
inconsistent? (Recall that two statements are inconsistent if their
truth sets have no element in common.)
(a) r, s
[Ans. consistent.]
(b) s, t
[Ans. inconsistent.]
(c) r, ¬r
[Ans. inconsistent.]
(d) r, t
[Ans. consistent.]
11. State a theorem suggested by Exercises 9 and 10.
12. An experiment has three possible outcomes, a, b, and c. Let p be
the statement “the outcome is a or b”, and q be the statement
“the outcome is b or c”. Assume that weights have been assigned
to the three outcomes so that Pr[p] = 2 and Pr[q] = 6 . Find the
5
3
weights.
111
[Ans. , , .]
623

1 3
13. Repeat Exercise 12 if Pr[p] = and Pr[q] = 8 .
2



4.2 Properties of a probability measure
Before studying special probability measures, we shall consider some
general properties of such measures which are useful in computations
and in the general understanding of probability theory.
Three basic properties of a probability measure are
(A) m(X) = 0 if and only if X = ….
(B) 0 < m(X) < 1 for any set X.
(C) For two sets X and Y ,
m(X ∪ Y ) = m(X) + m(Y )
if and only if X and Y are disjoint, i.e., have no elements in common.
88 CHAPTER 4. PROBABILITY THEORY

The proofs of properties (A) and (B) are left as an exercise (see
Exercise 16). We shall prove (C). We observe ¬rst that m(X) + m(Y )
is the sum of the weights of the elements of X added to the sum of the
weights of Y . If X and Y are disjoint, then the weight of every element
of X ∪ Y is added once and only once, and hence m(X) + m(Y ) =
m(X ∪ Y ). Assume now that X and Y are not disjoint. Here the
weight of every element contained in both X and Y , i.e., in X © Y ,
is added twice in the sum m(X) + m(Y ). Thus this sum is greater
than m(X ∪ Y ) by an amount m(X © Y ). By (A) and (B), if X © Y
is not the empty set, then m(X © Y ) > 0. Hence in this case we have
m(X) + m(Y ) > m(X © Y ). Thus if X and Y are not disjoint, the
equality in (C) does not hold. Our proof shows that in general we have
(C ) For any two sets X and Y , m(X ∪Y ) = m(X)+m(Y )’m(X ©Y ).
Since the probabilities for statements are obtained directly from the
probability measure m(X), any property of m(X) can be translated into
a property about the probability of statements. For example, the above
properties become, when expressed in terms of statements,
(a) Pr[p] = 0 if and only if p is logically false.
(b) 0 < Pr[p] < 1 for any statement p.
(c) The equality
Pr[p ∨ q] = Pr[p] + Pr[q]
holds and only if p and q are inconsistent.
(c ) For any two statements p and q,

Pr[p ∨ q] = Pr[p] + Pr[q] ’ Pr[p § q].

Another property of a probability measure which is often useful in
computation is
˜
(D) m(X) = 1 ’ m(X),
or, in the language of statements,
(d) Pr[¬p] = 1 ’ Pr[p].
The proofs of (D) and (d) are left as an exercise (see Exercise 17).
It is important to observe that our probability measure assigns prob-
ability 0 only to statements which are logically false, i.e., which are false
for every logical possibility. Hence, a prediction that such a statement
89
4.2. PROPERTIES OF A PROBABILITY MEASURE

will be true is certain to be wrong. Similarly, a statement is assigned
probability 1 only if it is true in every case, i.e., logically true. Thus
the prediction that a statement of this type will be true is certain to be
correct. (While these properties of a probability measure seem quite
natural, it is necessary, when dealing with in¬nite possibility sets, to
weaken them slightly. We consider in this book only the ¬nite possibil-
ity sets.)
We shall now discuss the interpretation of probabilities that are not
0 or 1. We shall give only some intuitive ideas that are commonly
held concerning probabilities. While these ideas can be made mathe-
matically more precise, we o¬er them here only as a guide to intuitive
thinking.
Suppose that, relative to a given experiment, a statement has been
assigned probability p. From this it is often inferred that if a sequence of
such experiments is performed under identical conditions, the fraction
of experiments which yield outcomes making the statement true would
be approximately p. The mathematical version of this is the “law of
large numbers” of probability theory (which will be treated in Section
4.10). In cases where there is no natural way to assign a probability
measure, the probability of a statement is estimated experimentally.
A sequence of experiments is performed and the fraction of the ex-
periments which make the statement true is taken as the approximate
probability for the statement.
A second and related interpretation of probabilities is concerned
with betting. Suppose that a certain statement has been assigned prob-
ability p. We wish to o¬er a bet that the statement will in fact turn
out to be true. We agree to give r dollars if the statement does not
turn out to be true, provided that we receive s dollars if it does turn
out to be true. What should r and s be to make the bet fair? If it were
true that in a large number of such bets we would win s a fraction p
of the times and lose r a fraction 1 ’ p of the time, then our average
winning per bet would be sp ’ r(1 ’ p). To make the bet fair we should
make this average winning 0. This will be the case if sp = r(1 ’ p)
or if r/s = p/(1 ’ p). Notice that this determines only the ratio of r
and s. Such a ratio, written r : s, is said to give odds in favor of the
statement.
De¬nition. The odds in favor of an outcome are r : s (r to s), if the
probability of the outcome is p, and r/s = p/(1 ’ p). Any two numbers
having the required ratio may be used in place of r and s. Thus 6 : 4
odds are the same as 3 : 2 odds.
90 CHAPTER 4. PROBABILITY THEORY

Example 4.3 Assume that a probability of 3 has been assigned to a
4
certain horse winning a race. Then the odds for a fair bet would be
3 1
: 4 . These odds could be equally well written as 3 : 1, 6 : 2 or 12 : 4,
4
etc. A fair bet would be to agree to pay $3 if the horse loses and receive
$1 if the horse wins. Another fair bet would be to pay $6 if the horse
™¦
loses and win $2 if the horse wins.


Exercises
1 1
1. Let p and q be statements such that Pr[p § q] = 4 , Pr[¬p] = 3 ,
1
and Pr[q] = 2 . What is Pr[p ∨ q]?

11
[Ans. .]
12


2. Using the result of Exercise 1, ¬nd Pr[¬p § ¬q].
1
and Pr[q] = 2 . Are
3. Let p and q be statements such that Pr[p] = 2 3
p and q consistent?

[Ans. Yes.]

4. Show that, if Pr[p] + Pr[q] > 1, then p and q are consistent.

5. A student is worried about his or her grades in English and Art.
The student estimates that the probability of passing English is
.4, the probability of passing at least one course with probability
.6, but that the probability of 1 of passing both courses is only
.1? What is the probability that the student will pass Art?

[Ans. .3.]

6. Given that a school has grades A, B, C, D, and F, and that a
student has probability .9 of passing a course, and .6 of getting a
grade lower than B, what is the probability that the student will
get a C or D?

1
[Ans. .]
2


7. What odds should a person give on a bet that a six will turn up
when a die is thrown?
91
4.2. PROPERTIES OF A PROBABILITY MEASURE

8. Referring to Example 4.2, what odds should the man be willing
to give for a bet that either A or B will come in ¬rst?
9. Prove that if the odds in favor of a given statement are r : s, then
the probability that the statement will be true is r/(r + s).
10. Using the result of Exercise 9 and the de¬nition of “odds”, show
that if the odds are r : s that a statement is true, then the odds
are s : r that it is false.
11. A gambler is willing to give 5 : 4 odds that the Dodgers will win
the World Series. What must the probability of a Dodger victory
be for this to be a fair bet?
5
[Ans. .]
9

12. A statistician has found through long experience that if he or she
washes the car, it rains the next day 85 per cent of the time.
What odds should the statistician give that this will occur next
time?
13. A gambler o¬ers 1 : 3 odds that A will occur, 1 : 2 odds that B
will occur. The gambler knows that A and B cannot both occur.
What odds should he or she give that A or B will occur?

[Ans. 7 : 5.]

14. A gambler o¬ers 3 : 1 odds that A will occur, 2 : 1 odds that B
will occur. The gambler knows that A and B cannot both occur.
What odds should he or she give that A or B will occur?
15. Show from the de¬nition of a probability measure that m(X) = 1
if and only if X = U .
16. Show from the de¬nition of a probability measure that properties
(A), (B) of the text are true.
17. Prove property (D) of the text. Why does property (d) follow
from this property?
18. Prove that if R, S, and T are three sets that have no element in
common,

m(R ∪ S ∪ T ) = m(R) + m(S) + m(T ).
92 CHAPTER 4. PROBABILITY THEORY

19. If X and Y are two sets such that X is a subset of Y , prove that
m(X) ¤ m(Y ).

20. If p and q are two statements such that p implies q, prove that
Pr[p] ¤ Pr[q].

21. Suppose that you are given n statements and each has been as-
signed a probability less than or equal to r. Prove that the prob-
ability of the disjunction of these statements is less than or equal
to nr.

22. The following is an alternative proof of property (C ) of the text.
Give a reason for each step.

˜ ˜
(a) X ∪ Y = (X © Y ) ∪ (X © Y ) ∪ (X © Y ).
˜ ˜
(b) m(X ∪ Y ) = m(X © Y ) + m(X © Y ) + m(X © Y ).
(c) m(X ∪ Y ) = m(X) + m(Y ) ’ m(X © Y ).

23. If X, Y , and Z are any three sets, prove that, for any probability
measure,

m(X ∪ Y ∪ Z) = m(X) + m(Y ) + m(Z)
’m(X © Y ) ’ m(Y © Z) ’ m(X © Z)
+m(X © Y © Z).

24. Translate the result of Exercise 23 into a result concerning three
statements p, q, and r.

25. A man o¬ers to bet “dollars to doughnuts” that a certain event
will take place. Assuming that a doughnut costs a nickel, what
must the probability of the event be for this to be a fair bet?

20
[Ans. .]
21


26. Show that the inclusion-exclusion formula 3.2 is true is n is re-
placed by m. Apply this result to

Pr[p1 ∨ p2 ∨ . . . ∨ pn ].
93
4.3. THE EQUIPROBABLE MEASURE

4.3 The equiprobable measure
We have already seen several examples where it was natural to assign
the same weight to all possibilities in determining the appropriate prob-
ability measure. The probability measure determined in this manner
is called the equiprobable measure. The measure of sets in the case of
the equiprobable measure has a very simple form. In fact, if U has n
elements and if the equiprobable measure has been assigned, then for
any set X, m(X) is r/n, where r is the number of elements in the set
X. This is true since the weight of each element in X is 1/n, and hence
the sum of the weights of elements of X is r/n.
The particularly simple form of the equiprobable measure makes
it easy to work with. In view of this, it is important to observe that
a particular choice for the set of possibilities in a given situation may
lead to the equiprobable measure, while some other choice will not. For
example, consider the case of two throws of an ordinary coin. Suppose
that we are interested in statements about the number of heads which
occur. If we take for the possibility set the set U = {HH, HT, TH, TT}
then it is reasonable to assign the same weight to each outcome, and
we are led to the equiprobable measure. If, on the other hand, we
were to take as possible outcomes the set U = {no H, one H, two H},
it would not be natural to assign the same weight to each outcome,
since one head can occur in two di¬erent ways, while each of the other
possibilities can occur in only one way.

Example 4.4 Suppose that we throw two ordinary dice. Each die can
turn up a number from 1 to 6; hence there are 6 · 6 possibilities. We
1
assign weight 36 to each possibility. A prediction that is true in j cases
will then have probability j/36. For example, “The sum of the dice is
5” will be true if we get 1 + 4, 2 + 3, 3 + 2, or 4 + 1. Hence the
probability that the sum of the dice is 5 is 36 = 1 . The sum can be 12
4
9
1
in only one way, 6 + 6. Hence the probability that the sum is 12 is 36 .
™¦


Example 4.5 Suppose that two cards are drawn successively from a
deck of cards. What is the probability that both are hearts? There
are 52 possibilities for the ¬rst card, and for each of these there are
51 possibilities for the second. Hence there are 52 · 51 possibilities for
the result of the two draws. We assign the equiprobable measure. The
statement “The two cards are hearts” is true in 13 · 12 of the 52 · 51
94 CHAPTER 4. PROBABILITY THEORY

possibilities. Hence the probability of this statement is 13·12/(52·51) =
1
™¦
.
17



Example 4.6 Assume that, on the basis of a predictive index applied
to students A, B, and C when entering college, it is predicted that after
four years of college the scholastic record of A will be the highest, C the
second highest, and B the lowest of the three. Suppose, in fact, that
these predictions turn out to be exactly correct. If the predictive index
has no merit at all and hence the predictions amount simply to guessing,
what is the probability that such a prediction will be correct? There
are 3! = 6 orders in which the men might ¬nish. If the predictions were
really just guessing, then we would assign an equal weight to each of the
six outcomes. In this case the probability that a particular prediction is
1
true is 6 . Since this probability is reasonably large, we would hesitate
to conclude that the predictive index is in fact useful, on the basis
of this one experiment. Suppose, on the other hand, it predicted the
order of six men correctly. Then a similar analysis would show that,
1 1
by guessing, the probability is 6! = 720 that such a prediction would be
correct. Hence, we might conclude here that there is strong evidence
™¦
that the index has some merit.


Exercises
1. A letter is chosen at random from the word “random”. What is
the probability that it is an n? That it is a vowel?

11
[Ans. 6 ; 3 .]

2. An integer between 3 and 12 inclusive is chosen at random. What
is the probability that it is an even number? That it is even and
divisible by three?

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

(a) What is the probability that it is either a heart or the king
of clubs?
7
[Ans. .]
26

(b) What is the probability that it is either the queen of hearts
or an honor card (i.e., ten, jack, queen, king, or ace)?
95
4.3. THE EQUIPROBABLE MEASURE

5
[Ans. .]
13

4. A word is chosen at random from the set of words

U = {men, bird, ball, ¬eld, book}.

Let p, q, and r be the statements:

p: The word has two vowels.

q: The ¬rst letter of the word is b.

r: The word rhymes with cook.

Find the probability of the following statements.

(a) p.
(b) q.
(c) r.
(d) p § q.
(e) (p ∨ q) § ¬r.
(f) p ’ q.
4
[Ans. .]
5

5. A single die is thrown. Find the probability that

(a) An odd number turns up.
(b) The number which turns up is greater than two.
(c) A seven turns up.

6. In the Primary voting example of Section 2.1, assume that all 36
possibilities in the elections are equally likely. Find

(a) The probability that candidate A wins more states than ei-
ther B or C.
7
[Ans. .]
18

(b) That all the states are won by the same candidate.
1
[Ans. .]
36

(c) That every state is won by a di¬erent candidate.
96 CHAPTER 4. PROBABILITY THEORY

[Ans. 0.]

7. A single die is thrown twice. What value for the sum of the two
outcomes has the highest probability? What value or values of
the sum has the lowest probability of occurring?

8. Two boys and two girls are placed at random in a row for a
picture. What is the probability that the boys and girls alternate
in the picture?

1
[Ans. .]
3


9. A certain college has 500 students and it is known that
300 read French.
200 read German.
50 read Russian.
20 read French and Russian.
30 read German and Russian.
20 read German and French.
10 read all three languages.
If a student is chosen at random from the school, what is the
probability that the student

(a) Reads two and only two languages?
(b) Reads at least one language?

10. Suppose that three people enter a restaurant which has a row
of six seats. If they choose their seats at random, what is the
probability that they sit with no seats between them? What is
the probability that there is at least one empty seat between any
two of them?

11. Find the probability of obtaining each of the following poker
hands. (A poker hand is a set of ¬ve cards chosen at random
from a deck of 52 cards.)

(a) Royal ¬‚ush (ten, jack, queen, king, ace in a single suit).
52
[Ans. 4/ = .0000015.]
5

(b) Straight ¬‚ush (¬ve in a sequence in a single suit, but not a
royal ¬‚ush).
97
4.3. THE EQUIPROBABLE MEASURE

52
[Ans. (40 ’ 4)/ = .000014.]
5

(c) Four of a kind (four cards of the same face value).
52
[Ans. 624/ = .00024.]
5

(d) Full house (one pair and one triple of the same face value).
52
[Ans. 3744/ = .0014.]
5

(e) Flush (¬ve cards in a single suit but not a straight or royal
¬‚ush).
52
[Ans. (5148 ’ 40)/ = .0020.]
5

(f) Straight (¬ve cards in a row, not all of the same suit).
52
[Ans. (10, 240 ’ 40)/ = .0039.]
5

(g) Straight or better.
[Ans. .0076.]

12. If ten people are seated at a circular table at random, what is
the probability that a particular pair of people are seated next to
each other?

2
[Ans. .]
9


13. A room contains a group of n people who are wearing badges
numbered from 1 to n. If two people are selected at random, what
is the probability that the larger badge number is a 3? Answer
this problem assuming that n = 5, 4, 3, 2.

112
[Ans. ; ; ; 0.]
533


14. In Exercise 13, suppose that we observe two men leaving the room
and that the larger of their badge numbers is 3. What might we
guess as to the number of people in the room?

15. Find the probability that a bridge hand will have suits of

(a) 5, 4, 3, and 1 cards.
4!(13)(13)(13)(13)
[Ans. = .129.]
5 4 3 1
(52)
13
98 CHAPTER 4. PROBABILITY THEORY

(b) 6, 4, 2, and 1 cards.
[Ans. .047.]
(c) 4, 4, 3, and 2 cards.
[Ans. .216.]
(d) 4, 3, 3, and 3 cards.
[Ans. .105.]

16. There are 52 = 6.5 — 1011 possible bridge hands. Find the
13
probability that a bridge hand dealt at random will be all of one
suit. Estimate roughly the number of bridge hands dealt in the
entire country in a year. Is it likely that a hand of all one suit
will occur sometime during the year in the United States?

Supplementary exercises.

17. Find the probability of not having a pair in a hand of poker.

18. Find the probability of a “bust” hand in poker. [Hint: A hand
is a “bust” if there is no pair, and it is neither a straight nor a
¬‚ush.]

[Ans. .5012.]

19. In poker, ¬nd the probability of having

(a) Exactly one pair.
[Ans. .4226.]
(b) Two pairs.
[Ans. .0475.]
(c) Three of a kind.
[Ans. .0211.]

20. Verify from Exercises 11, 18, 19 that the probabilities for all pos-
sible poker hands add up to one (within a rounding error).

21. A certain French professor announces that he or she will select
three out of eight pages of text to put on an examination and that
each student can choose one of these three pages to translate.
99
4.4. TWO NONINTUITIVE EXAMPLES

(a) What is the maximum number of pages that a student should
prepare in order to be certain of being able to translate a
page that he or she has studied?
(b) Smith decides to study only four of the eight pages. What
is the probability that one of these four pages will appear on
the examination?


4.4 Two nonintuitive examples
There are occasions in probability theory when one ¬nds a problem for
which the answer, based on probability theory, is not at all in agreement
with one™s intuition. It is usually possible to arrange a few wagers that
will bring one™s intuition into line with the mathematical theory. A
particularly good example of this is provided by the matching birthdays
problem.
Assume that we have a room with r people in it and we propose
the bet that there are at least two people in the room having the same
birthday, i.e., the same month and day of the year. We ask for the
value of r which will make this a fair bet. Few people would be willing
to bet even money on this wager unless there were at least 100 people
in the room. Most people would suggest 150 as a reasonable number.
However, we shall see that with 150 people the odds are approximately
4,100,000,000,000,000 to 1 in favor of two people having the same birth-
day, and that one should be willing to bet even money with as few as
23 people in the room.
Let us ¬rst ¬nd the probability that in a room with r people, no two
have the same birthday. There are 365 possibilities for each person™s
birthday (neglecting February 29). There are then 365r possibilities
for the birthdays of r people. We assume that all these possibilities
are equally likely. To ¬nd the probability that no two have the same
birthday we must ¬nd the number of possibilities for the birthdays
which have no day represented twice. The ¬rst person can have any of
365 days for his or her birthday. For each of these, if the second person
is to have a di¬erent birthday, there are only 364 possibilities for his
or her birthday. For the third person, there are 363 possibilities if he
or she is to have a di¬erent birthday than the ¬rst two, etc. Thus the
probability that no two people have the same birthday in a group of r
people is
365 · 364 · . . . · (365 ’ r + 1)
qr = .
365r
100 CHAPTER 4. PROBABILITY THEORY




Figure 4.1: ™¦

The probability that at least two people have the same birthday is
then pr = 1 ’ qr . In Figure 4.1 the values of pr and the odds for a fair
bet, pr : (1 ’ pr ) are given for several values of r.
We consider now a second problem in which intuition does not lead
to the correct answer. A hat-check clerk has checked n hats, but they
have become hopelessly scrambled. The clerk hands back the hats at
random. What is the probability that at least one head gets its own
hat? For this problem some people™s intuition would lead them to
guess that for a large number of hats this probability should be small,
while others guess that it should be large. Few people guess that the
probability is neither large nor small and essentially independent of the
number of hats involved.
101
4.4. TWO NONINTUITIVE EXAMPLES

Let pj be the statement “the jth head gets its own hat back”. We
wish to ¬nd Pr[p1 ∨ p2 ∨ . . . ∨ pn ]. We know from Exercise 26 that
a probability of this form can be found from the inclusion-exclusion
formula. We must add all probabilities of the form Pr[pi ], then subtract
the sum of all probabilities of the form Pr[pi § pj ], then add the sum of
all probabilities of the form Pr[pi § pj § pk ], etc.
However, each of these probabilities represents the probability that
a particular set of heads get their own hats back. These probabilities
are very easy to compute. Let us ¬nd the probability that out of n
heads some particular m of them get back their own hats. There are n!
ways that the hats can be returned. If a particular m of them are to get
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)!
.
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.

<<

. 3
( 6)



>>