Recall that a Monte Carlo algorithm is $ p $-Correct if you give a correct answer with probability at least $ p $. In the case of decision problems, where the response is binary, repeating the MC algorithm can increase the confidence that a correct answer is obtained.
However, in the case that more than one answer is correct, this confidence may decrease. I wonder how many times $ k $ Is it necessary to execute an algorithm of this type to obtain a confidence in the response that is less than 50%?
This is what I have done:
Suppose that $ k = 3 $ and I have a 75% correct MC algorithm that generates 5 possible answers, 4 of which are correct and 1 is incorrect. I believe that in this case, the 75% "correction" of the algorithm is divided among all the possible correct answers, so that each correct answer has a "probability" of 75% / 4.
Suppose that the correct answers are $ a, b, c, d $ and an incorrect answer is $ e $.
In this case, if I list all the possible combinations of outputs of an MC algorithm that I execute $ k = 3 $ Sometimes, I get a list of tuples $ (a, a, a) $, $ (a, a, b) $… and so on, each of which is associated with a probability that it will occur. For example $ (a, a, a) $ has probability $ (0.75 / 4) ^ 3 $ of happening and $ (a, a, e) $ has probability $ (0.75 / 4) ^ 2 * 0.25 $.
So, if I build a table associating each possible tuple with its probability of occurrence, and add up the probabilities of all the events in which the algorithm would yield the correct answer by majority vote (the ties are divided by random selection), this should give me the final "Confidence" of the algorithm. In this case, I get numbers around 0.65-0.75 (due to the randomness in the draws division).
However, I could not find a $ k $ which gets this value below 50%.
Any idea if I'm doing something wrong? The help is very appreciated.