Planetary Party
(a) Suppose we are at party on a planet where every year is 2849 days. If 30 people attend this party, what is the exact probability that two people will share the same birthday? You may leave your answer as an unevaluated expression.
(b) Give an approximation for the probability in (a) using a result you learned from lecture.
(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?
(d) Now suppose that 100 people attend this party. What the is probability that none of these 100 individuals have the same birthday?
CS 70, Fall 2018, DIS 10A 1
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?
