4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jul 14 '18 at 1:27
  • $\begingroup$ @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. $\endgroup$
    – Arthur
    Jul 14 '18 at 19:02
2
$\begingroup$

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$).

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Arthur
    Jul 16 '18 at 19:47

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.