Take the 2-minute tour ×  Any ideas on how to approach this
problem?  (Due to Karp) Consider a bin containing d balls chosen
at random (without replacement) from a collection of n distinct
balls. Without being able to see or count the balls in the bin,
we would like to simulate random sampling with replacement from
the original set of n balls. Our only access to the balls in
that we can sample without replacement from the bin.  Consider
the following strategy. Suppose that k < d balls have been drawn
from the bin so far. Flip a coin with probability of HEADS being
k / n. If HEADS appears, then pick one of the k previously drawn
balls uniformly at random; otherwise, draw a random ball from
the bin. Show that each choice is independently and uniformly
distributed over the space of the n original balls. How many
times can we repeat the sampling?  share|improve this question I
am not sure what "independently" means in this context, but you
should be able to calculate the probability of a given sample of
$c$ balls