<< . .

. 12
( : 20)

. . >>

16. Prove that for any three statements p, q, and r,

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

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.

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

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

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-
comes, and the probabilities for each of these outcomes is 2 regardless

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

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

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

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
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
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
assumption that urn 1 is chosen. Similarly we assign p1,B = 2 , p2,W = 3 ,
p2,B = 2 . We indicate these probabilities on their possibility tree in
Figure 4.4. The probability that a white ball is drawn is then found

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¬.
Machine A pays o¬ each time with probability 2 , and machine B with
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] =

Figure 4.5: ™¦

Figure 4.6: ™¦

The truth set of the statement p § q consists of a single path which has
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
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.)

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
winning a game when B is the opponent 3 . The probability of
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?

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

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

(b) That we play the same machine the second time if and only
if we won the ¬rst time.
[Ans. .]

10. A chess player plays three successive games of chess. The player™s
psychological makeup is such that the probability of winning a
given game is ( 2 )k+1 , where k is the number of games won so far.
(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
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
President and his or her Vice President are sure to be nominated
and have probability 3 of being elected again. If the President
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
Vice President will be re-elected?

[Ans. .]

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?

<< . .

. 12
( : 20)

. . >>