Page 518 - Discrete Mathematics and Its Applications

Supplementary Exercises 497

b) What is the probability that the odd person out is de- b) What is the expected number of balls that land in a
cided with the kth flip? particular bin?
c) What is the expected number of flips needed to decide
c) What is the expected number of balls tossed until a
odd person out with n people?
particular bin contains a ball?
14. Suppose that p and q are primes and n = pq. What is the
∗ d) What is the expected number of balls tossed until all
probability that a randomly chosen positive integer less
bins contain a ball? [Hint: Let X i denote the number
than n is not divisible by either p or q?
of tosses required to have a ball land in an ith bin
∗ 15. Suppose that m and n are positive integers. What is the once i − 1 bins contain a ball. Find E(X i ) and use the
probability that a randomly chosen positive integer less linearity of expectations.]
than mn is not divisible by either m or n?
23. Suppose that A and B are events with probabilities
16. SupposethatE 1 ,E 2 ,...,E n areneventswithp(E i )> 0 p(A) = 3/4 and p(B) = 1/3.
for i = 1, 2,...,n. Show that a) What is the largest p(A ∩ B) can be? What is the
smallest it can be? Give examples to show that both
p(E 1 ∩ E 2 ∩ ··· ∩ E n ) extremes for p(A ∩ B) are possible.
= p(E 1 )p(E 2 | E 1 )p(E 3 | E 1 ∩ E 2 )
b) What is the largest p(A ∪ B) can be? What is the
··· p(E n | E 1 ∩ E 2 ∩ ··· ∩ E n−1 ). smallest it can be? Give examples to show that both
extremes for p(A ∪ B) are possible.
17. There are three cards in a box. Both sides of one card are 24. Suppose that A and B are events with probabilities
black, both sides of one card are red, and the third card p(A) = 2/3 and p(B) = 1/2.
has one black side and one red side. We pick a card at
a) What is the largest p(A ∩ B) can be? What is the
random and observe only one side.
smallest it can be? Give examples to show that both
a) If the side is black, what is the probability that the extremes for p(A ∩ B) are possible.
other side is also black?
b) What is the largest p(A ∪ B) can be? What is the
b) What is the probability that the opposite side is the smallest it can be? Give examples to show that both
same color as the one we observed?
extremes for p(A ∪ B) are possible.
18. What is the probability that when a fair coin is flipped n
25. Recall from Definition 5 in Section 7.2 that the
times an equal number of heads and tails appear?
events E 1 ,E 2 ,...,E n are mutually independent if
19. What is the probability that a randomly selected bit string )
p(E i 1 ∩ E i 2 ∩ ··· ∩ E i m ) = p(E i 1 )p(E i 2 ) ··· p(E i m
of length 10 is a palindrome? whenever i j ,j = 1, 2,...,m, are integers with 1 ≤ i 1 <
20. What is the probability that a randomly selected bit string i 2 < ··· <i m ≤ n and m ≥ 2.
of length 11 is a palindrome? a) Write out the conditions required for three
21. Consider the following game. A person flips a coin re- events E 1 ,E 2 , and E 3 to be mutually independent.
peatedly until a head comes up. This person receives a b) Let E 1 , E 2 , and E 3 be the events that the first flip
n
payment of 2 dollars if the first head comes up at the comes up heads, that the second flip comes up tails,
nth flip. and that the third flip comes up tails, respectively,
a) Let X be a random variable equal to the amount of when a fair coin is flipped three times. Are E 1 , E 2 ,
money the person wins. Show that the expected value and E 3 mutually independent?
of X does not exist (that is, it is infinite). Show that c) Let E 1 , E 2 , and E 3 be the events that the first flip
a rational gambler, that is, someone willing to pay to comes up heads, that the third flip comes up heads,
play the game as long as the price to play is not more and that an even number of heads come up, respec-
than the expected payoff, should be willing to wager tively, when a fair coin is flipped three times. Are E 1 ,
anyamountofmoneytoplaythisgame.(Thisisknown E 2 , and E 3 pairwise independent? Are they mutually
as the St. Petersburg paradox. Why do you suppose independent?
it is called a paradox?)
n
b) Suppose that the person receives 2 dollars if the d) Let E 1 , E 2 , and E 3 be the events that the first flip
first head comes up on the nth flip where n< 8 and comes up heads, that the third flip comes up heads,
8
2 = 256 dollars if the first head comes up on or af- and that exactly one of the first flip and third flip come
ter the eighth flip. What is the expected value of the up heads, respectively, when a fair coin is flipped three
amount of money the person wins? How much money times. Are E 1 , E 2 , and E 3 pairwise independent? Are
should a person be willing to pay to play this game? they mutually independent?
22. Suppose that n balls are tossed into b bins so that each e) How many conditions must be checked to show that n
ball is equally likely to fall into any of the bins and that events are mutually independent?
the tosses are independent. 26. Suppose that A and B are events from a sample
a) Find the probability that a particular ball lands in a space S such that p(A) = 0 and p(B) = 0. Show that if
specified bin. p(B | A) < p(B), then p(A | B)<p(A).