Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 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. –  Dilip Sarwate Feb 7 '12 at 14:30

1 Answer 1

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

share|improve this answer
    
what is B? q^3+3*q^2*(1-q)=0.104, if q=0.2 so q_B<q. How do you deduce the probability? –  miracle173 Feb 7 '12 at 18:15
    
@Thrasos: You are right, but not entirely. If $q>1/2$, then the "majority vote from $3$" gives improved probability. If $q<1/2$, it is worse! Your calculation illustrated that. The break-even point is $q=1/2$, where $q^3+3q^2(1-q)=1/2$. If the probability that an individual is right is $<1/2$, then taking a majority vote is a very bad idea. –  André Nicolas Feb 7 '12 at 18:58
    
@AndréNicolas If the probability that an individual is right is indeed smaller than $1/2$, one should take the majority vote and do the exact opposite! –  Dilip Sarwate Feb 7 '12 at 21:15
    
@Dilip Sarwate: Thanks for adding that, I should have said it. –  André Nicolas Feb 7 '12 at 21:22
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. –  Ansgar Esztermann Feb 8 '12 at 7:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.