# RSA calculations

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.

-
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

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