1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Dec 30, 2018 at 19:10

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .