Zufällig ist kaum zufällig?

79

Ich habe dies getan, um die Zufälligkeit von Randint zu testen:

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

Ich habe ungefähr 10 Mal mehr versucht und das beste Ergebnis waren 121 Iterationen vor einem Repeater. Ist dies das beste Ergebnis, das Sie mit der Standardbibliothek erzielen können?

Orokusaki
quelle
56
"The Pragmatic Programmer", Regel 26. "select" Isn't Broken. Es kommt selten vor, dass ein Fehler im Betriebssystem oder im Compiler oder sogar in einem Produkt oder einer Bibliothek eines Drittanbieters auftritt. Der Fehler ist höchstwahrscheinlich in der Anwendung. Oder in diesem Fall die Anwendung der Wahrscheinlichkeitstheorie.
10
Nur Nitpicking: uniques = set () und uniques.add (x) wären geeigneter (effizienter).
Eric O Lebigot
22
Eine der Schlüsseleigenschaften des Geburtstagsparadoxons ist, dass es nicht intuitiv ist. Wenn Sie sich dessen nicht bewusst sind oder keinen Hintergrund in der Wahrscheinlichkeitstheorie haben, haben Sie nicht unbedingt einen Grund, eine Stichwortsuche danach durchzuführen. Einer der USPs von Q & A-Sites ist, dass Sie eine Frage in Begriffen stellen können, die niemals zu Antworten auf die Frage passen würden, wenn Sie eine reine Keyword-Suche durchgeführt hätten, ohne zu wissen, wonach Sie suchen sollen.
ConcernedOfTunbridgeWells
7
@okoku: (in Bezug auf Ihre Antwort auf ConcernedOfTunbridge): Was Sie sprechen, ist ein ganz anderes Problem. Eine ist die Wahrscheinlichkeit, zweimal hintereinander dieselbe Karte zu erhalten. die andere ist die Wahrscheinlichkeit, ANY der vorhergehenden N-1 - Karten nach N - Picks. Die durchschnittliche Anzahl von Karten aus einem perfekten RNG für das zweite Problem sollte ungefähr 67 betragen. Wenn man bedenkt, dass man zwischen 8 und 121 hat, klingt das ungefähr richtig.
BlueRaja - Danny Pflughoeft
5
Sie verwechseln Random mit Evenly Distributed. Es ist durchaus gültig, dass ein Zufallsgenerator immer und immer wieder genau denselben Wert zurückgibt. Wenn Sie einen gleichmäßig verteilten Zufallszahlengenerator wünschen, der ein völlig anderes Problem darstellt, handelt es sich um ein Mischproblem und nicht um ein Generatorproblem.

Antworten:

287

Das Geburtstagsparadoxon oder warum PRNGs häufiger Duplikate produzieren, als Sie vielleicht denken.


Es gibt ein paar Probleme im OP-Problem. Eines ist das oben erwähnte Geburtstagsparadoxon und das zweite ist die Art dessen, was Sie generieren, was nicht von Natur aus garantiert, dass eine bestimmte Zahl nicht wiederholt wird.

Das Geburtstagsparadoxon gilt, wenn ein bestimmter Wert während des Zeitraums des Generators mehrmals auftreten kann - und daher innerhalb einer Stichprobe von Werten Duplikate auftreten können. Das Geburtstagsparadoxon hat zur Folge, dass die tatsächliche Wahrscheinlichkeit, solche Duplikate zu erhalten, sehr hoch ist und der durchschnittliche Zeitraum zwischen ihnen kleiner ist, als man sonst gedacht hätte. Diese Dissonanz zwischen den wahrgenommenen und tatsächlichen Wahrscheinlichkeiten macht das Geburtstagsparadoxon zu einem guten Beispiel für eine kognitive Verzerrung , bei der eine naive intuitive Schätzung wahrscheinlich völlig falsch ist.

Eine kurze Einführung in Pseudo-Zufallszahlengeneratoren (PRNGs)

Der erste Teil Ihres Problems besteht darin, dass Sie den exponierten Wert eines Zufallszahlengenerators in eine viel kleinere Zahl umwandeln, sodass der Platz für mögliche Werte verringert wird. Obwohl einige Pseudozufallszahlengeneratoren während ihrer Periode keine Werte wiederholen, ändert diese Transformation die Domäne in eine viel kleinere. Die kleinere Domain macht die Bedingung "Keine Wiederholungen" ungültig, sodass Sie mit einer erheblichen Wahrscheinlichkeit von Wiederholungen rechnen können.

Einige Algorithmen, wie das lineare kongruente PRNG ( A'=AX|M) , garantieren die Eindeutigkeit für den gesamten Zeitraum. In einer LCG enthält der generierte Wert den gesamten Zustand des Akkumulators und es wird kein zusätzlicher Zustand gehalten. Der Generator ist deterministisch und kann eine Zahl innerhalb der Periode nicht wiederholen - jeder gegebene Akkumulatorwert kann nur einen möglichen aufeinanderfolgenden Wert implizieren. Daher kann jeder Wert innerhalb der Periode des Generators nur einmal auftreten. Die Periode eines solchen PRNG ist jedoch relativ klein - etwa 2 bis 30 für typische Implementierungen des LCG-Algorithmus - und kann möglicherweise nicht größer als die Anzahl unterschiedlicher Werte sein.

Nicht alle PRNG-Algorithmen teilen diese Eigenschaft. Einige können einen bestimmten Wert innerhalb des Zeitraums wiederholen. Im OP-Problem hat der Mersenne-Twister- Algorithmus (der in Pythons Zufallsmodul verwendet wird) eine sehr lange Periode - viel größer als 2 ^ 32. Im Gegensatz zu einem linearen kongruenten PRNG ist das Ergebnis nicht nur eine Funktion des vorherigen Ausgabewerts, da der Akkumulator einen zusätzlichen Zustand enthält. Bei einer 32-Bit-Ganzzahlausgabe und einem Zeitraum von ~ 2 ^ 19937 kann eine solche Garantie unmöglich gegeben werden.

Der Mersenne Twister ist ein beliebter Algorithmus für PRNGs, da er gute statistische und geometrische Eigenschaften und einen sehr langen Zeitraum aufweist - wünschenswerte Eigenschaften für ein PRNG, das in Simulationsmodellen verwendet wird.

  • Gute statistische Eigenschaften bedeuten, dass die vom Algorithmus erzeugten Zahlen gleichmäßig verteilt sind, ohne dass Zahlen mit einer signifikant höheren Wahrscheinlichkeit erscheinen als andere. Schlechte statistische Eigenschaften können zu unerwünschten Abweichungen in den Ergebnissen führen.

  • Gute geometrische Eigenschaften bedeuten, dass Mengen von N Zahlen nicht auf einer Hyperebene im N-dimensionalen Raum liegen. Schlechte geometrische Eigenschaften können zu falschen Korrelationen in einem Simulationsmodell führen und die Ergebnisse verzerren.

  • Ein langer Zeitraum bedeutet, dass Sie viele Zahlen generieren können, bevor die Sequenz zum Start führt. Wenn ein Modell eine große Anzahl von Iterationen benötigt oder von mehreren Seeds ausgeführt werden muss, sind die etwa 2 ^ 30 diskreten Zahlen, die für eine typische LCG-Implementierung verfügbar sind, möglicherweise nicht ausreichend. Der MT19337-Algorithmus hat eine sehr lange Periode - 2 ^ 19337-1 oder ungefähr 10 ^ 5821. Zum Vergleich: Die Gesamtzahl der Atome im Universum wird auf etwa 10 ^ 80 geschätzt.

Die von einem MT19337 PRNG erzeugte 32-Bit-Ganzzahl kann möglicherweise nicht genügend diskrete Werte darstellen, um eine Wiederholung während eines so großen Zeitraums zu vermeiden. In diesem Fall treten bei einer ausreichend großen Stichprobe wahrscheinlich doppelte Werte auf, die unvermeidlich sind.

Das Geburtstagsparadoxon auf den Punkt gebracht

Dieses Problem ist ursprünglich definiert als die Wahrscheinlichkeit, dass zwei Personen im Raum denselben Geburtstag haben. Der entscheidende Punkt ist, dass zwei Personen im Raum einen Geburtstag teilen können. Menschen neigen dazu, das Problem naiv als die Wahrscheinlichkeit zu interpretieren, dass jemand im Raum einen Geburtstag mit einer bestimmten Person teilt. Dies ist die Quelle der kognitiven Vorurteile , die häufig dazu führen, dass Menschen die Wahrscheinlichkeit unterschätzen. Dies ist die falsche Annahme - es ist nicht erforderlich, dass die Übereinstimmung mit einer bestimmten Person erfolgt und zwei Personen übereinstimmen können.

Diese Grafik zeigt die Wahrscheinlichkeit eines gemeinsamen Geburtstages, wenn die Anzahl der Personen im Raum zunimmt.  Für 23 Personen liegt die Wahrscheinlichkeit, dass zwei einen Geburtstag teilen, bei etwas mehr als 50%.

Die Wahrscheinlichkeit, dass eine Übereinstimmung zwischen zwei Personen auftritt, ist viel höher als die Wahrscheinlichkeit einer Übereinstimmung mit einer bestimmten Person, da die Übereinstimmung nicht mit einem bestimmten Datum erfolgen muss. Vielmehr müssen Sie nur zwei Personen finden, die denselben Geburtstag haben. Aus dieser Grafik (die auf der Wikipedia-Seite zu diesem Thema zu finden ist) können wir ersehen, dass wir nur 23 Personen im Raum benötigen, damit eine 50% ige Chance besteht, zwei Personen zu finden, die auf diese Weise übereinstimmen.

Aus dem Wikipedia-Eintrag zu diesem Thema können wir eine schöne Zusammenfassung erhalten. Im OP-Problem haben wir 4.500 mögliche "Geburtstage" anstelle von 365. Für eine bestimmte Anzahl von generierten Zufallswerten (entspricht "Personen") möchten wir die Wahrscheinlichkeit kennen, dass zwei identische Werte in der Sequenz auftreten.

Berechnung der wahrscheinlichen Auswirkung des Geburtstagsparadoxons auf das OP-Problem

Für eine Folge von 100 Zahlen haben wir (100 · 99) / 2 = 4950 Paare (siehe Das Problem verstehen ), die möglicherweise übereinstimmen könnten (dh die erste könnte mit der zweiten, dritten usw. übereinstimmen, die zweite könnte mit der dritten, vierten usw. übereinstimmen usw.) Die Anzahl der Kombinationen , die möglicherweise übereinstimmen könnten, beträgt eher mehr als nur 100.

Aus der Berechnung der Wahrscheinlichkeit erhalten wir einen Ausdruck von 1 - (4500! / (4500 ** 100 * (4500 - 100)!) . Das folgende Snippet des Python-Codes führt eine naive Bewertung der Wahrscheinlichkeit des Auftretens eines übereinstimmenden Paares durch.

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

Dies ergibt ein vernünftig aussehendes Ergebnis von p = 0,669 für eine Übereinstimmung innerhalb von 100 Zahlen, die aus einer Population von 4500 möglichen Werten abgetastet wurden. (Vielleicht könnte jemand dies überprüfen und einen Kommentar posten, wenn es falsch ist). Daraus können wir ersehen, dass die vom OP beobachteten Lauflängen zwischen übereinstimmenden Zahlen durchaus vernünftig erscheinen.

Fußnote: Verwenden von Shuffling, um eine eindeutige Folge von Pseudozufallszahlen zu erhalten

In dieser Antwort von S. Mark finden Sie eine Möglichkeit, einen garantierten eindeutigen Satz von Zufallszahlen zu erhalten. Die Technik, auf die sich das Poster bezieht, verwendet eine Reihe von Zahlen (die Sie angeben, damit Sie sie eindeutig machen können) und mischt sie in eine zufällige Reihenfolge. Wenn Sie die Zahlen nacheinander aus dem gemischten Array ziehen, erhalten Sie eine Folge von Pseudozufallszahlen, die sich garantiert nicht wiederholen.

Fußnote: Kryptografisch sichere PRNGs

Der MT-Algorithmus ist nicht kryptografisch sicher, da es relativ einfach ist, den internen Zustand des Generators durch Beobachtung einer Folge von Zahlen abzuleiten. Andere Algorithmen wie Blum Blum Shub werden für kryptografische Anwendungen verwendet, sind jedoch möglicherweise für Simulations- oder allgemeine Zufallszahlenanwendungen ungeeignet. Kryptografisch sichere PRNGs können teuer sein (möglicherweise erfordern sie Bignumberechnungen) oder haben möglicherweise keine guten geometrischen Eigenschaften. Im Fall dieser Art von Algorithmus besteht die Hauptanforderung darin, dass es rechnerisch unmöglich sein sollte, den internen Zustand des Generators durch Beobachtung einer Folge von Werten abzuleiten.

ConcernedOfTunbridgeWells
quelle
Eine Korrektur: LCG-basierte PRNGs garantieren bei ordnungsgemäßer Verwendung keine eindeutige Ausgabe für den gesamten Zyklus. Zum Beispiel hat das traditionelle Turbo Pascal LCG (IIRC) 31 Bits internen Zustands, aber es erzeugt nur 15-Bit-Zahlen, die sich innerhalb eines einzelnen Zyklus wiederholen können und tun.
Porculus
46

Bevor Sie Python beschuldigen, sollten Sie einige Wahrscheinlichkeits- und Statistiktheorien auffrischen. Beginnen Sie mit dem Lesen über das Geburtstagsparadoxon

Das randomModul in Python verwendet übrigens den Mersenne-Twister PRNG, der als sehr gut gilt, eine enorme Zeit hat und ausgiebig getestet wurde. Seien Sie also versichert, dass Sie in guten Händen sind.

Eli Bendersky
quelle
42

Wenn Sie keine Wiederholung wünschen, generieren Sie ein sequentielles Array und verwenden Sie random.shuffle

SIE
quelle
3
Gott, ich liebe random.shuffle. Es ist einer der Kerne meines Projekts :)
PizzAzzra
39

Als Antwort auf die Antwort von Nimbuz:

http://xkcd.com/221/

Alt-Text

Quark
quelle
7
RFC 1149.5 gibt 4 als standardmäßige IEEE-geprüfte Zufallszahl an.
Zano
15

Wahre Zufälligkeit beinhaltet definitiv die Wiederholung von Werten, bevor der gesamte Satz möglicher Werte erschöpft ist. Andernfalls wäre es nicht zufällig, da Sie vorhersagen können, wie lange ein Wert nicht wiederholt wird.

Wenn Sie jemals gewürfelt haben, haben Sie sicherlich ziemlich oft 3 Sechser hintereinander ...

Ber
quelle
4

Das ist kein Repeater. Ein Repeater ist, wenn Sie dieselbe Sequenz wiederholen . Nicht nur eine Nummer.

Lennart Regebro
quelle
4

Sie generieren 4500Zufallszahlen aus einem Bereich 500 <= x <= 5000. Anschließend prüfen Sie für jede Nummer, ob sie zuvor generiert wurde. Das Geburtstagsproblem gibt an , wie wahrscheinlich es ist, dass zwei dieser Zahlen mit bestimmten nVersuchen außerhalb eines Bereichs übereinstimmen d.

Sie können die Formel auch invertieren, um zu berechnen, wie viele Zahlen Sie generieren müssen, bis die Wahrscheinlichkeit, ein Duplikat zu generieren, größer ist als 50%. In diesem Fall haben Sie die >50%Möglichkeit, nach 79Iterationen eine doppelte Nummer zu finden .

liwp
quelle
1

Sie haben einen zufälligen Bereich von 4501 Werten (500-5000) definiert und iterieren 4500 Mal. Grundsätzlich ist es garantiert, dass Sie in dem von Ihnen geschriebenen Test eine Kollision bekommen.

Anders denken:

  • Wenn das Ergebnisarray leer ist, ist P (dupe) = 0
  • 1 Wert in Array P (dupe) = 1/4500
  • 2 Werte in Array P (dupe) = 2/4500
  • etc.

Wenn Sie also 45/4500 erreichen, hat diese Einfügung eine 1% ige Chance, ein Duplikat zu sein, und diese Wahrscheinlichkeit steigt mit jeder nachfolgenden Einfügung weiter an.

Um einen Test zu erstellen, der die Fähigkeiten der Zufallsfunktion wirklich testet, vergrößern Sie das Universum möglicher Zufallswerte (z. B. 500-500000). Möglicherweise erhalten Sie einen Betrüger oder nicht. Im Durchschnitt erhalten Sie jedoch weitaus mehr Iterationen.

sfrench
quelle
3
Ihre Mathematik ist wegen des Geburtstagsproblems falsch. Siehe andere Antworten. Nach 45 Einfügungen haben Sie eine 1% ige Chance, die erste Einfügung wiederholt zu haben, aber Sie haben auch 44 andere unterschiedliche Einfügungen, die Sie möglicherweise wiederholt haben.
JCDyer
0

Für alle anderen mit diesem Problem habe ich uuid.uuid4 () verwendet und es funktioniert wie ein Zauber.

Orokusaki
quelle
3
Die Frage hätte dann besser formuliert werden können: "Ich möchte eine Reihe sich nicht wiederholender Zahlen generieren, Pythons randint () scheint das nicht zu tun - was macht das?" anstatt "Pythons Zufallszahlengenerator ist schlecht" :-) Angenommen, uuid4 () ist wirklich zufällig, kann es sich dennoch wiederholen - nur wirklich unwahrscheinlich. Was sind die tatsächlichen Eigenschaften, die Sie von den Zahlen wollen? Nicht wiederholend? Zufällig? (Wählen Sie eine aus.) Nicht oft wiederholen? (Verwenden Sie einen größeren int Bereich, effektiv alle uuid4 ist, wie es scheint.) Was genau wollen Sie die Zahlen verwenden , für die eigentliche Frage ist.
Agnoster
@agnoster Ich hatte wirklich nicht vor, Python zu beleidigen, aber zufällig: Mangelnde Vorhersagbarkeit ohne systematisches Muster und Wiederholungsmuster: Ein Muster einer Gruppe von Elementen, das sich immer wieder wiederholt. Sehen Sie, der Zufallsgenerator ist nicht zufällig, wenn er wiederholt wird, weil er dann ein Muster hat.
Orokusaki
9
Ihre Definition von "zufällig" ist falsch. Im Ernst, gehen Sie zurück und lesen Sie die Teile des Geburtstagsparadoxons erneut. Ein wirklich zufälliger Zahlengenerator wird immer noch viel häufiger Wiederholungen haben, als Sie es von der Intuition erwarten. Wie @ConcernedOfTunbridgeW hervorhebt, beträgt die Wahrscheinlichkeit einer Wiederholung im Bereich von 500 bis 5000 innerhalb der ersten 100 Zahlen ~ 66%, was meiner Meinung nach keineswegs unvereinbar mit dem ist, was Sie beobachtet haben. Zufälligkeit bedeutet nicht "ohne Wiederholungen", sondern nur ... nun, zufällig. Wenn Sie einen Mangel an Wiederholungen garantieren, muss der Generator weniger zufällig sein, um dies durchzusetzen.
Agnoster
1
Die Frage, wofür Sie diese Zahlen wollen, steht noch. Wenn Sie speziell nicht wiederholte Zahlen möchten, warum? uuid4 () unterscheidet sich (wenn es wirklich zufällig ist) nicht von randint () mit einem sehr sehr großen Bereich. Wenn Sie möchten, dass die Sequenz schwer zu erraten ist, tut es Ihnen tatsächlich weh, Wiederholungen zu eliminieren, denn sobald ich die Zahl 33 sehe, weiß ich, dass alles, was als nächstes kommt, keine 33 enthält. So Durchsetzung nicht-Wiederholung macht eigentlich Ihre Sequenz mehr berechenbar - sehen Sie?
Agnoster
0

Es gibt das Geburtstagsparadoxon. Wenn Sie dies berücksichtigen, stellen Sie fest, dass Sie sagen, dass das Finden von "764, 3875, 4290, 4378, 764" oder ähnlichem nicht sehr zufällig ist, da sich eine Zahl in dieser Sequenz wiederholt. Der wahre Weg, dies zu tun, besteht darin, Sequenzen miteinander zu vergleichen. Ich habe dazu ein Python-Skript geschrieben.

from random import randint
y = 21533456
uniques = []
for i in range(y):  
    x1 = str(randint(500, 5000))
    x2 = str(randint(500, 5000))
    x3 = str(randint(500, 5000))
    x4 = str(randint(500, 5000))
    x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
    raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
    raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)
Himbeer-Typ
quelle
Diese Antwort wurde vor Jahren gegeben (siehe ausgewählte Antwort oben). Es wird nicht das Geburtstagsparadoxon genannt, da es kein Paradoxon ist, sondern nur das Geburtstagsproblem.
Orokusaki