ein Algorithmus, der mit zufälligen Bits arbeitet, die in den Anwendungen Pseudozufallszahlen sind.

Somit besteht ein randomisierter Algorithmus aus einer Klasse von Algorithmen und einer Wahrscheinlichkeitsverteilung auf dieser Klasse. Randomisierte Algorithmen können wesentlich effizienter sein als die besten bekannten deterministischen Algorithmen.

Wenn ein Algorithmus seine Aufgabe lösen kann, indem er eines von m guten Objekten aus einer Menge von 2m Objekten benutzt, sind deterministisch im worst case m +1 Versuche nötig, während bei zufälliger Wahl durchschnittlich zwei Versuche genügen.