Occupancy distribution for batched allocations?

54 Views Asked by At

I've searched here and in my limited collection of combinatorics books for a solution to this with no luck.

Say I have $b$ bins labeled $1$...$b$.

A process selects $k$<=$b$ integers from $[1,b]$ without replacement, and a single ball is placed into each of the correspondingly labeled boxes. (n.b.: the "without replacement" applies only to each iteration of the process, not throughout the iterations, that is, at each iteration, all of the integers $[1,b]$ are available for sampling).

If I repeat the process (with $k$ fixed for each iteration) $z$ times, what is the distribution of fillings for the bins - that is, I'd like to be able to get the probability that some bin has $0$<=$n$<=$z$ balls at the completion of the iterations of the process.

I naively thought this would be a simple extension of the same problem where one ball is allocated at each iteration, but it's clearly more complex and beyond my limited combinatorics knowledge.

Help, even if only in a literature reference, will be most appreciated.

1

There are 1 best solutions below

0
On

Let $\mathbf{N} = (N_1,...,N_b)$ be the number of balls in each bin after allocating $k$ balls at random. This vector of counts follows the multinomial distribution with a uniform probability parameter:

$$\mathbb{P}(\mathbf{N} = \mathbf{n}|k,b) = \text{Mu}( \mathbf{n} | k, (\tfrac{1}{b},...,\tfrac{1}{b})) = {k \choose \mathbf{n}} \frac{1}{b^k}.$$

If you repeatedly ransomise $k$ balls at a time, each iteration will add a count vector from this distribution. For example, after $z$ iterations of sampling $k$ times, you will have allocated $zk$ balls at random, so the probability mass function will be the same as the above, except that the value $k$ is replaced with $zk$.