1
$\begingroup$

I am having a problem similar to one that has been discussed before, how to uniformly sample from the set of all partitions of a set, but with a few differences.

First, for my case I want to sample from the set of all ordered partitions of a set. This seems easy enough, as in practice the $n$ urns you've probabilistically selected will just as easily have an order as not.

However what I'm having trouble with, is how I would go about uniformly sampling from the set of ordered partitions of a set that do not conflict with a given ordered "subpartition". To give a little insight into why, I'm solving a problem where a solution can be modeled as an ordered partition of a set. However, since the search space is so large, and testing solutions to the problem is computationally expensive, I want to be able to reduce the search space by creating a "partial" ordered partition which represents a partial solution to my problem. Where all elements contained in the ordered "subpartition" are correctly located relative to all other elements in the subpartition. But intuitively I'm unable to imagine a heuristic for efficiently uniformly sampling this smaller set.

e.g. an ordered partition that is a solution to our problem might look like this:

$$P_f = \Big[\{a\},\{e\},\{b,c\},\{d\},\{f,g\}\Big]$$

and an ordered subpartition that conveys a partial solution might look like this:

$$P_p = \Big[\{a\},\{b\},\{f,g\}\Big]$$

Naively, it doesn't seem too difficult to generate uniform samples over the entire set of ordered partitions using the technique we know, and reject samples that do not comply with the subpartition we have constructed. However, the size of the set of all ordered partitions we're sampling from is equal to the $n$th Fubini number, or $a(n)$, where $n$ is the number of elements in the set. So I can imagine the amount of times you would need to sample to not reject, once $P_p$ contains a large proportion of the elements in $P_f$, increases by an infeasible amount.

Another solution, which is efficient, might not be uniform. You select a random remaining element that is in $P_f$ but is not in $P_p$, and use a discrete distribution to place the element into $P_p$, either between or outside the existing sets (forming a new set), or into one of the sets. And continue this until you have no remaining elements, and an ordered partition sample $P_s$. I have a hunch that using the uniform discrete distribution across all of these listed positions will not result in a uniformly sampled partition for the space we're searching, most likely due to the distribution of $|P_s|$ for all sampled ordered partitions in this manner not matching the distribution of ordered partitions for the set that satisfies the subpartition. It seems like the correct distribution would be related to Dobiński's formula in some similar but not exact way to the other question.

I would also like to know the search space of the described problem, but I'm not quite sure how to come up with it, as the number of locations you can throw each ball changes depending on where you threw the last one.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.