We can suppose that we are asked a true/false question. We have a means of possibly getting an answer. With probability $(1-p_1)$ it is inconclusive. However, with probability $(p_1)$ we can arrive at one of two conclusions. If we divide the step with the conclusions into $(p_2)$ parts, then $(p_2-4)$ parts guarantee that the conclusion is true. Of the remaining 4 parts, one is false and the other three are true, but we don't know which is which. We can tell if we've picked one of the 4 parts or one of the $(p_2-4)$ parts, but nothing more.

We are allowed to go through this "operation" more than one time.

My question is, if the answer is false, can we guarantee that we arrive at the correct answer, false, with high probability?


My idea is that we can, because we can go through the process many times to allow the conclusion step to be reached with high probability. Then if we pick a false part, we can go through many more times to see if it might be true. If it isn't we can conclude the result is false with high certainty.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.