Return to Question

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur equal probability.

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.

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.

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins. There are no constraints as to the capacities of the individual bins, and the items themselves are also all indistinguishable. I want my algorithm to generate allocations in a uniform manner, that is each distinct allocation has equal probability of occurring. Since the bins are indistinguishable, bin order is irrelevant and duplicates need to be accounted for. Let me explain with a small example:

If we have 3 bins and 3 items to allocate, then the following sets each only contain identical allocations:

$A = \{0|1|2, 0|2|1, 1|0|2, 1|2|0, 2|0|1, 2|1|0\}$

$B = \{3|0|0, 0|3|0, 0|0|3\}$

And if $x$ is the resulting allocation, then I want $P(x \in A) = P(x \in B)$.

I've thought about this problem for a while and found that's not trivial at all. At first, I thought that I could successively pick a random bin for each item. But this has two problems:

1. It favors allocations with many duplicates.
2. Some distinct allocations have more ways of items falling into bins which lead up to them than others. The allocation where all items fall into the same bin will be much more unlikely than the one where they are distributed perfectly even. And this problem remains even if we get rid of duplicates.

I found out that my problem can also be understood through partitions from number theory. Unfortunately, there's no known closed-form expression for the number of distinct partitions. So it seems to me that it's not feasible to find a clever encoding of distinct allocations and somehow exploit that in combination with a uniform RNG.

But I'm still curious if there's some way to achieve my goal? Or would the lack of such an expression imply that I'm trying to achieve something impossible?

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.

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur equal probability.

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.

I'm trying to randomly allocate N items over B indistinguishable bins. There are no constraints as to the capacities of the individual bins, and the items themselves are also all indistinguishable. I want my algorithm to generate allocations in a uniform manner, that is each distinct allocation has equal probability of occurring. Since the bins are indistinguishable, bin order is irrelevant and duplicates need to be accounted for. Let me explain with a small example:

If we have 3 bins and 3 items to allocate, then the following sets each only contain identical allocations:

$A = \{0|1|2, 0|2|1, 1|0|2, 1|2|0, 2|0|1, 2|1|0\}$

$B = \{3|0|0, 0|3|0, 0|0|3\}$

And if $x$ is the resulting allocation, then I want $P(x \in A) = P(x \in B)$.

I've thought about this problem for a while and found that's not trivial at all. At first, I thought that I could successively pick a random bin for each item. But this has two problems:

1. It favors allocations with many duplicates.
2. Some distinct allocations have more ways of items falling into bins which lead up to them than others. The allocation where all items fall into the same bin will be much more unlikely than the one where they are distributed perfectly even. And this problem remains even if we get rid of duplicates.

I found out that my problem can also be understood through partitions from number theory. Unfortunately, there's no known closed-form expression for the number of distinct partitions. So it seems to me that it's not feasible to find a clever encoding of distinct allocations and somehow exploit that in combination with a uniform RNG.

But I'm still curious if there's some way to achieve my goal? Or would the lack of such an expression imply that I'm trying to achieve something impossible?

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.

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins. There are no constraints as to the capacities of the individual bins, and the items themselves are also all indistinguishable. I want my algorithm to generate allocations in a uniform manner, that is each distinct allocation has equal probability of occurring. Since the bins are indistinguishable, bin order is irrelevant and duplicates need to be accounted for. Let me explain with a small example:

If we have 3 bins and 3 items to allocate, then the following sets each only contain identical allocations:

$A = \{0|1|2, 0|2|1, 1|0|2, 1|2|0, 2|0|1, 2|1|0\}$

$B = \{3|0|0, 0|3|0, 0|0|3\}$

And if $x$ is the resulting allocation, then I want $P(x \in A) = P(x \in B)$.

I've thought about this problem for a while and found that's not trivial at all. At first, I thought that I could successively pick a random bin for each item. But this has two problems:

1. It favors allocations with many duplicates.
2. Some distinct allocations have more ways of items falling into bins which lead up to them than others. The allocation where all items fall into the same bin will be much more unlikely than the one where they are distributed perfectly even. And this problem remains even if we get rid of duplicates.

I found out that my problem can also be understood through partitions from number theory. Unfortunately, there's no known closed-form expression for the number of distinct partitions. So it seems to me that it's not feasible to find a clever encoding of distinct allocations and somehow exploit that in combination with a uniform RNG.

But I'm still curious if there's some way to achieve my goal? Or would the lack of such an expression imply that I'm trying to achieve something impossible?

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.