Gilt die Gambler's Fallacy auch für Pseudo-Zufallszahlen aus dem Rechner?

[Ancient]

Agenommen wir haben einen Algorithmus der Pseudo-Zufallszahlen erzeugt und für den Folgendes gilt:
1. "Er" liefert auf lange Sicht gleichverteilte Zahlen.
2. Kennt man den Seed-Wert, können alle erzeugten Zahlen vorhergesagt werden.

Wir wissen alle, dass am Roulettetisch die Annahme "rot ist jetzt überfällig" wenn zuvor zehn mal hintereinander schwarz kam ein Trugschluss ist - aber wie sieht es mit pseudo-Zufallszahlen aus?
Nehmen wir an, der Computer erzeugt in einer Schleife zufällig entweder die Zahl 0 oder 1. Das Programm läuft los und es kommt zehn mal hintereinander die 0. Habe ich jetzt eine Chance minimal größer als 50%, dass die nächste Zahl 1 ist, weil der pseudo-Zufallsgenerator den Anspruch hat, gleichverteilte Zahlen zu liefern?

 

[Muthombo]

Die Definition der Pseudozufalls ist ja, dass der Betrachter ihn aus seiner Perspektive nicht vom echten Zufall unterscheiden kann. Wären die Ergebnisse beim Pseudozufall gleichmäßiger verteilt (im Schnitt kürzere Streaks) als beim echten, könnte er sie voneinander unterscheiden. Daher gilt die Gambler's Fallacy auch für den Pseudozufall.

 

[Ancient]

Kannst du etwas mehr dazu sagen? Ich finde es schwer nachvollziehbar, wie es moeglich sein soll einen deterministischen Algorithmus zu implementieren der gleichverteilte Zahlen garantiert (was der echte Zufall ja nicht tut?) aber gleichzeitig von aussen nicht vom echten Zufall zu unterscheiden ist.

Habe mal ein kleines Pythonscript geschrieben, fuer die paar Testlaeufe die ich gemacht habe zeigt sich keine Tendenz zu wins/losses > 1.

import random

rolls = 10000000000
streak = 1
wins = 0
losses = 0
bet = None

prev = random.randint(0,1)
for i in range(rolls - 1):
    curr = random.randint(0,1)
    if bet != None:
        if curr == bet:
            wins += 1
        else:
            losses += 1
    if prev == curr:
        streak += 1
    else:
        streak = 1
    bet = 1 - curr if streak >= 20 else None
    prev = curr

print('wins =', wins, '\tlosses =', losses, '\twins/losses =',\
       wins/losses if losses != 0 else 'NaN')

 

[mfb]

Kannst du etwas mehr dazu sagen? Ich finde es schwer nachvollziehbar, wie es moeglich sein soll einen deterministischen Algorithmus zu implementieren der gleichverteilte Zahlen garantiert (was der echte Zufall ja nicht tut?)

Die Frage nach der Verteilung ist erstmal unabhängig von echtem und Pseudozufall, aber beschränken wir uns beim echten Zufall mal auf Gleichverteilungen:
Doch, dann garantiert der echte Zufall Gleichverteilungen - per Definition! Das heißt aber eben, dass jede Zahl unabhängig von den vorherigen ist. Und somit hast du beim echten Zufall genau wie beim Pseudozufall nach egal welchen vorherigen Ergebnissen 50% Chance auf rot bzw. schwarz.

Edit: Um das noch etwas zu erweitern:
Keine Korrelation zwischen aufeinanderfolgenden Werten zu haben ist eines der wichtigsten Kriterien für Pseudozufallszahl-Algorithmen. Ein Algorithmus, der dort schon versagt, ist schlecht.

 

[freesta]

Es hängt wohl von der Qualität Algorithmus ab, auf Wikipedia gibts dazu eine Seite:
http://de.wikipedia.org/wiki/Spektraltest

edit: willst du ein online-spielcasino ausnehmen?

 

[zoiX]

Nutzen online-Kasinos nicht echten Zufall durch radioaktiven Zerfall o.ä.?

 

[GeckoVOD]

Sie nutzen die spanische Inquisition, mit der rechnet keiner.

Spoiler

Partypoker, 2 sec google, ka was die anderen machen.

Der innere Zustand des Zufallszahlengenerators ist gesichert und der Seed stammt aus einer Entropiequelle, die durch Überprüfung des Quelltextes und der Dokumentation verifiziert wurde.

Quelle

Ich meine irgendwo gelesen zu haben, dass viele Mikrofone und Umweltgeräusche (aus dem Meer?) nutzen. Weiß es echt nicht mehr genau.

 

[ducki]

Keine Korrelation zwischen aufeinanderfolgenden Werten zu haben ist eines der wichtigsten Kriterien für Pseudozufallszahl-Algorithmen. Ein Algorithmus, der dort schon versagt, ist schlecht.

und doch ist ein jeder PRNG nunmal deterministisch. auch wenn man das aus einer lokalen stichprobe nicht eindeutig erkennen kann, besteht immer irgendein verhältnis zwischen den pseudozufallszahlen.

Wir wissen alle, dass am Roulettetisch die Annahme "rot ist jetzt überfällig" wenn zuvor zehn mal hintereinander schwarz kam ein Trugschluss ist - aber wie sieht es mit pseudo-Zufallszahlen aus?
Nehmen wir an, der Computer erzeugt in einer Schleife zufällig entweder die Zahl 0 oder 1. Das Programm läuft los und es kommt zehn mal hintereinander die 0. Habe ich jetzt eine Chance minimal größer als 50%, dass die nächste Zahl 1 ist, weil der pseudo-Zufallsgenerator den Anspruch hat, gleichverteilte Zahlen zu liefern?

die frage lässt sich soweit ich das sehe nicht allgemein beantworten, bzw hier werden konzepte vermischt die die betrachtung erschweren.

sagen wir mal, wir haben einen algorithmus, der die bisher generierten zahlen zählt und die zahlen, die bisher weniger häufig generiert wurden, in der nächsten iteration mit größerer wahrscheinlichkeit erzeugt.
hier hätte der gambler recht! wenn die letzten 10 mal rot gefallen ist, wäre es sinnvoller, auf schwarz zu setzen.
ein solcher PRNG ist sehr schwach - zwar kommt man damit am ende wohl auf eine annähernde gleichverteilung, aber man bekommt zu wenig lange zahlenfolgen mit der gleichen zahl.

ein guter PRNG kann auch durchaus 20 mal hintereinander die gleiche zahl erzeugen - wie das beim echten zufall nunmal auch passiert.

was heißt das für den gambler?
echter zufall: trugschluss
schlechter PRNG: der gambler hat begrenzt recht
guter PRNG: geht am thema gambler's fallacy vorbei. wenn der gambler den algorithmus + seed kennt, kann er natürlich die nächste zahl voraussagen. wenn der gambler diese informationen nicht hat und der PRNG gut genug ist, ist das vorhersagen der nächsten zahl anhand der vorherigen zahlen aber sehr schwer.
die fallacy bezieht sich ja nur auf den echten zufall, und der hat nunmal kein gedächtnis. jeder PRNG - so gut er auch sein mag - ist deterministisch und hat eine art von 'gedächtnis'.

 

[mfb]

und doch ist ein jeder PRNG nunmal deterministisch. auch wenn man das aus einer lokalen stichprobe nicht eindeutig erkennen kann, besteht immer irgendein verhältnis zwischen den pseudozufallszahlen.

Natürlich. Aber das wird man (hoffentlich!) nicht daran bemerken, dass nach 10mal rot häufiger rot oder schwarz kommt.

sagen wir mal, wir haben einen algorithmus, der die bisher generierten zahlen zählt und die zahlen, die bisher weniger häufig generiert wurden, in der nächsten iteration mit größerer wahrscheinlichkeit erzeugt.
hier hätte der gambler recht! wenn die letzten 10 mal rot gefallen ist, wäre es sinnvoller, auf schwarz zu setzen.
ein solcher PRNG ist sehr schwach - zwar kommt man damit am ende wohl auf eine annähernde gleichverteilung, aber man bekommt zu wenig lange zahlenfolgen mit der gleichen zahl.

Da kann man gleich "rot, schwarz, repeat" implementieren. Ist nur noch minimal schlechter.

die fallacy bezieht sich ja nur auf den echten zufall, und der hat nunmal kein gedächtnis. jeder PRNG - so gut er auch sein mag - ist deterministisch und hat eine art von 'gedächtnis'.

Das heißt aber nicht, dass nach 10mal rot schwarz wahrscheinlicher wäre - es könnte auch rot wahrscheinlicher sein.

 

[Ancient]

ein guter PRNG kann auch durchaus 20 mal hintereinander die gleiche zahl erzeugen - wie das beim echten zufall nunmal auch passiert.

sicher, aber ist die chance dass zahl 21 jetzt eine andere wird bei einem "guten" PRNG minimal erhoeht (egal ob das nun dem gambler in der praxis einen vorteil bringt) oder nicht? d.h. muss ich den streak des PRNG nur hoch genug waehlen, meinetwegen tausend mal hintereinander die gleiche zahl, um eine merkbar erhoehte chance zu haben, dass zahl n+1 eine andere wird?

 

[ducki]

Natürlich. Aber das wird man (hoffentlich!) nicht daran bemerken, dass nach 10mal rot häufiger rot oder schwarz kommt.

Da kann man gleich "rot, schwarz, repeat" implementieren. Ist nur noch minimal schlechter.

Das heißt aber nicht, dass nach 10mal rot schwarz wahrscheinlicher wäre - es könnte auch rot wahrscheinlicher sein.

das stimmt soweit alles.
den schwachen PRNG habe ich gewählt, um zu zeigen, dass man u.U. voraussagen über die nächste zahl machen kann. der algorithmus ist natürlich völliger bullshit

sicher, aber ist die chance dass zahl 21 jetzt eine andere wird bei einem "guten" PRNG minimal erhoeht (egal ob das nun dem gambler in der praxis einen vorteil bringt) oder nicht? d.h. muss ich den streak des PRNG nur hoch genug waehlen, meinetwegen tausend mal hintereinander die gleiche zahl, um eine merkbar erhoehte chance zu haben, dass zahl n+1 eine andere wird?

bei den guten PRNG ist die chance bei in der praxis relevanten stichprobengrößen nicht erhöht. man nimmt an, dass eine zahlenfolge eines guten PRNG ohne kenntnis des seeds/algorithmus nicht von einer komplett zufälligen zahlenfolge (wo zahl 21 eben keine höhere wahrscheinlichkeit hat, anders zu rollen als die vorherigen 20) zu unterscheiden ist - darauf beruht mehr oder weniger die moderne kryptographie. bewiesen wurde hier aber noch nichts.

sicher ist, dass ein jeder PRNG periodisch ist und früher oder später anfängt, die gleichen zahlen erneut auszuspucken. in der praxis wegen riesiger perioden bei guten PRNG zwar nicht relevant, aber vielleicht hilft das beim gambler-problem?

ich weiß nicht ob ich deine frage zumindest zum teil beantworten konnte, aber ich bewege mich mit meinem wissen langsam auf ziemlich dünnes eis und möchte keine wagen behauptungen aufstellen. frag mich in ein paar semestern nochmal, vielleicht habe ich bis dahin mein kryptographie-wissen noch ein wenig vertieft
ist schon ein sehr interessantes thema, leider nur schrecklich unintuitiv.

 

[MegaVolt]

Ich glaube hier liegt ein Missverständnis bei der Gleichverteilung vor.
Gleichverteilung kann nicht garantiert werden und sollte es auch nicht. Bei keiner Art von Zufallsvariablen.
Wenn man Gleichverteilung garantiert dann muss zwangsläufig der "rot ist überfällig"-Effekt eintreten, weil ja dann ein Ereignis das andere ausgleichen würde.

Was bei (guten) Zufallszahlen stattdessen passiert ist folgendes:
Eine Stichprobe von n Ziehungen ist nicht gleich verteilt. Durch Zufall gibt es mehr rot als schwarz in der Stichprobe.
Dieses Ungleichgewicht bleibt bestehen und wird nie "kompensiert". Stattdessen werden bei neuen Ziehungen immer mehr Zahlen erzeugt, die für sich (wenn man nur n Ziehungen betrachtet) wieder nicht gleich verteilt sind.
Schickt man nun n gegen unendlich so macht die nicht-gleiche Verteilung der einzelnen Ziehungen auf die unendliche Menge nichts mehr aus und man hat im Mittel die Gleichverteilung. Das bedeutet aber nicht, dass irgendein endliches Teilstück der Ziehung jemals gleich verteilt sein müsste.

Nimmt man einen ganz simplen Primzahlen-Zufallsgenerator dann erfüllt der diese Voraussetzung eher nicht. Bei diesen sind die Zufallszahlen i.d.R. recht deutlich korreliert (siehe die oben verlinkte Seite zum Spektraltest). Gute Generatoren, insb. solche mit externen Entropiequellen, erfüllen das aber sehr gut. So gut, dass so ziemlich alle physikalischen Computersimulationen auf solchen Pseudozufallszahlen aufbauen. Gäbe es da Korrelationen würden all diese physikalischen Simulationen falsche Ergebnisse liefern. Das hätte schon lange auffallen müssen Allerdings ist die Wahl eines guten Zufallszahlengenerators sehr wichtig und Dissertationen auf dem Gebiet widmen der Auswahl eines passenden Generators in der Regel durchaus ein paar Seiten.

Die Frage im Topic würde ich also so beantworten: Es kommt auf den Pseudozufalszahlengenerator an. Ein schlechter wird Korrelationen haben, bei einem guten sollten diese nicht vorhanden bzw. in der Praxis undetektierbar niedrig sein.

 

[xornado]

Raute an MV.

Ein 'guter' generator ist eben dadurch ausgezeichnet, dass er allen bekannten zufallszahlengeneratorentests genügt. z.b. auch 'liefert er rot nach 100 mal schwarz mit höherer wsk?' etc.

 

[Ancient]

Danke fuer die Antworten allerseits
Ich lasse aus Spass an der Freude gerade das obige Pythonscript mit je 10 Milliarden rolls und streak >= 20 laufen, was pro Durchlauf auf meinem i3 so 6 Stunden dauert. Sobald ich ~50 Testergebnisse habe poste ich sie hier.

 

[MegaVolt]

Damit testest du aber "nur" den Standard-Python-Zufallszahlengenerator.
Diese Standard-Generatoren sind meist nicht besonders gut, d.h. hier würde ich Korrelationen erwarten.
Statt deinem Test kannst du aber auch den Spektraltest machen, der geht schneller.

Alternativ kannst du auch einen n-komponentigen Vektor nehmen (Spektraltest macht ja nur 3), der ist dann grafisch nicht mehr so schön darstellbar aber man kann auch "langreichweitige" Korrelationen finden. Ist natürlich deutlich aufwändiger.

http://de.wikipedia.org/wiki/Liste_von_Zufallszahlengeneratoren

 

[Ancient]

Damit testest du aber "nur" den Standard-Python-Zufallszahlengenerator.

Ist mir klar. Ich will ja auch Korrelation sehen.
Spektraltest mach ich auch nochmal.

 

[Ancient]

Hatte nur Bock auf 10 outputs zu warten:
rolls = 10000000000, streak >= 20

wins = 9608 losses = 9612 wins/losses = 0.9995838535164377
wins = 9441 losses = 9256 wins/losses = 1.0199870354364737
wins = 9440 losses = 9504 wins/losses = 0.9932659932659933
wins = 9541 losses = 9564 wins/losses = 0.9975951484734421
wins = 9561 losses = 9672 wins/losses = 0.9885235732009926
wins = 9603 losses = 9828 wins/losses = 0.9771062271062271
wins = 9558 losses = 9478 wins/losses = 1.0084405992825491
wins = 9420 losses = 9484 wins/losses = 0.9932517924926192
wins = 9609 losses = 9713 wins/losses = 0.9892927005044785
wins = 9513 losses = 9796 wins/losses = 0.9711106574111883

hm.

 

[mfb]

Etwa 1% Abweichung ist genau das, was du im Mittel erwarten würdest. Der letzte Wert fällt mit 2,9% Abweichung etwas heraus, kann aber trotzdem noch gut sein.

Als Differenz insgesamt ergibt sich -613 mit einer Standardabweichung von 437. Also kein Hinweis auf irgendeinen Effekt.

 

[ducki]

python nutzt standardmäßig Mersenne Twister, glaube nicht dass du da was findest.

It passes numerous tests for statistical randomness, including the Diehard tests.