1
$\begingroup$

I can not find a solution to the following problem. The problem is:

We have an algorithm A for a decision problem that answers yes or no and for every input it gives the right answer with possibility at least equal to q. To improve the possibility q, we run the algorithm 3 times and we see the three outputs. Which is the possibility for the answer to be true? Is this possibility indeed higher than q?

thank you.

  • 0
    This has been studied in the literature on _fault-tolerant computing_. Search for _triple modular redundancy_, which uses three (possibly faulty) identical circuits to evaluate a Boolean function, and takes a majority vote of the three outputs to decide the correct value. See e.g. [here](http://courses.engr.illinois.edu/ece313/fall00/ppt/Lecture19.pdf) for a simple example that leads to the same answer as given by Ansgar Esztermann, and which also considers failures in the majority computation. It is not how people vote, but how ballots are counted, that determines the results of elections.2012-02-07

1 Answers 1

3

Here's my take: I will assume subsequent runs of A (on the same input) are independent. One would define the algorithm $T$ as: run $A$ three times, return true if at least two runs of $A$ return true, return false otherwise. Three runs of $A$ yield either $(ccc), (cci), (cii), (iii)$ where $c$ means the correct result, $i$ the incorrect one, so $T$ is correct with probability $q_{T}=q^3+3q^2(1-q)$.

The only thing that remains is to determine if $q_T>q$ (which is straightforward).

  • 1
    @miracle173 Ouch, that should read $T$. I've edited my answer accordingly. As to the case q<1/2, the strategy _do the opposite_ applies to a single run of $A$ as well, so we can use that to keep $q\geq 1/2$ w.l.o.g -- if $q$ is known, that is.2012-02-08