# Combinatorics: likelihood of a uniform draw

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?

-
Find 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. – CodyBugstein Oct 12 '12 at 15:30
wouldn't this mean that there is a probability to draw 12 pebbles of each kind, while we only draw 100 pebbles? – Alexis Oct 12 '12 at 15:43
@Alexis: Yes, that, and it would assume that these events are independent, which they aren't. – joriki Oct 12 '12 at 15:58
Do we draw with or without replacement? – joriki Oct 12 '12 at 16:01
without replacement (updated) – Alexis Oct 12 '12 at 17:11

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).

-
So the geometric mean of the bounds $0.03$ and $0.004$, which is about $0.011$, isn’t a bad estimate. – Brian M. Scott Oct 13 '12 at 4:04
The "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... – Alexis Oct 13 '12 at 11:53
@Alexis: You're welcome! – joriki Oct 13 '12 at 12:44