Recall that a false-biased Monte Carlo (MC) algorithm is always correct when it returns false for some decision problem i.e. it has a one sided error and its always correct on NO instances.

Assume that we have a false-biased MC algorithm. In this case when it says NO its always correct. This means that it is not allowed to say NO on YES instances (otherwise, it would make a mistake). So on YES instances it always says YES (and never NO) and when it says NO in NO instances, its correct. In other words:

So if the answer to some problem is YES, then algorithm $A$ will always output YES, while if the answer is NO, it will output NO with probability at least $\frac{1}{3}$.

What confuses me is how one would calculate the probability of the algorithm being correct (say, for only 1 run of it, we can extend it to amplification if we want later). I was told that such an algorithm as described above has probability at least $\frac{1}{3}$ of being correct (i.e. $Pr[\text{correct}] \geq \frac{1}{3}$), however, I wasn't sure how to formally justify this.

These are my thought. For calculating the probability of the algorithm being correct I would write down the total law of probability (and Bayes rule)to decide if its correct:

$$ Pr[correct] = Pr[correct \mid \text{NO instance} ] P[\text{NO instance}] + Pr[correct \mid \text{YES instance} ] P[\text{YES instance}] $$

$$ Pr[correct] = Pr[A(x) = NO \mid \text{NO instance} ] P[\text{NO instance}] + Pr[A(x) = YES \mid \text{YES instance} ] P[\text{YES instance}] $$

However, it seems that this is not the approach people take when talking about the correctness of an MC algorithm. I understand that in this paradigm of algorithms one does not think of the input as being randomized, so, is the standard thing to say that the probability of getting any instances is 0.5?

In that case we have:

$$ Pr[correct] = Pr[A(x) = NO \mid \text{NO instance} ] \frac{1}{2} + Pr[A(x) = YES \mid \text{YES instance} ] \frac{1}{2} $$

$$ \geq \frac{1}{3} \cdot \frac{1}{2} + \frac{1}{2} = \frac{2}{3}$$

From my analysis, it seems that the correct thing to say is its correct with probability at least $2/3$ however, one would say that its correct with prob at least $\frac{1}{3}$? I guess it is still correct but I am unsure if this is the correct way to think about it and also why one would say instead that the probability of it being correct is $\frac{1}{3}$ and not $\frac{2}{3}$? (I know that amplification makes which constant we say meaningless, but my question is not about which one we say, but rather how does one calculate the probability of a randomized algorithm being correct).

It seems to me that the usual way to think about it is to consider which type of instance we get separately but I don't quite understand why that is the case. I am saying that is the "usual" way because of the following excerpt:

enter image description here

I just want to clarify that I do understand how they got $1 - (\frac{2}{3})^k$ and that isn't what is confusing me. What is confusing me is how one deals with conditional probabilities in Monte Carlo algorithms and how one uses the total law of probability (and marginalization) to deal with these probabilistic events.

I guess my question can also be phrased as why goes the following phrase:

A randomized algorithm for a decision problem with one-sided-error and correctness probability $\frac{1}{3}$

equivalent to:

that is, if the answer is YES, it will always output YES, while if the answer is NO, it will output NO with probability 1/3.

From what I am reading from the solutions, it seems to me that one says an MC algorithm is correct if for each instances NO and YES, for both cases, the algorithm A outputs a correct answer with probability greater than whatever constant one is aiming for...and one doesn't involve the probabilities of the instances because we don't think of the probability of those events?

In other words, an MC algorithm being correct with prob greater than 0.5 doesn't mean we consider the event:


instead, we consider the probability of correct for each instances separately and if both satisfy the inequality that we need, then the algorithm succeeds with the desired probability?


1 Answer 1


We say that a randomized algorithm $A$ has success probability $p$ if

  • On a YES instance $x$, $\Pr[A(x)=YES] \geq p$.
  • On a NO instance $x$, $\Pr[A(x)=NO] \geq p$.

We say that a randomized algorithm $A$ has one-sided success probability $p$ if

  • On a YES instance $x$, $\Pr[A(x)=YES] = 1$.
  • On a NO instance $x$, $\Pr[A(x)=NO] \geq p$.

In all cases, the probability is taken (only) over the coin tosses of the algorithm. We can't take probability over $x$ since we are not given any distribution over instances.

The exercise has a slightly unorthodox definition that is useful mostly for the exercise (with $=$ instead of $\geq$).

These definitions are worst-case – the success probability of the algorithm (which can be taken as the optimal $p$) depends on the worst input. In a distributional setting – in which there is a distribution on the instances – we can also consider $\Pr[A(x)=T(x)]$, where $T(x)$ is the type of $x$, and this time the probability is taken over both $x$ and the coin tosses of the algorithm. In this setting it is also common to consider deterministic algorithms. We can consider both two-sided and one-sided algorithms in this setting as well.

  • $\begingroup$ I am trying to understand it further than what the exercise is talking about. Is the probability of correctness of an MC algorithm decided based on looking at the probability of it being correct on each case when it receives a YES instance and a NO instance? The equality is of literally, zero interest to me. What I care about is knowing what the phrase "An MC algorithm is correct with probability p" means exactly. $\endgroup$ Nov 2, 2015 at 22:34
  • $\begingroup$ The probability is calculated for each instance separately. The sample space is the coin tosses of the algorithm. $\endgroup$ Nov 2, 2015 at 22:37
  • $\begingroup$ So how exactly does one calculate the event Pr[correct] if the coin tosses of the algorithm are the sample space? I am still confused on how one decides if the algorithm succeeds with probability at least p. Is that true whenever the algorithm satisfies $Pr[A(x) = Yes | Yes ] \geq p$ and $Pr[A(x) = No | No ] \geq p$? $\endgroup$ Nov 2, 2015 at 22:41
  • 1
    $\begingroup$ No. There is no such thing as Pr[correct]. A two-sided algorithm succeeds with probability $p$ if for an instance $x$ of type $T(x)$, $\Pr[A(x)=T(x)] \geq p$. We never take any kind of probability over $x$, since there is no distribution of instances given to us. $\endgroup$ Nov 2, 2015 at 22:57
  • $\begingroup$ There is a different definition for one-sided algorithms, but you already know it. $\endgroup$ Nov 2, 2015 at 22:58

Your Answer

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

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