Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 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 –  Henry Apr 20 '13 at 10:41
Thanks for your comments. Your understanding of this problem is quite similar with my thoughts. Here's my analysis: –  Charles Apr 20 '13 at 13:56
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? –  Charles Apr 20 '13 at 14:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.