<p>I have a black-box function which returns true with probability <span class="math-container">$ P(A) $</span>, that I don't know how to calculate.</p>
<p>I receive evidence B, and I want to create a function which returns true with probability <span class="math-container">$ P(A|B) $</span>. According to Bayes' theorem <span class="math-container">$ P(A|B) = P(A) \frac{P(B|A)}{P(B)} $</span>.</p>
<p>I can calculate <span class="math-container">$P(B|A)$</span> and <span class="math-container">$P(B)$</span>, so I can calculate <span class="math-container">$\alpha=\frac{P(B|A)}{P(B)}$</span>, and I need to create a function which returns true with probability <span class="math-container">$\alpha P(A)$</span>. I know how to do that for <span class="math-container">$\alpha\le1$</span> - just create an independent event <span class="math-container">$C$</span> with <span class="math-container">$P(C) = \alpha$</span> and check <span class="math-container">$A \land C$</span>.</p>
<p>Is there a way to do that for <span class="math-container">$\alpha &gt; 1$</span>? And if there is, what would be the minimal number of evaluations of the function to do that? If there isn't any efficient exact method, I'm also interested in efficient approximations.</p>
<p>EDIT:</p>
<p>I think I know how to prove it can't be done with only a single call:</p>
<p>Assuming a fixed <span class="math-container">$\alpha &gt; 1$</span>, there must be some event, <span class="math-container">$B$</span>, where <span class="math-container">$A$</span> is false, but the function returns true. Since the function is a black-box, those cases are independent of the function, and have a constant non-zero probability <span class="math-container">$x=P(B)$</span>.
That means that even if you make <span class="math-container">$P(A)$</span> arbitrarily small the probability of outputting true would be at least <span class="math-container">$x$</span>, which is impossible if the probability of outputting true is <span class="math-container">$\alpha P(A)$</span></p>

CC BY-SA 4.0
2022-03-31T15:39:06.193Z
Implementing the approach you suggest is (informally) NP-hard, by the following reduction from 3-SAT.  Given an $n$-variable 3CNF- formula $\phi$, construct a "black box" that chooses a random assignment and returns true if the assignment satisfies $\phi$, else false.  Let $A$ be the event that it returns true.  Suppose that, for $\alpha=2^n$, you could construct a function that returns true with probability $\min(1, \alpha P(A))$.  This function will return true if $\phi$ is satisfiable and false otherwise.
Neal Young
CC BY-SA 4.0
2022-03-31T18:02:55.580Z
Are you happy with methods that take $O(\alpha)$ invocations of the black-box and loosely approximate the desired probability?  If so, you can query the blackbox $O(\alpha)$ times, and check if it returns true more than a few times; if yes, then use the proportion of trues to estimate $P(A)$ and flip a coin with the desired heads probability, otherwise query the blackbox $\alpha$ more times and return true the logical-or of those $\alpha$ results.  I'll let you work out the details, the parameters, and the quality of the resulting approximation.
D.W.
CC BY-SA 4.0
2022-04-02T10:38:38.343Z
I read they use https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm for essentially this task in Probabilistic Programming and other Bayesian inference applications, but I guess I misunderstand your question, sorry...
Alex Chichigin
<pr.probability><random-oracles><black-box>
Outputting true with probabiltiy $P(A|B)$ given $P(B), P(B|A)$, and a function which returns true with probability $P(A)$
Command Master
# Outputting true with probabiltiy $P(A|B)$ given $P(B), P(B|A)$, and a function which returns true with probability $P(A)$

(Asked by: username_0 on 2022-03-30)

I have a black-box function which returns true with probability $ P(A) $, that I don't know how to calculate.

I receive evidence B, and I want to create a function which returns true with probability $ P(A|B) $. According to Bayes' theorem $ P(A|B) = P(A) \frac{P(B|A)}{P(B)} $.

I can calculate $P(B|A)$ and $P(B)$, so I can calculate $\alpha=\frac{P(B|A)}{P(B)}$, and I need to create a function which returns true with probability $\alpha P(A)$. I know how to do that for $\alpha\le1$ - just create an independent event $C$ with $P(C) = \alpha$ and check $A \land C$.

Is there a way to do that for $\alpha > 1$? And if there is, what would be the minimal number of evaluations of the function to do that? If there isn't any efficient exact method, I'm also interested in efficient approximations.

EDIT:

I think I know how to prove it can't be done with only a single call:

Assuming a fixed $\alpha > 1$, there must be some event, $B$, where $A$ is false, but the function returns true. Since the function is a black-box, those cases are independent of the function, and have a constant non-zero probability $x=P(B)$.
That means that even if you make $P(A)$ arbitrarily small the probability of outputting true would be at least $x$, which is impossible if the probability of outputting true is $\alpha P(A)$

**Tags:** pr.probability, random-oracles, black-box
> **Comments:**
> **username_1**: Implementing the approach you suggest is (informally) NP-hard, by the following reduction from 3-SAT.  Given an $n$-variable 3CNF- formula $\phi$, construct a "black box" that chooses a random assignment and returns true if the assignment satisfies $\phi$, else false.  Let $A$ be the event that it returns true.  Suppose that, for $\alpha=2^n$, you could construct a function that returns true with probability $\min(1, \alpha P(A))$.  This function will return true if $\phi$ is satisfiable and false otherwise.  
> **username_2**: Are you happy with methods that take $O(\alpha)$ invocations of the black-box and loosely approximate the desired probability?  If so, you can query the blackbox $O(\alpha)$ times, and check if it returns true more than a few times; if yes, then use the proportion of trues to estimate $P(A)$ and flip a coin with the desired heads probability, otherwise query the blackbox $\alpha$ more times and return true the logical-or of those $\alpha$ results.  I'll let you work out the details, the parameters, and the quality of the resulting approximation.  
> **username_3**: I read they use https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm for essentially this task in Probabilistic Programming and other Bayesian inference applications, but I guess I misunderstand your question, sorry...  

---

## 0 answers

