If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?


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.