Description

CS 70 Discrete Mathematics and Probability Theory

1 Probability Potpourri
Prove a brief justification for each part.
(a) For two events A and B in any probability space, show that P(AB) ≥ P(A)−P(B).
(b) If |Ω| = n, how many distinct events does the probability space have?

(c) Suppose P(D |C)=P(D |C), where C is the complement of C. Prove that D is independent of C.
2 Aces
Consider a standard 52-card deck of cards:
(a) Find the probability of getting an ace or a red card, when drawing a single card.
(b) Find the probability of getting an ace or a spade, but not both, when drawing a single card.
(c) Find the probability of getting the ace of diamonds when drawing a 5 card hand.
(d) Find the probability of getting exactly 2 aces when drawing a 5 card hand.
(e) Find the probability of getting at least 1 ace when drawing a 5 card hand.
(f) Find the probability of getting at least 1 ace or at least 1 heart when drawing a 5 card hand.
3 Balls and Bins
Throw n balls into n labeled bins one at a time.
(a) What is the probability that the first bin is empty?
(b) What is the probability that the first k bins are empty?
(c) Let A be the event that at least k bins are empty. Notice that there are m sets of k bins out of the total n bins. If we assune Ai is the event that the ith set of k bins is empty. Then we can write A as the union of Ai’s.
m
A = [Ai.
i=1 Write the union bound for the probability A.
(d) Use the union bound to give an upper bound on the probability A from part (c).
(e) What is the probability that the second bin is empty given that the first one is empty?
(f) Are the events that “the first bin is empty” and “the first two bins are empty” independent?
(g) Are the events that “the first bin is empty” and “the second bin is empty” independent?