Suppose I have a collection of N items, each of which has A different attributes, a1, a2, ..., aA. Attribute ai can take on Vi different possible (discrete) values, distributed across the population with some kind of complicated joint probability φ(a1, a2, ..., aA). It is quite likely that many possible combinations of attributes are either extremely rare in or entirely absent in my collection.
Now suppose I want to draw a sample of S items from my collection, and I want my final sample to satisfy a set of aggregate constraints, each having the form lij ≤ Sij ≤ uij, where Sij is the number of items in the sample for which attribute ai takes on its jth value.
What I'd like to find is an efficient way to do the following things:
- Determine for certain whether or not there exists a possible sample from my collection that satisfies the constraints.
- Get at least a rough idea of what fraction of possible samples from the collection will satisfy the constraints.
- Efficiently select such a sample at random. In particular, if only a very small fraction of possible samples will satisfy the constraints, I'd like a good way to do some kind of pre-filtration on the space I sample from, to reduce the number of random samples I have to draw before I get one that satisfies my constraints. Since the space of possible samples is quite large, exhaustively enumerating possibilities and filtering for satisfactory ones is not a reasonable option.
I don't have a lot of domain knowledge in this area, so even suggestions of better terminology for expressing this issue would be helpful.