Randomisierter Algorithmus
Bei randomisierten Algorithmen werden Zufallszahlen (in der Implementierung meist Pseudozufallszahlen) verwendet, um Algorithmen mit akzeptabler Laufzeit für komplizierte Probleme zu bekommen. Bei den meisten randomisierten Algorithmen "bezahlt" man allerdings für die gute Laufzeit damit, dass der Algorithmus mit einer beschränkten Wahrscheinlichkeit Fehler machen darf. Diese werden auch stochastische oder probabilistische Algorithmen genannt, allerdings sind nicht alle randomisierten Algorithmen probabilistisch (siehe unten).Ob ein Fehler auftritt oder nicht, hängt sowohl von der Eingabe (der Instanz des Problems) als auch von der Zufallszahl ab. Dadurch kann man durch wiederholtes Durchführen des Algorithmus (mit verschiedenen Zufallszahlen) das korrekte Ergebnis als das "mehrheitliche Ergebnis" ermitteln. Die genauen Wahrscheinlichkeiten dabei hängen von Details des Algorithmus ab, die allgemeine Idee ist jedoch Folgende:
- Voraussetzung: die Wahrscheinlichkeit für einen Fehler muss insgesamt (Ja- und Nein-Antworten) sein, sonst funktioniert die "Verstärkung der Wahrscheinlichkeit für die korrekten Antwort" (engl probability amplification) nicht
- Bei gleicher Eingabe ist die Wahrscheinlichkeit für einen Fehler beim ersten Durchlauf des Algorithmus also , beim zweiten und beim n-ten Durchlauf , also ziemlich klein, meist vernachlässigbar
Es gibt verschiedene Varianten von erlaubten Fehlern:
- einseitiger Fehler: Hier darf nur bei einer der möglichen Ausgaben (ja/nein) ein Fehler -- mit Wahrscheinlichkeit -- auftreten. Beispielsweise darf der Miller-Rabin-Test für die Primalität einer natürlichen Zahl zwar fälschlicherweise behaupten, die Zahl sei prim, wenn der Algorithmus aber ausgibt, dass es sich um eine zusammengesetzte Zahl handelt, dann ist diese Ausgabe garantiert korrekt. Wenn nach mehrfacher Ausführung des Algorithmus das Ergebnis jedesmal "Primzahl" lautete, kann man jedoch mit hoher Wahrscheinlichkeit davon ausgehen, dass dies zutrifft. (Für die genaue Abschätzung der Wahrscheinlichkeit wird in diesem Fall ein Ergebnis aus der Zahlentheorie benötigt).
- Beim zweiseitiger Fehler darf sowohl die ja als auch die nein-Antwort falsch sein. Um damit eine Gesamt-Fehlerwahrscheinlichkeit zu erreichen, muss die Wahrscheinlichkeit für jeden der beiden erlaubten Fehler sein, also kann man jeder Antwort davon ausgehen, dass sie mit einer Wahrscheinlichkeit von mehr als 50% korrekt ist. Damit ist analog zu den einseitigen Fehlern eine probability amplification möglich.