An oracle can be asked a binary question. If the real answer is true, the oracle says true with probability tt (and false with probability tf=1-tt). If the real answer is false, the oracle says false with probability ff (and true with probability_ft=1-ff_). So the oracle is defined as P(q) = { tt, ff}.

When the oracle is asked the same question n times and answers true at least m times, what is the probability that the real answer is true?

  • $\begingroup$ By and large, you're better off posting these sorts of Probability questions over at math.stackexchange.com $\endgroup$
    – Steve S
    Jul 5 '14 at 17:05

Let $R$ represent if the real answer is true ($R=T$) or not ($R=F$). Let $N$ ($<n$) be the number of times the oracle says true. The required quantity is $\text{P}(R=T|N\ge m)$. Use Bayes theorem:

$$\text{P}(R=T|N\ge m) = \frac{\text{P}(N\ge m|R=T)\text{P}(R=T)}{\text{P}(N \ge m)}$$

Assuming the oracle answers each question independently,

$$\left( N|R=T \right) \sim \text{Bin}(n, tt)$$

A similar expression for $N|R=F$ can be obtained, allowing the calculation of the probabilities involving $N$ in the question.

No information regarding $\text{P}(R=T)$ is given, so a prior probability of $\frac{1}{2}$ might be assumed.


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.