1
$\begingroup$

Recall that a Monte Carlo algorithm is $p$-correct if it outputs a correct answer with probability at least $p$. In the case of decision problems, where the answer is binary, repeating the MC algorithm can increase the confidence that a correct answer is obtained.

However, in the case where more than 1 possible answer is correct, this confidence can actually decrease. I'm wondering how many times $k$ does such an algorithm have to be run to obtain a confidence in the answer that is less than 50%.

Here's what I've done:

Suppose that $k=3$ and I have a 75%-correct MC algorithm that outputs 5 possible answers, 4 of which are right, and 1 is wrong. I think in this case, the 75% "correctness" of the algorithm is split between all possible right answers, such that each correct answer has a "probability" of 75%/4.

Suppose the right answers are $a, b, c, d$ and a wrong answer is $e$.

In this case, if I list all possible combinations of outputs of an MC algorithm that I run $k=3$ times, I get a list of tuples $(a, a, a)$, $(a, a, b)$... and so on, each of which is associated with a probability of occurring. So for instance $(a, a, a)$ has probability $(0.75/4)^3$ of occurring and $(a, a, e)$ has probability $(0.75/4)^2 * 0.25$.

So if I build a table associating each possible tuple to its probability of occurring, and sum the probabilities of all events where the algorithm would output the correct answer by majority voting (ties are split by choosing randomly), this should give me the final "confidence" of the algorithm. In this case, I get numbers around 0.65-0.75 (because of the randomness in tying splits).

However, I haven't been able to find a $k$ that gets this value to below 50%.

Any ideas if I'm doing something wrong? Help is much appreciated.

$\endgroup$
  • 1
    $\begingroup$ I think your premise is confused. If you want a less-than-50% confidence in your answer, just pick a known-invalid answer and have zero confidence. Other than that, just because an algorithm can produce multiple possible outputs doesn't mean that those outputs are equiprobable. And your example algorithm is worse than just picking one of $a$, $b$, $c$, $d$, $e$ uniformly at random, so why would anyone ever use it? $\endgroup$ – David Richerby Dec 11 '18 at 21:40
  • $\begingroup$ @DavidRicherby Most of the assumptions here are just for the sake of the argument I'm trying to make (i.e. that running MC on non decision problems many times does not result in an increase of stochastic advantage). I know these outputs don't have to be equiprobable; I'm just assuming so for simplicity. Finally, showing that this algorithm is bad is the point: I'm interested in showing that there exists a $k$ such that running MC $k$ times on this problem gives me a final confidence of less than 50% in the answer. $\endgroup$ – Emilio Botero Dec 11 '18 at 21:47
  • $\begingroup$ When $k=70$, the probability that the wrong outcome would be the strict plurality answer is roughly 0.502. This is the minimal $k$ for which this probability exceeds 1/2. $\endgroup$ – Yuval Filmus Dec 11 '18 at 23:53
1
$\begingroup$

You can compute the probability that outcome $e$ is the unique plurality answer, when repeating the algorithm $k$ times, as follows: $$ \sum_{\substack{a+b+c+d+e=k \\ a,b,c,d,e \geq 0 \\ e > a,b,c,d}} \frac{n!}{a!b!c!d!e!} \left(\frac{1}{4}\right)^e \left(\frac{3}{16}\right)^{k-e}. $$ This can be computed explicitly. When $k = 70$, the probability is roughly $0.502$, and this is the minimal $k$ for which the probability exceeds $1/2$.

$\endgroup$
  • $\begingroup$ ... at which point, the correct thing to do is to output anything but $e$! $\endgroup$ – David Richerby Dec 12 '18 at 0:39
  • $\begingroup$ @YuvalFilmus can you please elaborate on your answer? I'm not sure I understand the formula. How did you go about finding this equation? So you run a summation over each possible answer, where the variable for the letter indicates how many times the algorithm outputs that variable? What is $n!$ in the formula? $\endgroup$ – Emilio Botero Dec 12 '18 at 0:52
  • $\begingroup$ Take it as an exercise. In my formula, $n!$ is $n$ factorial, and the term involving it is a multinomial coefficient. $\endgroup$ – Yuval Filmus Dec 12 '18 at 1:12
  • $\begingroup$ Can you then provide a hint or two to get started? Thank you for your answer. $\endgroup$ – Emilio Botero Dec 12 '18 at 1:36
  • $\begingroup$ The multinomial coefficient counts the number of outcomes with $a$ outputs “a”, ..., $e$ outputs “e”. The other factor is the probability of each such outcome. The sum is over all “bad” outcomes. $\endgroup$ – Yuval Filmus Dec 12 '18 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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