Skip to main content
8 of 8
Replaced the mushroom story with a more appropriate example; deleted 6 characters in body; added 36 characters in body; Post Made Community Wiki
user14324
  • 309
  • 1
  • 13

Probability of having a bounded ratio of two types of balls in each of 'S' bins after random partitioning of a fixed number of balls

Let's say I have a bag with $A$ red balls, $B$ blue balls, and a total number of balls $N = A + B$. With uniform probability, and sampling without replacement from the $N$ balls, I fill an integer number of bins, $S$, with exactly $L$ balls each, where $N = S*L$. As such, the bag of all $N$ balls should be empty by the end of the procedure.

What is the probability of having at most $k \leq B$ blue balls in every one of the $S$ bins?

Edit - I would be very much interested in approximate solutions! This problem should essentially come down to something akin to making sure a fixed number of points randomly placed on a matrix are at least some fixed distance apart (causing them to end up in different bins), so surely there have been problems like this tackled in the literature?

Edit 2 - As per Peter Shor's recommendation, I'm interested in examples where $S$ and $L$ are of fixed size, but where $S$ is large, at least $10^3$ to $10^4$ or so, and $L$ is typically significantly smaller than $S$ (around $10$ to $10^2$ or so).


Another way of asking this question might be as follows -

Let's say that I have a matrix composed of $S$ blocks of $L$ cells (pick whatever geometry you'd like), where $S > 10^3$ and $L$ is approximately $10^1$ ~ $10^2$ or so. Some fixed number of cells, $A$, store the value '0', while the remaining $B$ cells store the value '1'. To be clear, there are a total of $A + B = S*L = N$ cells in the matrix.

What is the probability that all $S$ blocks contain at most $k$ cells with the storage value '1' (i.e. at most $k$ of the $B$ cells)?

user14324
  • 309
  • 1
  • 13