ich habe mal gelesen, daß es einen Algorithmus geben soll, mit dem ein faires Münzwurf-Spiel mit einer (unbekannt) gezinkten Münze möglich ist. Ich erinnere mich noch, daß man die Münze mehrmals werfen mußte, bis entschieden werden konnte, ob der Punkt an Spieler 1 oder 2 geht. Bei sehr stark gezinkter Münze braucht eine Entscheidung wahrscheinlich sehr lange. Mehr weiß ich nicht mehr und komme durch Nachdenken auch nicht selbst auf die Lösung (was wahrscheinlich peinlich ist, aber was solls!)…
Kann mir jemand diesen Algorithmus verraten und am besten auch noch den mathematischen Hintergrund, warum die Gewinnchancen für die beiden Spieler dann 1:1 sind?
daß es einen Algorithmus geben soll, mit
dem ein faires Münzwurf-Spiel mit einer (unbekannt) gezinkten
Münze möglich ist.
hast Du einen Bitstrom mit nicht gleichverteilten Zufallsbits, die keine Korrelationen untereinander aufweisen, und tust damit folgendes…
Die Bits des Bitstroms werden (beginnend mit dem ersten Bit) in Zweiergruppen zusammengefaßt;
Alle Gruppen mit identischen Bits („00“ und „11“) interessieren nicht und werden verworfen/„ausgefiltert“;
Von den verbleibenden Gruppen („01“ und „10“) wird nur das jeweils erste Bits genommen. Diese Bits bilden die neue Sequenz.
…dann ist die resultierende Sequenz ein Bitstrom mit exakt gleichverteilten Bits (je genau 50% für „0“ und „1“)! Der einfache Grund dafür ist, daß die Wahrscheinlichkeiten der Kombinationen „01“ und „10“ immer gleich sind. Nachteilig bei diesem Verfahren ist, daß höchstens 1/4 der Eingabe-Bits übrigbleiben (der best case liegt dann vor, wenn bereits der ursprüngliche Strom Gleichverteilung aufweist).
Das Verfahren wird zur Symmetrierung von „echten“, d. h. physikalischen Zufallsgeneratoren verwendet. Man kann z. B. das Rauschen einer Zenerdiode verstärken und dieses Signal abtasten. Die Verstärkung kann man so wählen, daß ein Samplewert mit einer Wahrscheinlichkeit von _ungefähr_ 50 % unter-/oberhalb eines bestimmten Schwellenwertes liegt (= Kriterium dafür, ob das Ergebnisbit 0 oder 1 ist), aber man kann sie nicht so genau einstellen, daß die Wahrscheinlichkeit _genau_ 50 % beträgt. Um dies zu erreichen, hat man zwei Möglichkeiten:
a) man bedient sich des obigen Verfahrens. Dann muß man jedoch ein Absinken der ursprünglichen Generationsrate auf ca. 1/4 in Kauf nehmen.
b) man generiert mit einem Pseudo-Zufallsgenerator, d. h. per Algorithmus, eine zweite Bitsequenz gleicher Rate, die von Haus aus Gleichverteilung aufweist (das sicherzustellen ist kein Problem). Beide Sequenzen verknüpft man mit einem XOR-Gatter. Dann entscheidet jedes Bits aus der echten, aber (schwach) ungleichverteilten Sequenz darüber, ob sein „Partner“ in der pseudohaften, aber gleichverteilten Sequenz umgeklappt wird. Die Ergebnissequenz ist gleichverteilt und einer echten ebenbürtig. Der Vorteil dieser Methode ist, daß sie keine Geschwindigkeitseinbuße mit sich bringt.
Das beste was mir einfiele wäre der sogenannte „Random Walk“ und „Martingal“. Bei einem Random Walk ist es allerdings wahrscheinlicher, das der einmal Führende seinen Vorteil nicht verliert, weil sein ‚Gewinn‘ erstmal ausgeglichen werden muss. Aber eigentlich ist das nur eine Modifikation des normalen Münzwurfs, in dem erst nach x (x>=2) Würfen entschieden wird, wer gewinnt.