Page 489 - Discrete Mathematics and Its Applications

468 7 / Discrete Probability

31. Find the probability that a family with five children does b) Suppose that the honest observer tells us that at least
not have a boy, if the sexes of children are independent one die came up five. What is the probability the sum
and if of the numbers that came up on the dice is seven, given
a) a boy and a girl are equally likely. this information?
∗∗
b) the probability of a boy is 0.51. 39. This exercise employs the probabilistic method to prove a
result about round-robin tournaments. In a round-robin
c) the probability that the ith child is a boy is
tournament with m players, every two players play one
0.51 − (i/100).
game in which one player wins and the other loses.
32. Find the probability that a randomly generated bit string
We want to find conditions on positive integers m
of length 10 begins witha1or ends with a 00 for the same
and k with k< m such that it is possible for the outcomes
conditions as in parts (a), (b), and (c) of Exercise 30, if
of the tournament to have the property that for every set
bits are generated independently.
of k players, there is a player who beats every member
33. Find the probability that the first child of a family with in this set. So that we can use probabilistic reasoning to
five children is a boy or that the last two children of the draw conclusions about round-robin tournaments, we as-
family are girls, for the same conditions as in parts (a), sume that when two players compete it is equally likely
(b), and (c) of Exercise 31. that either player wins the game and we assume that the
outcomes of different games are independent. Let E be
34. Find each of the following probabilities when n indepen-
the event that for every set S with k players, where k is
dent Bernoulli trials are carried out with probability of
a positive integer less than m, there is a player who has
success p.
beaten all k players in S.
a) the probability of no successes
m
( k )
b) the probability of at least one success a) Show that p(E) ≤ j=1 p(F j ), where F j is the event
that there is no player who beats all k players from the
c) the probability of at most one success
m
jth set in a list of the sets of k players.
d) the probability of at least two successes k −k m−k
b) Show that the probability of F j is (1−2 ) .
35. Find each of the following probabilities when n indepen-
c) Conclude from parts (a) and (b) that p(E) ≤
dent Bernoulli trials are carried out with probability of −k m−k
m
success p. k (1 − 2 ) and, therefore, that there must
be a tournament with the described property if
a) the probability of no failures −k m−k
m
k (1−2 ) < 1.
b) the probability of at least one failure d) Use part (c) to find values of m such that there is a
c) the probability of at most one failure tournament with m players such that for every set S
d) the probability of at least two failures of two players, there is a player who has beaten both
players in S. Repeat for sets of three players.
36. Use mathematical induction to prove that if
∗
E 1 ,E 2 ,...,E n is a sequence of n pairwise disjoint 40. Devise a Monte Carlo algorithm that determines whether
events in a sample space S, where n is a positive integer, a permutation of the integers 1 through n has already been
n n sorted (that is, it is in increasing order), or instead, is a ran-
then p( E i ) = p(E i ).
i=1 i=1
dom permutation. A step of the algorithm should answer
∗ 37. (Requires calculus) Show that if E 1 ,E 2 ,... is an infinite
“true” if it determines the list is not sorted and “unknown”
sequence of pairwise disjoint events in a sample space S,
∞ ∞ otherwise.After k steps, the algorithm decides that the in-
then p( E i ) = p(E i ).[Hint: Use Exercise 36
i=1 i=1 tegers are sorted if the answer is “unknown” in each step.
and take limits.]
Show that as the number of steps increases, the proba-
38. A pair of dice is rolled in a remote location and when you bility that the algorithm produces an incorrect answer is
ask an honest observer whether at least one die came up extremely small. [Hint: For each step, test whether cer-
six, this honest observer answers in the affirmative. tain elements are in the correct order. Make sure these
a) What is the probability that the sum of the numbers tests are independent.]
that came up on the two dice is seven, given the infor- 41. Use pseudocode to write out the probabilistic primality
mation provided by the honest observer? test described in Example 16.
7.3 Bayes’Theorem
Introduction
There are many times when we want to assess the probability that a particular event occurs on
the basis of partial evidence. For example, suppose we know the percentage of people who have
a particular disease for which there is a very accurate diagnostic test. People who test positive for