mercredi 6 février 2019

Probability amplification for a randomised algorithm

I missed the lecture on randomised algorithms and can't wrap my head around amplifying the probability of a two sided error algorithm.

Can someone explain why the probability that the following algorithm gives a correct output increase through repetition and how can that probability be calculated?

L is a formal language
If the input x ∈ L, the output of the algorithm will be YES with a probability of 2/3
If the input x !∈ L, the output of the algorithm will be NO with a probability > 1/2

Thank you in advance




Aucun commentaire:

Enregistrer un commentaire