<p>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:</p>

<ol>
<li><p>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.</p></li>
<li><p>Choose an $x$ uniformly at random from $S$.  Output $x$.</p></li>
</ol>

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

<hr>

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

CC BY-SA 4.0
2018-07-16T19:47:51.990Z
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.
Arthur
CC BY-SA 4.0
2018-07-15T18:24:23.673Z
2018-07-15T18:24:23.673Z
D.W.
<p>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.</p>

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

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

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

<p>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]}$.</p>

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

<hr>

<p>First try:</p>

<p>1 run A once and obtain a sample $S$.</p>

<p>2 select an element from $S$ uniformly at random.</p>

<p>3 return $x$.</p>

<p>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.</p>

<p>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$. </p>

<hr>

<p>Any help is appreciated.</p>

CC BY-SA 4.0
2018-07-14T01:27:07.210Z
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.
CC BY-SA 4.0
2018-07-14T19:02:59.453Z
@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.
Arthur
<st.statistics><monte-carlo><lts-simulations>
Design a sampling process to select an element with probability proportional to its appear probability in a simulation
Arthur
# Design a sampling process to select an element with probability proportional to its appear probability in a simulation

(Asked by: username_0 on 2018-07-12)

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.

**Tags:** st.statistics, monte-carlo, lts-simulations
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_1 on 2018-07-15. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  

---

