Description

1 Planetary Party
(b) From lecture, we know that given n bins and m balls, Pno collision . Using this, give an approximation for the probability in part (a).
(c) What is the minimum number of people that need to attend this party to ensure that the probability that any two people share a birthday is at least 0.5? You can use the approximation you used in the previous part.
(d) Now suppose that 70 people attend this party. What the is probability that none of these 70 individuals have the same birthday? You can use the approximation you used in the previous parts.
2 Throwing Balls into a Depth-Limited Bin
Say you want to throw n balls into n bins with depth k−1 (they can fit k−1 balls, after that the bins overflow). Suppose that n is a large number and k = 0.1n. You throw the balls randomly into the bins, but you would like it if they don’t overflow. You feel that you might expect not too many balls to land in each bin, but you’re not sure, so you decide to investigate the probability of a bin overflowing.
(a) Count the number of ways we can select k balls to put in the first bin, and then throw the remaining balls randomly. You should assume that the balls are distinguishable.
(b) Argue that your answer in (a) is an upper bound for the number of ways that the first bin can overflow.
(c) Calculate an upper bound on the probability that the first bin will overflow.
(d) Upper bound the probability that some bin will overflow. [Hint: Use the union bound.]
(e) How does the above probability scale as n gets really large?
3 The Memoryless Property
Let X be a discrete random variable which takes on values in Z+. Suppose that for all m,n ∈ N, we have P(X > m+n | X > n) = P(X > m). Prove that X is a geometric distribution. Hint: In order to prove that X is geometric, it suffices to prove that there exists a p ∈ [0,1] such that P(X > i) = (1− p)i for all i > 0.