I was trying to understand the definition of what it meant to say that a Monte Carlo (MC) algorithm succeeds with probability at least $p$.
Usually in probability I would have concluded that the probability would be something like:
$$ Pr[correct] = Pr[correct \mid \text{NO instance} ] P[\text{NO instance}] + Pr[correct \mid \text{YES instance} ] P[\text{YES instance}] $$
however, in that paradigm of algorithm analysis, there is no distribution of the instances of a problem. Therefore, that seemed an incorrect way to calculate the probability of a MC algorithm being correct.
So does one say an algorithm $A$ succeeds with probability at least $p$ if the following two conditions are met:
$$ Pr[A(x) = No \mid \text{NO instance} ] \geq p \wedge Pr[A(x) = Yes \mid \text{Yes instance} ] \geq p $$
?
Or does one do some other manipulation of $Pr[A(x) = No \mid \text{NO instance} ]$ and $Pr[A(x) = Yes \mid \text{Yes instance} ] $ to decide if to call its success rate at least $p$?