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