What is the advantage of probability algorithm?

What is advantage of probability algorithm (we usually use randomized algorithm instead of probability algorithm)? Well this is a big question, e.g. we don’t know if $P = BPP$, if so then we would say that deterministic algorithm is the same as randomized algorithm. If not, i.e. $P ne BPP$ then randomized algorithm gives us more power than deterministic algorithm. I think randomized algorithm can give us some polynomial speed up but I’m not sure if it can give us an exponential speed up over deterministic.

Note that P is the class of all problems that can be done by efficient algorithm (i.e. polynomial algorithm in the size of the input) while BPP stands for Bounded-error Probabilistic Polynomial time, i.e. it contains all problems that have a non-deterministic TM with at least 1/2 of the branches accepts and less than 1/3 of the branches rejects.

A quick example of a randomized algorithm is verifying polynomial identities, e.g. given (x+2)(x-4)(x+22)(x-43)(x+11) = x^5-2x+4. The question is: Can you verify that the right-hand side is equal to the left hand side? One way to do is to multiply all terms together which takes O(n^2) where n is the number of terms. But we can do it in O(n) time by selecting some random number and text whether they are equal or not. Yes, there is a probability of wrong answer, but with many run of the algorithm (say 100) if there is at least one counterexample, then this is enough.

There are two major textbooks in randomized algorithm which are:

  • Probability and Computing – Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal

  • Randomized Algorithm By Rajeev Motwani and Prabhakar Raghavan

I recommend the first since it is easier and have one or more examples in each chapters while the second is good if you are interested in randomized complexity.