2
$\begingroup$

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:

  1. Determine for certain whether or not there exists a possible sample from my collection that satisfies the constraints.
  2. Get at least a rough idea of what fraction of possible samples from the collection will satisfy the constraints.
  3. 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.

$\endgroup$
6
  • $\begingroup$ You could easily compute $\mathbb{E}[S_{ij}]$ and $\text{Var}[S_{ij}]$, then as a heuristic, treat each $S_{ij}$ as an independent Gaussian with the corresponding mean and variance, and use that to estimate the probability that a random sample satisfies all of your constraints. The independent assumption isn't actually accurate, but in many cases if the sample is large enough and the collection is not too degenerate, it might be a fairly reasonable approximation. $\endgroup$
    – D.W. ♦
    Mar 16, 2018 at 4:32
  • $\begingroup$ It's definitely not accurate to assume that the different attributes are independent. They are highly correlated. And, in general, some of the constraints will involve requiring at least a certain minimum representation from some of the rarer attribute values. So unfortunately It's considerably more likely that the cases I'm interested in will not be well represented by crude heuristics of this kind. $\endgroup$
    – Anne Hanna
    Mar 16, 2018 at 22:24
  • $\begingroup$ Your question #2 can be reduced to (approximate) counting the number of lattice points in a convex polytope. Perhaps the known methods for that problem might be of interest. See, e.g., cs.stackexchange.com/a/62927/755 and cstheory.stackexchange.com/a/6464/5038, which compute an exact count; the catch is that the resulting method is probably exponential in A (I think). I don't know if there are better methods for approximate counting, or for sampling. $\endgroup$
    – D.W. ♦
    Mar 16, 2018 at 22:36
  • $\begingroup$ Unfortunately those papers are sufficiently abstract that I can't translate them fast enough for what I need, to see if their methods are actually more efficient than what I was doing. So I stopped trying to get things perfect and just did empirical testing with my particular dataset. I found that over 100s of trials I got a working sample in under a minute's worth of draws every time. I know for sure there exist cases that won't work, but they are apparently very rare, which is good enough for me for now. Can anybody inform me of the correct question-handling etiquette for this situation? $\endgroup$
    – Anne Hanna
    Mar 24, 2018 at 6:19
  • $\begingroup$ If you think your solution might be of interest to others who come across this page, you can write an answer in the Answer Box describing what you found that works. If not, you could just leave the question as is, in case someone else comes across this in the future and has a better suggestion. $\endgroup$
    – D.W. ♦
    Mar 24, 2018 at 6:44

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.