# How to sample uniformly from ten urns with ten balls each

I have ten numbered urns with numbered 10 balls in each. I want to draw $$n<100$$ balls in a uniform distribution from all $$100$$ balls (the urns and all balls are distinct.) My procedure: I roll a 10-sided die to decide on the urn and then another one to decide on the ball in it. For the first draw, every ball has $$p=0.01$$.) But for the second draw it could happen with the same $$p$$ that my dice indicate the same ball as before that has been removed. Should I now:

1. repeat the process of throwing both dice so many times that I get a ball that hasn't been drawn?
2. just repeat the second die roll and stay in the same urn?

Both seemed biased. In 1. the result would be that I might do more than $$n$$ iterations and in 2. it seems that the probability for a ball in an urn that has been chosen before goes up (resulting in a nonuniform distribution.)

What procedure needs to be done to result in a uniform distribution?

• The problem with your method is: once you draw a ball you have to reduce the probability that you repeat the same urn (else the other balls in that urn have a greater chance of being picked next). Hard to implement with dice. Your first method works but, as you say, it is inefficient.
– lulu
Commented Dec 30, 2018 at 19:10

Your first approach will give a uniform distribution. Even after you have removed $$k$$ balls, each of the remaining $$100-k$$ balls has $$0.01$$ chance to be picked on one roll. The downside is you have to roll a lot of times-when you get to $$2$$ balls you expect to need $$50$$ rolls to pick one of them. This is the coupon collector's problem but you don't need to pick the last coupon because presumably when you have picked $$99$$ balls you can just pick the last without rolling. Your expected total number of rolls is $$100H_{100}-100\approx 418$$ rolls.
Your second approach is biased. If the first five balls come out of the same urn, the remaining balls have chance $$0.02$$ to be picked while all the other balls still have chance $$0.01$$ to be picked.
An improvement is to recognize that you have essentially numbered the balls $$00$$ through $$99$$. You can keep track of the order of the remaining balls, so when you roll $$26$$ you pick the $$26^{th}$$ ball of the remaining set instead of ball $$6$$ from urn $$2$$. The advantage comes when you have removed $$50$$ balls. Now you can assign two numbers to each ball and increase the odds the number is small enough to find a ball. Once you have removed $$67$$ balls you can give each ball $$3$$ numbers and so on.
More efficient yet is to note that $$100! \approx 9.3\cdot 10^{157}$$ You can roll $$158$$ numbers from $$00$$ through $$99$$ and use them to pick a specific permutation of the balls. You have only about a $$7\%$$ chance of getting too high a number to use. You can start over, or use the number you have and roll a time or two more. The last will take some thought how to make it work.