4
$\begingroup$

As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\mathbb{Z}^n$ for some $n$, but I would expect any answer to be independent of that structure), and a domain $B\subset A$. If I have an efficient algorithm for uniformly sampling from $A$, and an efficient algorithm for uniformly sampling from $B$, is there any way of 'combining' these to get an efficient algorithm for uniformly sampling $A-B$? I can certainly rejection-sample, but if $|A-B|\ll|A|$ then there's no guarantee that that will be efficient.

$\endgroup$
3
$\begingroup$

Theorem: For any given $A$, either there are good algorithms to sample every subset of $A$, or what you're describing is impossible.

Proof (perhaps slightly informal): Suppose there are some "problematic" subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows that $|C| \ll |A|$ (otherwise $C$ could be dealt with by rejection-sampling). Now let $B = A \setminus C$. Clearly, rejection-sampling does work on $B$, because $B$ is almost the entirety of $A$. So now we have algorithms for both $A$ and $B$, but no algorithm for $C$. Q.E.D.

Here's a ridiculous example: $A = \{(x_1, x_2, x_3, x_4) \mid x_i \in \mathbb{Z},\; 2 < x_i < 10^{10^{10^{1000}}}\}$ and $B$ contains only those quadruplets of numbers which are not counterexamples to Fermat's Last Theorem (i.e. such that $x_1^{x_4} + x_2^{x_4} \neq x_3^{x_4}$). It's trivially easy to sample $B$, but that gives us no clue whatsoever about how to do $A \setminus B$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don‘t get how your proof works. I must be missing something. I mean: I believe it, but I don‘t see how your proof really proves anything. You start by assuming C is problematic and you end up concluding that then B is not but C still is... what?!?! Not knowing how to sample from C does not mean it is not possible. You then proceed to give an example where it is hard to sample from C. You might as well have given one where it is easy. You not being able to construct an algo for C given one for A and B does not prove it is not possible per se... $\endgroup$ – dingalapadum Jul 1 at 11:19
  • $\begingroup$ The point is: if at least one problematic set exists (let's call it C), then I can give you an example of a set B such that B is easy to sample, while A\B isn't. Therefore, the general problem of transforming a sampler for B into a sampler for A\B is unsolvable. $\endgroup$ – Сергей Макеев Jul 1 at 15:15
  • $\begingroup$ oh, now I see what you mean! In my own words: either there are no problematic sets or if there is one (C), then by assumption A\C can‘t help you - in particular A\C being unproblematic makes no difference. Therefore, A being easy and B being easy can‘t help you with C if C is problematic. That makes complete sense. Sry for being a slow thinker... Now, if I understood correctly there still is one little issue: we don‘t know if C is problematic or not. So what probably is missing is to show that even if C is unproblematic, algos for A and B won‘t necessarily yield one for C, right? $\endgroup$ – dingalapadum Jul 1 at 15:55
  • $\begingroup$ @dingalapadum No; this is an existence proof — I was asking whether we can always sample $A-B$ efficiently, and this shows that there's at least one difference set that we can't sample efficiently. That said, there's a little bit of a catch here... $\endgroup$ – Steven Stadnicki Jul 1 at 15:58
  • 1
    $\begingroup$ ..._do_ we know that $B$ can be efficiently rejection-sampled? We know that it's large and so rejection will work if we have an efficient test for membership in $B$ (or equivalently, in $C$)... but can we be certain that an efficient test for membership in $C$ doesn't imply an efficient means of sampling $C$? (I tend to believe that's not the case and so this proof should work, but I don't know for certain.) $\endgroup$ – Steven Stadnicki Jul 1 at 15:59
0
$\begingroup$

In general it is not possible to construct an efficient sampling algorithm for $A\setminus B$ given efficient ones for $A$ and $B$ (depending on your definition of efficient). Here is a simple counter-example, where efficient means $o(n)$ where $n$ is the size of $A$. Also for simplicity let $A$ be a set of integer. Now, define $B$ as $A\setminus \{x\}$ where $x$ is any integer. Then, if we have an efficient sampling algorithm for $A$ and $B$ and could create an efficient one for $A\setminus B$ which is equal to $\{x\}$, we could use it to efficiently check if $x$ is in $A$. However, by our definition of efficient this would mean that we could check membership in a without looking at all elements in a which is not possible :)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.