3
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Mar 31, 2022 at 15:39
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 31, 2022 at 18:02
  • $\begingroup$ I read they use 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... $\endgroup$
    – Alex Chichigin
    Apr 2, 2022 at 10:38

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.