# Birthday problem with limited bucket size

Let's say there are 1095 balls, 23 of them are black. Randomly assign each ball into 365 buckets, each has a maximum capacity of 3 balls. What is the probability of at least one bucket having at least 2 black balls?

Initially I thought the order does not matter, so we can imagine assigning the black balls to the buckets first. This will give probability of 0.5, just like the birthday problem. Then I think this is incorrect, as the bucket size is limited, the order of assignment actually matters. We cannot assign black balls first and the other balls later.

Update:
Could the probability simply be:

Probability of at least one unlimited bucket with at least 2 black balls - probability of at least one unlimited bucket with at least 4 black balls?

(By unlimited bucket I mean bucket with no capacity limitations.)

• Why would order matter? In the end, you just want how many black balls are in each container, right? Which is not an issue even if the buckets are bounded. – астон вілла олоф мэллбэрг Nov 1 '18 at 7:18
• Because if non-black balls are assigned to a bucket, there is less black balls you can assign to that bucket. If some buckets are already full, you will have less buckets to be assigned to. – Danny Nov 1 '18 at 8:29

Let $$p(n,b)$$ be the probability that with $$3n$$ balls of which $$b$$ are black and with $$n$$ buckets, you have no buckets with $$2$$ or $$3$$ black balls after putting $$3$$ balls in each bucket drawn at random without replacement from the $$3n$$:

Then you have $$p(n,0)=p(n,1)=1$$ and $$p(n,b)=0$$ when $$b \gt n$$. Otherwise I think you have $$p(n,b) = \frac{(3n-b)(3n-b-1)(3n-b-2) }{3n(3n-1)(3n-2)} p(n-1,b) +3 \frac{b(3n-b)(3n-b-1) }{3n(3n-1)(3n-2)} p(n-1,b-1)$$

so for example you get $$p(2,2)=\frac35$$ and $$p(3,2)=\frac34$$ and $$p(3,3)=\frac{9}{28}$$

I think you get $$p(365,23) \approx 0.62176$$ and so the probability you get at least one bucket with at least two black balls is about $$0.37824$$

Since it may be of interest, I also think $$p(365,27) \approx 0.51549$$ and $$p(365,28) \approx 0.48943$$

• Great solution. May I know if there is a way for solving these difference equations for large numbers? I actually wanted to calculate cases like randomly drawing groups of 100 balls from 10000 balls (with b = 500 black balls) and find the chance of at least one group with at least 51 black balls. – Danny Nov 13 '18 at 4:16
• Moving from "at least one bucket having at least $2$ black balls" to a greater number than $2$ would require a slightly more complicated approach. Simulation might be quicker – Henry Nov 13 '18 at 8:11
• For such large numbers, the answer should be very well approximated by the product of the binomial distribution (as in Ross' reply) and the number of groups, right? – Danny Nov 13 '18 at 9:42

You can just draw groups of $$3$$ and ask the chance that at least one group of $$3$$ has at least two black balls. The chance the first group has at least two black balls is $$3\cdot \frac {23}{1095}\cdot \frac {22}{1094}\cdot \frac {1072}{1093}+\frac {23}{1095}\cdot \frac {22}{1094}\cdot \frac {21}{1093}\approx 0.00124$$. The chance any given draw has at least two black balls is the same by symmetry. By the linearity of expectation, the expected number of buckets with at least two black balls is $$365$$ times this, or about $$0.4524$$. The chance of having at least one bucket with at least two black balls is a little less than this because of the chance you have more than one bucket with at least two black balls.

• 0.00124 is the probability of the first group with at least two black balls. The probability of that for the second group will be different, as balls are taken out and not replaced back. Right? Moreover, 0.4524 is the expected number of brackets, not a probability, so why should the chance of having at least one bucket with at least two black balls has anything to do with this expected number of buckets? – Danny Nov 1 '18 at 8:27
• @Danny: the marginal distribution for the second bucket is the the same as for the first bucket even if they are not independent, and similarly for other buckets. So you can add up the expectations. Meanwhile, the probability cannot be more than the expectation, so the expectation provides an upper bound. – Henry Nov 1 '18 at 9:15