Some Interesting Probablity Puzzles

Balls into Bins



1. Given n balls and n bins. We throw each ball uniformly randomly into the bins. What is the expected number of (i) empty bins (ii) bins containing one ball (iii) bins containing k balls



2. Given an unlimited supply of balls and a set of n empty bins. We take a ball from the supply and throw it randomly among the bins so that its chances of landing into any of the n bins is same. We continue throwing the balls until no bin is left empty. What is the expected number of balls thrown before no bin is left empty ?



3. Consider the following experiment that proceeds in a sequence of rounds. For the first round, we have n balls, which are thrown uniformly randomly into n bins. After round i , we discard every ball that fell into a bin itself in round i . The remaining balls are retained for i+1 round, in which they are again thrown independently and uniformly at random into the n bins. We stop when there is no ball left. Prove that with probability 1- o(1) the experiment will finish in loglog n number of rounds.



Balls out of Bin

1. A bin contains a white balls and b black balls. We take out the balls at random from the bin without replacement. What is the probability that first ball is white, second ball is white, kth ball is white.



2. A bin contains n balls numbered 1,2,...,n . We pick a bunch of k balls from the bin uniformly randomly. What is the
(i) expected number of the greatest numbered ball in the bunch.
(ii) expected number of the least numbered ball in the bunch.



3. There are n bins and n players, and each player has an infinite supply of balls. The bins are initially empty. We have a sequence of rounds : in each round, each player throws a ball into an empty bin chosen independently at random from all currently empty bins. Let the random variable Z be the number of rounds before every bin is non-empty. Determine the expected value of Z. What can you say about the distribution of Z?



4. A bin contains m white balls and n black balls. We take out the balls uniformly randomly from the bin without replacing them. What is the expected number of black balls left when all the white balls have been taken out.