Balls into Bins
-
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
-
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 ?
-
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
-
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.
-
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.
-
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?
-
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.