Theorie und Praxis des Zufalls //2306

Nur mal wieder ein kleiner Gedankengang.
Die Aufgabe beruht auf einem realen Programmierprojekt. Ich habe sie aber etwas abgewandelt und vereinfacht, um die Angelegenheit verständlicher zu machen.

Gegeben ist eine indizierte Liste mit – sagen wir – 25 unterschiedlichen Optionen.
Aus diversen Gründen können davon aber fünf Optionen nicht wahrgenommen werden. Welche das sind, ergibt sich erst zur Laufzeit. (Strenggenommen können es auch weniger als fünf sein, da die entsprechenden Optionen eventuell aus mehreren Gründen ausfallen, und dann teilweise identisch sind. Wir bleiben bei unserem Beispiel beim festen Wert 5.)
Ich möchte jetzt also – zufallsgesteuert – aus den verbleibenden Optionen eine auswählen.
Also werfe ich den Zufallsgenerator an, und lasse mir eine ganze Zahl zwischen 0 und 24 ausgeben. Dann prüfe ich nach, ob die Option mit diesem Index zulässig ist. In 80 Prozent der Fälle habe ich die endgültige Option bereits gefunden. Ansonsten mache ich einen weiteren Durchlauf, so lange, bis ich eine zulässige Option erhalte.
Das „Problem“ ist, dass ich rein theoretisch mit diesem Algorithmus in eine Endlosschleife geraten könnte.

Gehen wir mal davon aus, dass das Programm 1000 mal läuft. In 800 Fällen wird das Ergebnis (rein statistisch) auf Anhieb geschafft. In 160 weiteren beim zweiten Durchlauf. 32 Fälle brauchen drei Versuche. Bei nur 8 Fällen sind 4 oder mehr Durchläufe nötig.
Selbst wenn es 1000 Durchläufe wären, ginge das bei einem modernen Rechner ohne merkliche Zeitverzögerung. Aber rein mathematisch betrachtet, geht halt die Wahrscheinlichkeit, dass die Schleife (ohne zusätzliches Abbruchkriterium) endlos weiterläuft, nur asymptotisch gegen 0.
In der Praxis ist das jedoch kein Thema, und ich bin da einfach pragmatisch. Wie sollte das Programm auch reagieren, falls es tatsächlich mal nach tausend oder meinetwegen einer Million Durchläufen immer noch kein passendes Ergebnis gefunden hat?
Sofern man das Programm nur oft genug laufen lässt, wird allerdings auch das irgendwann mal passieren.

Während die genauen Zahlenwerte für den betrachteten Use Case eigentlich unerheblich sind, kann sich das Blatt durchaus wenden, wenn nur wenige erlaubte Optionen einer großen Zahl von ausgeschlossenen Werten gegenüberstehen.
Nehmen wir mal den umgekehrten Fall an: 20 unbrauchbaren Optionen stehen nur 5 akzeptable gegenüber. Bei insgesamt 1000 Läufen schaffen es auf Anhieb nur 200, beim zweiten Versuch 160, beim dritten 128, .. Wie man sieht, konvergiert die Sache wesentlich schlechter.
In diesem Fall wäre es wohl zweckmäßiger, von Anfang an einen anderen Algorithmus zu nutzen – z.B. sämtliche Optionen zufällig durchzumischen, und dann die Liste durchiterieren, um die erste gefundene erlaubte Option zu nehmen. Oder die verbotenen Optionen aus der Liste zu entfernen, um danach eine zufällige aus den verbliebenen zu nehmen. Oder .. Die beste Wahl hängt von der konkreten Ausgestaltung sowie weiteren Parametern und Zusatzbedingungen der Aufgabe ab.
Dass nicht schon von vornherein ein anderer Algorithmus benutzt wurde, hat historische Gründe. Ursprünglich stellte sich die Aufgabe einfacher dar, und die Notwendigkeit des Ausschlusses einzelner Optionen war noch nicht abzusehen gewesen. Flickwerk wie so vieles.