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?