Page 488 - Discrete Mathematics and Its Applications

7.2 Probability Theory 467

10. What is the probability of these events when we randomly 20. Find the smallest number of people you need to choose
select a permutation of the 26 lowercase letters of the En- at random so that the probability that at least one of them
glish alphabet? has a birthday today exceeds 1/2.
a) The first 13 letters of the permutation are in alphabet- 21. Find the smallest number of people you need to choose
ical order. at random so that the probability that at least two of them
b) a is the first letter of the permutation and z is the last were both born on April 1 exceeds 1/2.
letter.
∗ 22. February 29 occurs only in leap years. Years divisible
c) a and z are next to each other in the permutation. by 4, but not by 100, are always leap years. Years divisi-
d) a and b are not next to each other in the permutation.
e) a and z are separated by at least 23 letters in the per- ble by 100, but not by 400, are not leap years, but years
divisible by 400 are leap years.
mutation.
f) z precedes both a and b in the permutation. a) What probability distribution for birthdays should be
used to reflect how often February 29 occurs?
11. Suppose that E and F are events such that p(E) =
0.7 and p(F) = 0.5. Show that p(E ∪ F) ≥ 0.7 and b) Using the probability distribution from part (a), what
p(E ∩ F) ≥ 0.2. is the probability that in a group of n people at least
two have the same birthday?
12. Suppose that E and F are events such that p(E) =
0.8 and p(F) = 0.6. Show that p(E ∪ F) ≥ 0.8 and 23. What is the conditional probability that exactly four heads
p(E ∩ F) ≥ 0.4. appear when a fair coin is flipped five times, given that
the first flip came up heads?
13. Show that if E and F are events, then p(E ∩ F) ≥
p(E) + p(F) − 1. This is known as Bonferroni’s in- 24. What is the conditional probability that exactly four heads
equality. appear when a fair coin is flipped five times, given that
14. Use mathematical induction to prove the following gen- the first flip came up tails?
eralization of Bonferroni’s inequality: 25. What is the conditional probability that a randomly gen-
p(E 1 ∩ E 2 ∩ ··· ∩ E n ) erated bit string of length four contains at least two con-
secutive 0s, given that the first bit is a 1? (Assume the
≥ p(E 1 ) + p(E 2 ) + ··· + p(E n ) − (n − 1),
probabilities of a 0 and a 1 are the same.)
where E 1 ,E 2 ,...,E n are n events. 26. Let E be the event that a randomly generated bit string
15. Show that if E 1 ,E 2 ,...,E n are events from a finite sam- of length three contains an odd number of 1s, and let F
ple space, then be the event that the string starts with 1. Are E and F
independent?
p(E 1 ∪ E 2 ∪ ··· ∪ E n )
27. Let E and F be the events that a family of n children has
≤ p(E 1 ) + p(E 2 ) + ··· + p(E n ).
children of both sexes and has at most one boy, respec-
This is known as Boole’s inequality. tively. Are E and F independent if
16. Show that if E and F are independent events, then E a) n = 2? b) n = 4? c) n = 5?
and F are also independent events. 28. Assume that the probability a child is a boy is 0.51
17. If E and F are independent events, prove or disprove and that the sexes of children born into a family are
that E and F are necessarily independent events. independent. What is the probability that a family of five
In Exercises 18, 20, and 21 assume that the year has 366 days children has
and all birthdays are equally likely. In Exercise 19 assume it a) exactly three boys?
is equally likely that a person is born in any given month of b) at least one boy?
the year. c) at least one girl?
18. a) What is the probability that two people chosen at ran- d) all children of the same sex?
dom were born on the same day of the week? 29. Agroupofsixpeopleplaythegameof“oddpersonout”to
b) What is the probability that in a group of n people determine who will buy refreshments. Each person flips
chosen at random, there are at least two born on the a fair coin. If there is a person whose outcome is not the
same day of the week? same as that of any other member of the group, this per-
c) How many people chosen at random are needed to son has to buy the refreshments. What is the probability
make the probability greater than 1/2 that there are at that there is an odd person out after the coins are flipped
least two people born on the same day of the week?
once?
19. a) What is the probability that two people chosen at ran-
30. Find the probability that a randomly generated bit string
dom were born during the same month of the year?
b) What is the probability that in a group of n people of length 10 does not containa0if bits are independent
and if
chosen at random, there are at least two born in the
same month of the year? a) a 0 bit and a 1 bit are equally likely.
c) How many people chosen at random are needed to b) the probability that a bit isa1is 0.6.
i
make the probability greater than 1/2 that there are at c) the probability that the ithbitisa1is1/2 for
least two people born in the same month of the year? i = 1, 2, 3,..., 10.