Pr[p § q § r] = Pr[p] · Pr[q|p] · Pr[r|p § q].

17. A coin is thrown twice. Let p be the statement “Heads turns up

on the ¬rst toss” and q the statement “Heads turns up on the

second toss”. Show that it is possible to assign a measure to the

possibility space {HH, HT, TH, TT} so that these statements are

not independent.

18. A multiple-choice test question lists ¬ve alternative answers, of

which just one is correct. If a student has done the homework,

then he or she is certain to identify the correct answer; otherwise,

the student chooses an answer at random. Let p be the statement

“The student does the homework” and q the statement “The

student answers the question correctly”. Let Pr[p] = a.

(a) Find a formula for Pr[p|q] in terms of a.

(b) Show that Pr[p|q] ≥ Pr[p] for all values of a. When does the

equality hold?

19. A coin is weighted so that heads has probability .7, tails has

probability .2, and it stands on edge with probability .1. What

is the probability that it does not come up heads, given that it

does not come up tails?

1

[Ans. .]

8

20. A card is drawn at random from a deck of playing cards. Are the

following pairs of statements independent?

(a) p: A jack is drawn. q: A black card is drawn.

(b) p: An even numbered heart is drawn. q: A red card smaller

than a ¬ve is drawn.

21. A simple genetic model for the color of a person™s eyes is the

following: There are two kinds of color-determining genes, B and

b, and each person has two color-determining genes. If both are

b, he or she has blue eyes; otherwise he or she has brown eyes.

Assume that one-quarter of the people have two B genes, one-

quarter of the people have two b genes, and the rest have one B

gene and one b gene.

111

4.6. FINITE STOCHASTIC PROCESSES

(a) If a person has brown eyes, what is the probability that he

or she has two B genes?

Assume that a child™s mother and father have brown eyes

and blue eyes, respectively.

(b) What is the probability that the child will have brown eyes?

(c) If the child has brown eyes, what is the probability that the

father has two B genes?

1

[Ans. .]

2

22. Three red, three green, and three blue balls are to be put into

three urns, with at least two balls in each urn. Then an urn is

selected at random and two balls withdrawn.

(a) How should the balls be put in the urns in order to maximize

the probability of drawing two balls of di¬erent color? What

is the probability?

[Ans. 1.]

(b) How should the balls be put in the urns in order to maximize

the probability of withdrawing a red and a green ball? What

is the maximum probability?

7

[Ans. .]

10

4.6 Finite stochastic processes

We consider here a very general situation which we will specialize in

later sections. We deal with a sequence of experiments where the out-

come on each particular experiment depends on some chance element.

Any such sequence is called a stochastic process. (The Greek word

“stochos” means “guess”.) We shall assume a ¬nite number of exper-

iments and a ¬nite number of possibilities for each experiment. We

assume that, if all the outcomes of the experiments which precede a

given experiment were known, then both the possibilities for this ex-

periment and the probability that any particular possibility will occur

would be known. We wish to make predictions about the process as a

whole. For example, in the case of repeated throws of an ordinary coin

we would assume that on any particular experiment we have two out-

1

comes, and the probabilities for each of these outcomes is 2 regardless

112 CHAPTER 4. PROBABILITY THEORY

Figure 4.3: ™¦

of any other outcomes. We might be interested, however, in the proba-

bilities of statements of the form, “More than two-thirds of the throws

result in heads”, or “The number of heads and tails which occur is the

same”, etc. These are questions which can be answered only when a

probability measure has been assigned to the process as a whole. In this

section we show how a probability measure can be assigned, using the

given information. In the case of coin tossing, the probabilities (hence

also the possibilities) on any given experiment do not depend upon the

previous results. We will not make any such restriction here since the

assumption is not true in general.

We shall show how the probability measure is constructed for a par-

ticular example, and the procedure in the general case is similar. We

assume that we have a sequence of three experiments, the possibilities

for which are indicated in Figure 4.3. The set of all possible outcomes

which might occur on any of the experiments is represented by the set

{a, b, c, d, e, f }. Note that if we know that outcome b occurred on the

¬rst experiment, then we know that the possibilities on experiment two

are {a, e, d}. Similarly, if we know that b occurred on the ¬rst experi-

ment and a on the second, then the only possibilities for the third are

{c, f }. We denote by pa the probability that the ¬rst experiment re-

sults in outcome a, and by pb the probability that outcome b occurs in

the ¬rst experiment. We denote by pb,d the probability that outcome

d occurs on the second experiment, which is the probability computed

on the assumption that outcome b occurred on the ¬rst experiment.

Similarly for pb,a ,pb,e ,pa,a ,pa,c . We denote by pbd,c the probability that

outcome c occurs on the third experiment, the latter probability being

113

4.6. FINITE STOCHASTIC PROCESSES

computed on the assumption that outcome b occurred on the ¬rst ex-

periment and d on the second. Similarly for pba,c ,pba,f , etc. We have

assumed that these numbers are given and the fact that they are proba-

bilities assigned to possible outcomes would mean that they are positive

and that pa + pb = 1, pb,a + pb,e + pb,d = 1, and pbd,a + pbd,c = 1, etc.

It is convenient to associate each probability with the branch of

the tree that connects to the branch point representing the predicted

outcome. We have done this in Figure 4.3 for several branches. The

sum of the numbers assigned to branches from a particular branch point

is 1, e.g., pb,a + pb,e + pb,d = 1.

A possibility for the sequence of three experiments is indicated by a

path through the tree. We de¬ne now a probability measure on the set

of all paths. We call this a tree measure. To the path corresponding to

outcome b on the ¬rst experiment, d on the second, and c on the third,

we assign the weight pb ·pb,d ·pbd,c . That is the product of the probabilities

associated with each branch along the path being considered. We ¬nd

the probability for each path through the tree.

Before showing the reason for this choice, we must ¬rst show that it

determines a probability measure, in other words, that the weights are

positive and the sum of the weights is 1. The weights are products of

positive numbers and hence positive. To see that their sum is 1 we ¬rst

¬nd the sum of the weights of all paths corresponding to a particular

outcome, say b, on the ¬rst experiment and a particular outcome, say

d, on the second. We have

pb · pb,d · pbd,a + pb · pb,d · pbd,c = pb · pb,d [pbd,a + pbd,c ] = pb · pb,d .

For any other ¬rst two outcomes we would obtain a similar result.

For example, the sum of the weights assigned to paths corresponding

to outcome a on the ¬rst experiment and c on the second is pa · pa,c .

Notice that when we have veri¬ed that we have a probability measure,

this will be the probability that the ¬rst outcome results in a and the

second experiment results in c.

Next we ¬nd the sum of the weights assigned to all the paths cor-

responding to the cases where the outcome of the ¬rst experiment is

b. We ¬nd this by adding the sums corresponding to the di¬erent pos-

sibilities for the second experiment. But by our preceding calculation

this is

pb · pb,a + pb · pb,e + pb · pb,d = pb [pb,a + pb,e + pb,d ] = pb .

Similarly, the sum of the weights assigned to paths corresponding

to the outcome a on the ¬rst experiment is pa . Thus the sum of all

114 CHAPTER 4. PROBABILITY THEORY

weights is pa + pb = 1. Therefore we do have a probability measure.

Note that we have also shown that the probability that the outcome of

the ¬rst experiment is a has been assigned probability pa in agreement

with our given probability.

To see the complete connection of our new measure with the given

probabilities, let Xj = z be the statement “The outcome of the jth

experiment was z”. Then the statement [X1 = b § X2 = d § X3 = c] is

a compound statement that has been assigned probability pb · pb,d · pbd,c .

The statement [X1 = b§X2 = d] we have noted has been assigned prob-

ability pb · pb,d and the statement [X1 = b] has been assigned probability

pb . Thus

pb · pb,d · pbd,c

Pr[X3 = c|X2 = d § X1 = b] = = pbd,c ,

pb · pb,d

pb · pb,d

Pr[X2 = d|X1 = b] = = pb,d .

pb

Thus we see that our probabilities, computed under the assumption

that previous results were known, become the corresponding condi-

tional probabilities when computed with respect to the tree measure.

It can be shown that the tree measure which we have assigned is the

only one which will lead to this agreement. We can now ¬nd the proba-

bility of any statement concerning the stochastic process from our tree

measure.

Example 4.11 Suppose that we have two urns. Urn 1 contains two

black balls and three white balls. Urn 2 contains two black balls and

one white ball. An urn is chosen at random and a ball chosen from this

urn at random. What is the probability that a white ball is chosen?

A hasty answer might be 1 since there are an equal number of black

2

and white balls involved and everything is done at random. However,

it is hasty answers like this (which is wrong) which show the need for

a more careful analysis.

We are considering two experiments. The ¬rst consists in choosing

the urn and the second in choosing the ball. There are two possibilities

for the ¬rst experiment, and we assign p1 = p2 = 1 for the probabilities

2

of choosing the ¬rst and the second urn, respectively. We then assign

p1,W = 3 for the probability that a white ball is chosen, under the

5

assumption that urn 1 is chosen. Similarly we assign p1,B = 2 , p2,W = 3 ,

1

5

p2,B = 2 . We indicate these probabilities on their possibility tree in

3

Figure 4.4. The probability that a white ball is drawn is then found

115

4.6. FINITE STOCHASTIC PROCESSES

Figure 4.4: ™¦

from the tree measure as the sum of the weights assigned to paths which

lead to a choice of a white ball. This is 1 · 5 + 1 · 1 = 15 .

3 7

™¦

2 23

Example 4.12 Suppose that a drunkard leaves a bar which is on a

corner which he or she knows to be one block from home. He or she is

unable to remember which street leads home, and proceeds to try each

of the streets at random without ever choosing the same street twice

until he or she goes on the one which leads home. What possibilities

are there for the trip home, and what is the probability for each of

these possible trips? We label the streets A, B, C, and Home. The

possibilities together with typical probabilities are given in Figure 4.5.

The probability for any particular trip, or path, is found by taking the

™¦

product of the branch probabilities.

Example 4.13 Assume that we are presented with two slot machines,

A and B. Each machine pays the same ¬xed amount when it pays o¬.

1

Machine A pays o¬ each time with probability 2 , and machine B with

1

probability 4 . We are not told which machine is A. Suppose that we

choose a machine at random and win. What is the probability that

we chose machine A? We ¬rst construct the tree (Figure 4.6) to show

the possibilities and assign branch probabilities to determine a tree

measure. Let p be the statement “Machine A was chosen” and q be

the statement “The machine chosen paid o¬”. Then we are asked for

Pr[p § q]

Pr[p|q] =

Pr[q]

116 CHAPTER 4. PROBABILITY THEORY

Figure 4.5: ™¦

Figure 4.6: ™¦

117

4.6. FINITE STOCHASTIC PROCESSES

The truth set of the statement p § q consists of a single path which has

1

been assigned weight 4 . The truth set of the statement q consists of

two paths, and the sum of the weights of these paths is 1 · 2 + 1 · 1 = 8 .

1 3

2 24

Thus Pr[p|q] = 2 . Thus if we win, it is more likely that we have machine

3

A than B and this suggests that next time we should play the same

machine. If we lose, however, it is more likely that we have machine

B than A, and hence we would switch machines before the next play.

™¦

(See Exercise 9.)

Exercises

1. The fractions of Republicans, Democrats, and Independent voters

in cities A and B are

City A: .30 Republican, .40 Democratic, .30 Independent;

City B: .40 Republican, .50 Democratic, .10 Independent.

A city is chosen at random and two voters are chosen succes-

sively and at random from the voters of this city. Construct a

tree measure and ¬nd the probability that two Democrats are

chosen. Find the probability that the second voter chosen is an

Independent voter.

[Ans. .205; .2.]

2. A coin is thrown. If a head turns up, a die is rolled. If a tail

turns up, the coin is thrown again. Construct a tree measure to

represent the two experiments and ¬nd the probability that the

die is thrown and a six turns up.

3. An athlete wins a certain tournament if he or she can win two

consecutive games out of three played alternately with two oppo-

nents A and B. A is a better player than B. The probability of

2

winning a game when B is the opponent 3 . The probability of

1

winning a game when A is the opponent is only 3 . Construct a

tree measure for the possibilities for three games, assuming that

he or she plays alternately but plays A ¬rst. Do the same assum-

ing that he or she plays B ¬rst. In each case ¬nd the probability

that he or she will win two consecutive games. Is it better to play

two games against the strong player or against the weaker player?

118 CHAPTER 4. PROBABILITY THEORY

10 8

[Ans. ;; better to play strong player twice.]

27 27

4. Construct a tree measure to represent the possibilities for four

throws of an ordinary coin. Assume that the probability of a

head on any toss is 1 regardless of any information about other

2

throws.

5. A student claims to be able to distinguish beer from ale. The

student is given a series of three tests. In each test, the student

is given two cans of beer and one of ale and asked to pick out

the ale. If the student gets two or more correct we will admit

the claim. Draw a tree to represent the possibilities (either right

or wrong) for the student™s answers. Construct the tree measure

which would correspond to guessing and ¬nd the probability that

the claim will be established if the student guesses on every trial.

6. A box contains three defective light bulbs and seven good ones.

Construct a tree to show the possibilities if three consecutive

bulbs are drawn at random from the box (they are not replaced

after being drawn). Assign a tree measure and ¬nd the probabil-

ity that at least one good bulb is drawn out. Find the probability

that all three are good if the ¬rst bulb is good.

119 5

[Ans. ; .]

120 12

7. In Example 4.12, ¬nd the probability that the drunkard reaches

home after trying at most one wrong street.

8. In Example 4.13, ¬nd the probability that machine A was chosen,

given that we lost.

9. In Example 4.13, assume that we make two plays. Find the prob-

ability that we win at least once under the assumption

(a) That we play the same machine twice.

19

[Ans. .]

32

(b) That we play the same machine the second time if and only

if we won the ¬rst time.

20

[Ans. .]

32

119

4.6. FINITE STOCHASTIC PROCESSES

10. A chess player plays three successive games of chess. The player™s

psychological makeup is such that the probability of winning a

1

given game is ( 2 )k+1 , where k is the number of games won so far.

1

(For instance, the probability of winning the ¬rst game is 2 , the

probability of winning the second game if the player has already

won the ¬rst game is 1 , etc.) What is the probability that the

4

player will win at least two of the three games?

11. Before a political convention, a political expert has assigned the

following probabilities. The probability that the President will

be willing to run again is 1 . If the President is willing to run, the

2

President and his or her Vice President are sure to be nominated

and have probability 3 of being elected again. If the President

5

1

does not run, the present Vice President has probability 10 of

being nominated, and any other presidential candidate has prob-

ability 1 of being elected. What is the probability that the present

2

Vice President will be re-elected?

13

[Ans. .]

40

12. There are two urns, A and B. Urn A contains one black and one

red ball. Urn B contains two black and three red balls. A ball is

chosen at random from urn A and put into urn B. A ball is then

drawn at random from urn B.

(a) What is the probability that both balls drawn are of the

same color?