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?

  • $\begingroup$ 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 with replacement from $n$ and then the probability of drawing the same $c$ balls in your more complicated setup. Depending on $c$ and $d$, there may be a particular pattern of sample in the standard arrangement which cannot possibly be reproduced in the complicated one $\endgroup$
    – Henry
    Apr 20, 2013 at 10:41
  • $\begingroup$ Thanks for your comments. Your understanding of this problem is quite similar with my thoughts. Here's my analysis: $\endgroup$
    – Charles
    Apr 20, 2013 at 13:56
  • $\begingroup$ Here's my analysis,assume the original set is S={1,2,...,n} we want sample a sequence of"223".By standard sampling, we obtain this sequence with probability1/n^3.While using the above method, we must first draw 2 and 3 out from S with probability(d/n)^2;Second, we sample 2 from d with (1/d); Third, we sample 2 from the set {2} (i.e.k=1) with probability(1/n);Finally, we sample 3 from d-{2} withprobability(1-1/n)*(1/(d-1));Thus,by the second method we obtain the sequence with probability(1/n^3)((d-1)/d),which is obviously different from the results got by the standard sampling.You got any clue? $\endgroup$
    – Charles
    Apr 20, 2013 at 14:14

1 Answer 1


Initially there are $k$ seen balls which have been drawn from the bin, $d-k$ unseen balls in the bin, and $n-d$ unseen balls which never reached the bin.

There is a probability $\frac{k}{n}$ of drawing from the $k$ seen balls and they are all equally likely so the probability of each one is $\frac{1}{k}\times \frac{k}{n}=\frac{1}{n}$. There is also a probability $\frac{n-k}{n}$ of picking one of the $d-k+n-d = n-k$ unseen balls making the probability of picking a particular unseen ball also $\frac{1}{n}$. So each ball is equally likely to be drawn, independently of whether it has already been seen or not.

Once an unseen ball is drawn, it becomes seen, increasing the number of seen balls and reducing the number of unseen balls in the bin. So this process can continue for at least $d-k$ draws. After that, there is a positive probability that there are no unseen balls left in the bin, and so the process and the earlier analysis can fail.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.