An urn contains 10 kinds of pebbles, and 100 pebbles of each kind. We draw 100 pebbles (without replacement). What is the probability that we get between 8 and 12 pebbles of each kind?
Combinatorics: likelihood of a uniform draw
-
0Find the probability that, say, Type A is picked 8 times, 9 times, 10 times, 11 times and 12 times. Add those up. Put the sum to the power of 10 and there's your answer. – 2012-10-12
-
2wouldn't this mean that there is a probability to draw 12 pebbles of each kind, while we only draw 100 pebbles? – 2012-10-12
-
0@Alexis: Yes, that, and it would assume that these events are independent, which they aren't. – 2012-10-12
-
0Do we draw with or without replacement? – 2012-10-12
-
0without replacement (updated) – 2012-10-12
1 Answers
The most likely of the admissible combinations is the completely uniform one, with a probability of
$$ \frac{\binom{100}{10}^{10}}{\binom{1000}{100}^{\hphantom{10}}}\approx3.8\cdot10^{-8} $$
(computation). Presumably the most unlikely of the admissible combinations is the most non-uniform one with $12$ pebbles of five kinds and $8$ of the others, with a probability of
$$ \frac{\binom{100}{12}^5\binom{100}8^5}{\binom{1000}{100}}\approx4.5\cdot10^{-9} $$
(computation). The number of admissible combinations can be calculated using the formula at the bottom of this page as the number of ways of distributing $k=20$ excess pebbles over $m=10$ kinds with a capacity of $R=4$ each, which yields
$$ \sum_{t=0}^4(-1)^t\binom{10}t\binom{29-5t}9=856945 $$
(computation). Thus the desired probability $p$ satisfies
$$ 0.03\approx 856945\cdot\frac{\binom{100}{10}^{10}}{\binom{1000}{100}^{\hphantom{10}}}\gt p\gt 856945\cdot\frac{\binom{100}{12}^5\binom{100}8^5}{\binom{1000}{100}}\approx0.004\;. $$
The exact answer is
226031412377730730814344253428220298277915460779610728832457924491489212422618433457300376001429754322127222112213012269223936000000000 ————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————— 18724490300969246403723903560710344364006715745998044509175019419801870086437214647777411833371759499800416660391039940703106220925825529
or about $0.012$, as computed by this code, which enumerates all admissible combinations and checks the result with a simulation (and also checks the number of admissible combinations).
-
1So the geometric mean of the bounds $0.03$ and $0.004$, which is about $0.011$, isn’t a bad estimate. – 2012-10-13
-
0The "Balls In Bins With Limited Capacity" formula looks like a good tool I'll keep in mind! I was struggling to find a formula giving the final result but it seems that there would not be any satisfactory one. Thank you very much for this detailed answer, the estimate formula looks good enough to reuse. I'd thought the probability would be higher... – 2012-10-13
-
0@Alexis: You're welcome! – 2012-10-13