Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?

Question

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the number of balls in each bin, and two allocations are equivalent if you can obtain one by permuting the other.

At first, I thought that I could successively pick a random bin for each item. But this has two problems:

1. Even though the bins are indistinguishable, they need to be indexed during the selection process to be adressable. But that introduces order. There are more distinct allocations when there's order, but they don't map uniformly to the ones from the orderless case. Thus, some allocations are more likely to occur.
2. If we look at the sequences of indices selected for each item in the allocation process, we see that allocations differ by how many different index sequences they can be reached. The allocation where all items fall into the same bin will be much more unlikely to occur than the one where they are distributed perfectly even.

I found out that my problem can also be understood through partitions from number theory, but didn't get very far with that, either.

The only solution I could think of, is to enumerate all allocations explicitly, then sort the bins by size to filter out duplicates, and then randomly pick one of the remaining allocations. But due to memory explosion, this obviously quickly becomes infeasible for non-toy problem sizes.

Answer 1

It appears your question is equivalent to sampling uniformly at random from the integer partitions of $N$, but constrained so that your partition has $\le B$ parts.

If that is correct, there are standard methods to sample uniformly at random from the integer partitions of $N$. See, e.g., https://stackoverflow.com/q/2161406/781723, https://stats.stackexchange.com/q/497858/2921. One approach to solve your problem is to use rejection sampling: generate a random integer partition, and if it has more than $B$ parts, throw it away and repeat.

Another way is to adapt the method of https://stats.stackexchange.com/q/497858/2921 to enforce this constraint, so rather than sampling from the distribution $\Pr[K=k] \propto k^n/k!$, sample from the conditional distribution $\Pr[K=k|K\le B]$. Note that $\Pr[K=k|K\le B] \propto k^n/k!$ for $k\le B$, so one way to sample from this distribution is to let $S=\sum_{k=0}^B k^n/k!$, sample $x$ uniformly at random from $[0,1]$, then let $j$ be the smallest $k$ such that $\sum_{k=0}^j k^n/k! \ge Sx$ and output $j$.

Another way is to take advantage of the recurrence relation for counting the number of integer partitions. You can convert any such recurrence relation into an algorithm for sampling uniformly at random. Let $p(Z,B;N)$ denote the number of integer partitions of $N$ into at most $B$ parts, such that each part is at most $Z$ (or equivalently, the number of distinct ways of throwing $N$ indistinguishable bins into $B$ indistinguishable bins, such that no bin contains more than $Z$ balls). Then there is a recurrence relation for this quantity:

$$p(Z,B;N) = p(Z,B-1;N) + p(Z-1,B;N-B).$$

The recurrence is obtained as follows. Each partition of $N$ falls into one of the following two cases: (1) it uses fewer than $B$ (non-zero) parts, or (2) it uses exactly $B$ (non-zero) parts. In case (2), if you subtract 1 from each part, you obtain a partition of $N-B$ using at most $B$ parts. This immediately gives an algorithm to sample uniformly at random from the set of all integer partitions of $N$ with $\le B$ parts and all parts having values $\le Z$:

Sample($Z,B;N$):

1. Compute $p(Z,B;N)$.

2. Sample an integer uniformly at random from $0,1,2,\dots,p(Z,B;N)-1$. Call it $x$.

3. If $x < p(Z,B-1;N)$, then call Sample($Z,B-1;N$) and return whatever it does.

4. Otherwise, call Sample($Z-1,B;N-B$), add 1 to each part of the partition it returns, append 1's until the partition has exactly $B$ parts, and return that modified partition.

(You'll need to add some appropriate base cases to ensure the recursion terminates, e.g., for the cases $B=1$ and $Z=1$.)

This generates the appropriate distribution. Also, if you compute $p(\cdot,\cdot;\cdot)$ using memoization and the recurrence relation above, this will be a relatively efficient algorithm. Its running time will be something like $O(ZBN)$.

Finally, given this algorithm, you can generate an integer partition of the desired form by invoking Sample($N,B;N$).