ńņš. 3 |

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 |