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.

Improve this question
$\endgroup$
3
  • 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, 2018 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, 2018 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, 2018 at 23:53

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ ... at which point, the correct thing to do is to output anything but $e$! $\endgroup$
    – David Richerby
    Dec 12, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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