Design a sampling process to select an element with probability proportional to its appear probability in a simulation

Question

We are given a black box $A$ that can do a simulation. Each time running box A gives a sample $S \in 2^X$ where $X$ is a finite ground set.

Let $\Pr[x]$ be the probability that $x \in X$ appears in the sample $S$.

We try to design a sampling process $B$ which can produce an element in $X$ randomly.

Let $\Pr_1[x]$ be the probability that $x$ is produced by $B$.

We need that $\Pr_1[y]=\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$ for each $y \in X$. An approximately correct algorithm would be OK too, i.e., $\Pr_1[y] \approx\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$.

How to design such a sampling process $B$ by using the black box $A$?

---

First try:

1 run A once and obtain a sample $S$.

2 select an element from $S$ uniformly at random.

3 return $x$.

Intuition: First, the probability that $x \in S$ is $\Pr[x]$. In the second step, each element in $S$ is selected with probability $1/|S|$. The expected value of $|S|$ is actually $\sum_{x \in X} \Pr[x]$. At the first glance, the probability that $y$ is returned seems to be $\frac{\Pr[y]}{\sum_{x \in X} \Pr[x]}$. However, that $x \in S$ and $|S|$ are not independent.

Counter Example: Suppose $X=\{1,2\}$ and the distribution associated with $A$ is $\Pr[\{1\}]=0.5$ and $\Pr[\{1,2\}]=0.5$. Then $\Pr_1[1]=0.5+0.5*0.5=0.75$. However, $\Pr[1]/(\Pr[1]+\Pr[2])=1/(1+0.5)=2/3$.

---

Any help is appreciated.

Answer 1

This can be done efficiently if the size of the samples $S$ is not too large. Let $m$ denote the maximum possible size of $S$. Then the following procedure outputs exactly the correct distribution:

1. Draw a sample $S$ (using the black box $A$). With probability $|S|/m$, keep $S$ and go to step 2. Otherwise, go back to step 1 and draw a new sample.

2. Choose an $x$ uniformly at random from $S$. Output $x$.

You can verify that this yields the correct distribution. It requires at most $O(m)$ samples (possibly less, depending on the distribution of the size of $S$).

---

On the other hand, if the samples can be very large, then approximating the distribution accurately may require many samples. Consider the following situation. Randomly choose a subset $X_0$ of $X$ of size $|X|/2$, and imagine a black box $A$ that works as follows: with probability $1/s$, it outputs the set $X_0$; otherwise, it outputs a single element chosen uniformly at random from $X$ (i.e., a random singleton set). Then if you draw $s$ samples, you have about a $1-1/e \approx 0.37$ probability of hitting the large set $X_0$. Moreover, if you don't hit the large set, the probability distribution of your procedure will be off by a total variation distance of $1/s$ (the probability for each element will be off by an additive error of $1/(s|X|)$). So, if you want a distribution that is close to correct in total variation distance, you'll need many samples. If you want an additive error of $\epsilon$ with probability at least $1-\delta$, you might need something like $O(1/\epsilon)$ samples (I'm not sure about the dependence on $\delta$).