Suppose we have black-box access to a function that returns the roots of some unknown 5-degree polynomial in each invocation. (So there will be 5 roots.)
But we also know that the function is probabilistic. In each invocation, it returns a true root with 0.8 probability, and it outputs a random value with 0.2 probability.
Say we do r invocation of the algorithm, and we are tasked to learn the roots of the unknown polynomial with very high confidence $\delta$ (= 0.9).
Now, what is the probability of a false negative -- not identifying one or more of the true roots of the unknown polynomial from the output of the function invocations?
I thought that after r invocations, we could draw a frequency histogram and identify the correct roots, but there could be two scenarios where we can have false negatives:
When one of the random values is also outputted too many times and hence pretending to be a correct root. This particular random value will be a false positive, but since we are going to select only 5 values from the histogram, hence we will not be picking a correct root and hence contributing toward a false negative scenario. In this case, the probability of a false negative should be $\frac{0.2}{N-5}^{r/5}$
Say t roots among the 5 roots are clearly visible from the histogram, but the remaining 5-t roots appear with almost the same frequency as the other random values.
I am not sure how to calculate the probability in Case 2 above and also the total false negative probability.