A.S.: Yep, anscheinend ist der Singular von ‚Würfel‘ ‚die‘. 😉
Eine knifflige Programmieraufgabe kursiert im Internet, die, wie Sie vielleicht aus meinem Versuch eines pragmatischen Titels erraten haben, wie folgt formalisiert werden kann:
Geben Sie eine Funktion vor, die eine gleichmäßige Zufallszahl zwischen 1 und 5 (einschließlich) zurückgibt, entwerfen Sie eine Funktion, die eine gleichmäßige Zufallszahl zwischen 1 und 7 (einschließlich) zurückgibt.
Wenn die Überschneidung von Algorithmen und Statistik Ihr Ding ist, dann versuchen Sie es doch einfach mal! Eine zusätzliche Herausforderung besteht darin, Ihren Algorithmus zeitlich zu begrenzen. Ich fand das eine unterhaltsame Übung, nur um festzustellen, dass hier fundamentale Grenzen im Spiel sind.
Natürlich ist mit einem Würfel hier ein vollkommen einheitlicher Zufallsgenerator gemeint, der nur in der Theorie existiert. In der realen Welt unterliegen Würfel den Naturgesetzen und den Unzulänglichkeiten der Umwelt, so dass sie nur eine (wenn auch gute) Annäherung an dieses abstrakte Modell darstellen.
Eine unbeschränkte Lösung
Lassen Sie uns eine Familie von unbeschränkten Algorithmen betrachten. Um einen Zufallsgenerator zu erzeugen, der mindestens 7 Ergebnisse hat, müssen wir den 5-seitigen Würfel mindestens zweimal werfen. Zweimal würfeln ergibt 5^2=25 mögliche Ergebnisse, und obwohl dies kein Faktor 7 ist, können wir die ersten 21 Ergebnisse 7 Gruppen der gleichen Größe 3 zuordnen. Wenn wir jedoch bei einem der verbleibenden 4 Ergebnisse landen, muss das Verfahren neu gestartet werden. Wir können nicht einfach einen dieser 4 unglücklichen Endzustände einer Ausgabe zuordnen, da dies die Eigenschaft der gleichmäßigen Zufälligkeit durcheinander bringen würde.
In der obigen Grafik stellen die Kreise „Zustände“ unseres Programms dar, und der Text darin ist der letzte Wert des gewürfelten Würfels. Die grünen Kästchen stellen dann die Ausgabe dar, die wir je nach Endzustand (= nach zweimaligem Würfeln) zuweisen. In 84 % der Fälle erhalten wir nach zwei Würfen eine Ausgabe und der Algorithmus ist beendet. Wie Sie sehen können, ist eine Schleife vorhanden, die den Algorithmus unbegrenzt macht. Das bedeutet, dass für jede ganze Zahl, egal wie groß sie ist, eine kleine, aber von Null abweichende Wahrscheinlichkeit besteht, dass die Gesamtzahl der Würfe diese Menge überschreitet, um einen Ausgabewert zu berechnen. Echtzeitanwendungen mit strengen Zeitvorgaben kommen daher nicht in Frage, es sei denn, man ist bereit, Kompromisse bei der statistischen Genauigkeit des Algorithmus einzugehen.
Eine Variante dieser Lösung würfelt zunächst bis zu drei Würfel, bevor sie neu gestartet wird: Dadurch entstehen 5^3=125 Endzustände, und wir können höchstens 119 davon 7 Gruppen gleicher Größe 17 zuordnen. Jetzt besteht eine Wahrscheinlichkeit von 95,2 %, dass das Spiel nach maximal drei Würfen beendet ist. Man beachte, dass wir im Durchschnitt weniger oft würfeln müssen als vorher (280/119 ≈ 2,35 gegenüber 50/21 ≈ 2,38), weil wir meist schon nach den ersten beiden Würfen eine Abkürzung nehmen und diese Zwischenzustände direkt einem Ausgang zuordnen können. Diese durchschnittliche Anzahl von Würfen sinkt weiter, wenn wir den Trend fortsetzen.
Wenn Sie mit der Informationstheorie vertraut sind, dann bedenken Sie, dass ein Wurf eines 5-seitigen Würfels (= rand5) log2(5) ≈ 2,32 Bits an Information erzeugt, und ein Wurf eines 7-seitigen Würfels (= rand7) log2(7) ≈ 2,81 Bits an Information erzeugt. Es stellt sich heraus, dass wir im Grenzfall nur log(7)/log(5) ≈ 1,21 Aufrufe von rand5 für jeden rand7-Wert benötigen, den wir erhalten möchten. Die genaue Implementierung, die beliebig nahe an dieser Grenze arbeitet, ist ziemlich kompliziert und würde den Rahmen dieses Artikels sprengen. Wir müssten zwischen mehreren Aufrufen von rand7 Zustandsinformationen speichern, und der Algorithmus, der mir vorschwebt, ist nicht nur in der Zeit, sondern auch im Speicher unbegrenzt. Ich lade Sie gerne ein, mir eine Methode mitzuteilen, die dieses letzte Problem löst!
Eine beschränkte Lösung
Es gibt keinen beschränkten Algorithmus, der einen vollkommen gleichmäßigen Zufallswert zwischen 1 und 7 berechnet, wenn ein Zufallsgenerator nur zwischen 1 und 5 vorhanden ist. Betrachten Sie die Familie der unbeschränkten Lösungen oben. Wie ich bereits angedeutet habe, gibt es an jedem Punkt immer eine gewisse Anzahl von „Restzuständen“ (zwischen 1 und 6), die den Algorithmus zu einem Neustart veranlassen. Das liegt daran, dass 5 und 7 Primzahlen sind und keine Potenz von 5 jemals ein Vielfaches von 7 sein kann. So verlockend es auch sein mag, den kleinen Satz von Fermat anzuwenden, solche Versuche werden zu Fehlern führen, da die grundlegende Zahlentheorie eine begrenzte Lösung in dieser Familie unmöglich macht.
Sie könnten zu Recht darauf hinweisen, dass die Anzahl der Endzustände nicht immer eine Potenz von 5 ist, zum Beispiel im Fall von „bis zu drei Würfen“, wo wir bereits nach zwei Würfen Abkürzungen nehmen können. Vielleicht könnte man das Zustandsdiagramm so gestalten, dass ein beschränkter Algorithmus mit Pfaden variabler Länge und 7n Endzuständen entsteht? Man bedenke jedoch Folgendes:
- Diese Endzustände werden nicht gleich wahrscheinlich sein, weil nicht jeder Pfad gleich lang ist (= Anzahl der rand5-Aufrufe).
- Wir können den Baum sehr leicht erweitern, um jeden Pfad gleich lang zu machen, indem wir rand5 unnötigerweise immer dann entsprechend oft aufrufen, wenn wir uns in einem vorzeitigen Endzustand befinden. Jetzt wird die Anzahl der Endzustände wieder zu einer Potenz von 5, und alle Endzustände sind gleich wahrscheinlich.
Dies ist natürlich kein formaler Beweis, aber ich hoffe, Ihnen eine gewisse Intuition für das Problem vermittelt zu haben. Wie wir sehen, kann ein Problem manchmal sehr realistisch erscheinen, nur um dann über mathematische Fakten wie diese zu stolpern. Können Sie nach dieser Analyse herausfinden, ob es möglich ist, einen 8-seitigen Würfel ausgehend von einem 4-seitigen Würfel zu simulieren?