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

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=0.5+0.5*0.5=0.75$. However, $\Pr/(\Pr+\Pr)=1/(1+0.5)=2/3$.

Any help is appreciated.

• It seems one straightforward approach is to estimate $\Pr[x]$ for each $x$ by sampling many times from $A$ and counting how many times each $x$ occurs among these samples, then compute the desired distribution. As long as you have enough samples this should be able to achieve as much accuracy as desired. There may be a better strategy (with better approximation with fewer queries), though.
– D.W.
Jul 14 '18 at 1:27
• @D.W. Thanks. My concern is that when $\Pr[x]$ is very small, estimating $\Pr[x]$, e.g., an $(\epsilon, \delta)$-estimation, requires a lot of simulations of A. Is it possible to obtain $\Pr[x]/\sum_{y\in X}\Pr[y]$ without directly estimating each $\Pr[x]$? I am not sure if this is theoretically possible. Jul 14 '18 at 19:02

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$).
• Amazing. That is exactly the solution. I do have an upper bound on $|S|$ but it is very loose. I am thinking to first estimate $\max(|S|)$ and then run your proposed solution. Thank you. Jul 16 '18 at 19:47