Randomized algorithms are algorithms that have access to a source of randomness. This means that their execution path and their outputs are both random. In general, we might be interested in making statements like the following:
It turns out that there are problems for which we can find efficient and likely to be correct randomized algorithms and for which we cannot find equally efficient deterministic algorithms. There are open questions in computational complexity about what exactly randomness buys us!
Broadly, there are 2 families of randomized algorithms: