Frage

Ich habe dies die Zufälligkeit der randint 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 versucht, etwa 10-mal mehr und das beste Ergebnis, das ich bekam, waren 121 Iterationen vor einem Repeater. Ist dies die beste Art von Ergebnis, das Sie aus der Standardbibliothek bekommen?

War es hilfreich?

Lösung

Der Geburtstag Paradox, oder warum PRNGs Duplikate mehr produzieren oft als Sie vielleicht denken.


Es gibt ein paar Probleme im Spiel in dem Problem des OP. Eine davon ist die Geburtstagsparadox wie oben erwähnt, und das zweite ist die Natur dessen, was Sie erzeugenden sind, die garantiert nicht, von Natur aus, dass eine bestimmte Anzahl wird nicht wiederholt.

Der Geburtstag Paradox gilt, wenn gegebener Wert mehr als einmal in der Zeit des Generators auftreten kann - und deshalb können Duplikate innerhalb einer Stichprobe von Werten geschehen. Die Wirkung des Geburtstags-Paradoxon ist, dass die reale Wahrscheinlichkeit, solche Duplikate immer sehr bedeutend ist und die durchschnittliche Zeit zwischen ihnen kleiner ist als man sonst vielleicht gedacht haben. Diese Dissonanz zwischen den wahrgenommenen und tatsächlichen Wahrscheinlichkeiten macht den Geburtstag Paradox ein gutes Beispiel für eine kognitive Verzerrung , wo eine naive intuitive Schätzung wahrscheinlich sein wild falsch ist.

Eine schnelle Grundierung auf Pseudozufallszahlengeneratoren (PRNGs)

Der erste Teil des Problems ist, dass Sie den freigelegten Wert eines Zufallszahlengenerators nehmen und es auf eine viel kleinere Zahl konvertieren, so dass der Raum der möglicher Werte reduziert wird. Obwohl einige Pseudo-Zufallszahlengeneratoren diese Transformation während ihrer Periode nicht wiederholen Werte tun ändert die Domäne ein viel kleineres. Die kleinere Domain erlischt die ‚keine Wiederholungen‘ Zustand, so dass Sie eine erhebliche Wahrscheinlichkeit von Wiederholungen erwarten können.

Einige Algorithmen, wie der linearen Kongruenz PRNG (A'=AX|M) tun Garantie Einzigartigkeit für den gesamten Zeitraum. In einer LCG enthält der erzeugte Wert den gesamten Zustand des Akkumulators und kein zusätzlicher Zustand gehalten wird. Der Generator ist deterministisch und kann nicht eine Zahl innerhalb der Periode wiederholen, - jeder gegebene Akkumulatorwert nur einen möglichen Wert sukzessive implizieren kann. Daher kann jeder Wert nur einmal auftritt innerhalb der Periode des Generators. die Periode eines solchen PRNG ist jedoch relativ klein - etwa 2 ^ 30 für typische Implementierungen des LCG-Algorithmus -. und kann möglicherweise nicht größer sein als die Anzahl der unterschiedlichen Werte

Nicht alle PRNG Algorithmen teilen diese Eigenschaft; einige können einen bestimmten Wert innerhalb des Zeitraums wiederholen. In dem Problem des OP, der Mersenne-Twister-Algorithmus (verwendet in Python Zufall Modul) hat eine sehr lange Zeit - viel größer als 2 ^ 32. Im Gegensatz zu einer linearen Kongruenz PRNG, ist das Ergebnis nicht lediglich eine Funktion des vorherigen Ausgabewertes als der Akkumulator zusätzlichen Zustand enthält. Mit 32-Bit-Integer-Ausgang und einen Zeitraum von ~ 2 ^ 19937, kann es unmöglich bieten eine solche Garantie.

Die Mersenne Twister ist ein beliebter Algorithmus für PRNGs, weil es gute statistische und geometrische Eigenschaften und eine sehr lange Zeit hat - wünschenswerte Eigenschaften für einen PRNG auf Simulationsmodelle verwendet.

  • Good statistische Eigenschaften bedeuten, dass die Zahlen, die durch den Algorithmus erzeugt gleichmäßig verteilt sind mit keine Zahlen, die eine deutlich höhere Wahrscheinlichkeit, erscheinen als andere haben. Schlechte statistische Eigenschaften könnten in den Ergebnissen unerwünschte Skew erzeugen.

  • Good geometrisch properies bedeutet, dass Gruppen vonN Zahlen liegen nicht auf einer Hyperebene in N-dimensionalen Raum. Schlechte geometrische Eigenschaften können Scheinkorrelationen in einem Simulationsmodell erzeugen und verzerren die Ergebnisse.

  • Eine lange Zeit bedeutet, dass Sie eine Menge von Zahlen erzeugen können, bevor die Sequenz zu Beginn umschlingt. Wenn ein Modell eine große Anzahl von Iterationen benötigt oder nur aus mehreren Samen ausgeführt werden sollte, dann die 2 ^ 30 oder so diskreten Zahlen zur Verfügung aus einer typischen LCG Implementierung können nicht ausreichend sein. Der MT19337 Algorithmus hat einen sehr langen Zeitraum - 2 ^ 19337-1 oder etwa 10 ^ 5821. Im Vergleich dazu ist die Gesamtzahl der Atome im Universum auf etwa 10 ^ 80.

  • geschätzt

Die 32-Bit-Ganzzahl durch einen MT19337 PRNG erzeugt werden, können möglicherweise nicht genug, um diskrete Werte darstellen, zu vermeiden, während einer so großen Zeitraum wiederholt wird. In diesem Fall sind doppelte Werte wahrscheinlich und unvermeidlich mit einer ausreichend großen Probe auftreten.

Der Geburtstag Paradox auf den Punkt

Dieses Problem wird ursprünglich als die Wahrscheinlichkeit von zwei beliebigen Personen im Raum definiert den gleichen Geburtstag zu teilen. Der entscheidende Punkt ist, dass zwei beliebigen Menschen im Raum einen Geburtstag teilen. Menschen neigen dazu, zu naiv, das Problem als die Wahrscheinlichkeit von jemandem im Raum fehlinterpretieren einen Geburtstag mit einer bestimmten Person zu teilen, die die Quelle des kognitive Verzerrung , die oft bewirkt, dass Menschen, die Wahrscheinlichkeit zu unterschätzen. Dies ist die falsche Annahme - es gibt keine Voraussetzung für das Spiel auf eine bestimmte Person zu sein und alle zwei Personen passen könnten.

Diese Grafik zeigt die Wahrscheinlichkeit eines gemeinsamen Geburtstag wie die Zahl der Menschen im Raum steigt. Für 23 Personen ist die Wahrscheinlichkeit, dass zwei knapp über 50% einen Geburtstag zu teilen.“ title = „Diese Grafik zeigt die Wahrscheinlichkeit eines gemeinsamen Geburtstag als Zahl der Menschen im Raum steigt. Für 23 Personen ist die Wahrscheinlichkeit von zwei einen Geburtstag zu teilen ist etwas mehr als 50%.“ loading=

Die Wahrscheinlichkeit einer Übereinstimmung zwischen zwei beliebigen Individuen auftritt, ist viel höher als die Wahrscheinlichkeit einer Übereinstimmung mit einer bestimmten Person als das Spiel nicht zu einem bestimmten Datum sein muss. Vielmehr müssen Sie nur zwei Personen finden, die am gleichen Tag Geburtstag teilen. Aus diesem Diagramm (die auf der Wikipedia-Seite zu dem Thema gefunden werden können), können wir sehen, dass wir 23 Leute im Raum nur noch für eine 50% ige Chance zu sein, zwei zu finden, dass Spiel auf diese Weise.

Von dem Wikipedia-Eintrag zum Thema können wir ein  Paare (siehe das Problem zu verstehen), die möglicherweise (dh die erste passen könnte könnte mit Spiel die zweite, dritte usw., die zweite könnte die dritte, vierte usw. usw.) entsprechen, so dass die Anzahl von Kombinationen , die potenziell Spiel ist, könnte eher mehr als nur 100

Von Die Berechnung der Wahrscheinlichkeit wir einen Ausdruck von 1 - (4500 / (4500 ** 100 * (4500 - 100)) . Der folgende Ausschnitt aus Python nachfolgendem Code hat eine naive Bewertung der Wahrscheinlichkeit, daß ein zusammenpassendes Paar auftreten.

# === 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 erzeugt ein vernünftiges aussehendes Ergebnis von p = 0,669 für eine Übereinstimmung innerhalb von 100 Zahlen auftritt aus einer Population von 4500 möglichen Werten abgetastet. (Vielleicht hat jemand könnte dies zu überprüfen und einen Kommentar hinterlassen, wenn es falsch ist). Daraus können wir durch die OP die Längen von Läufen zwischen matching numbers beobachtet zu sein scheinen recht vernünftig.

sehen, dass

Fußnote: schlurfend mit einer einzigartigen Sequenz von Pseudozufallszahlen erhalten

finden Sie unter für ein Mittel, einen garantierten einzigartigen Satz von Zufallszahlen zu bekommen. Die Technik das Plakat bezieht sich auf nimmt eine Reihe von Zahlen (die Sie liefern, so dass Sie sie einzigartig machen können) und mischt sie in zufälliger Reihenfolge. Zeichnen Sie die Zahlen in der Reihenfolge von dem gemischten Array gibt Ihnen eine Folge von Pseudozufallszahlen, die nicht zu wiederholen garantiert werden.

Fußnote: Kryptographisch Sichere PRNGs

Der MT-Algorithmus ist nicht kryptografisch sicheres da es relativ einfach ist, den inneren Zustand zu schließen, des Generators durch eine Folge von Zahlen zu beobachten. Andere Algorithmen wie Blum Blum Shub für Verschlüsselungsanwendungen verwendet werden, sondern kann für die Simulation oder allgemein ungeeignet Zufallszahl-Anwendungen. Kryptographisch sichere PRNGs teuer sein kann (vielleicht erfordern bignum Berechnungen) oder nicht gute geometrische Eigenschaften haben können. In dem Fall dieser Art von Algorithmus ist die primäre Voraussetzung, daß es rechnerisch unmöglich sein sollte, durch Beobachten eine Folge von Werten, den internen Zustand des Generators zu schließen.

Andere Tipps

Vor Python Schuld, Sie sollten wirklich etwas Wahrscheinlichkeit & Statistik Theorie auffrischen. Starten Sie durch das Lesen über die Geburtstagsparadox

Durch die Art und Weise, die random Modul in Python verwendet den Mersenne-Twister PRNG, der als sehr gut, hat eine enorme Zeit und wurde ausgiebig getestet. So sicher sein, Sie in guten Händen sind.

Wenn Sie nicht repetative einen wollen, erzeugen sequenzielle Array und verwenden zufällig. Shuffle

Als Antwort auf die Antwort von Nimbuz:

http://xkcd.com/221/

alt text

True Zufälligkeit schließt definitiv Wiederholung von Werten, bevor die ganze Reihe von möglichen Werten erschöpft ist. Es wäre sonst nicht zufällig sein, wie Sie es sich ein Wert vorherzusagen, wäre in der Lage, für wie lange nicht wiederholt werden.

Wenn Sie jemals gewürfelt, du hast sicher 3 Sechser in Reihe ziemlich oft ...

Pythons Zufalls Implementierung ist eigentlich ganz Stand der Technik:

Das ist kein Repeater. Ein Repeater ist, wenn Sie die gleiche sequence wiederholen. Nicht nur eine Zahl.

Sie generieren 4500 Zufallszahl aus einem Bereich 500 <= x <= 5000. Sie überprüfen dann für jede Nummer, um zu sehen, ob es vor erzeugt wurde. Die Geburtstag Problem sagt uns, was die Wahrscheinlichkeit für zwei dieser Zahlen ist gegeben n übereinstimmen probiert ein Bereich d.

Sie können auch invertieren die Formel zu berechnen, wie viele Zahlen Sie haben zu erzeugen, bis die Chance, ein Duplikat zu erzeugen mehr als 50% ist. In diesem Fall haben Sie eine >50% Chance auf eine doppelte Anzahl nach 79 Iterationen zu finden.

Sie haben einen zufälligen Raum von 4501 Werten (500-5000) definiert sind, und Sie sind Iterieren 4500 mal. Sie sind im Grunde um eine Kollision erhalten im Test garantiert, dass Sie geschrieben hat.

Um darüber nachdenken, es eine andere Art und Weise:

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

So durch die Zeit, die du 45/4500 erhalten, dass Einsatz hat eine Chance von 1% ein Duplikat zu sein, und diese Wahrscheinlichkeit hält mit jedem weiteren Einsatz zu erhöhen.

einen Test zu erstellen, die wirklich die Fähigkeiten der Zufallsfunktion testet, erhöht das Universum möglichen Zufallswert (zB: 500-500000) können Sie oder können nicht eine Betrogene bekommen. Aber Sie werden weit mehr Iterationen im Durchschnitt erhalten.

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

Es ist der Geburtstag Paradox. Unter Berücksichtigung dieser Tatsache Sie erkennen, dass das zu finden, was Sie sagen, ist „764, 3875, 4290, 4378, 764“ oder so etwas nicht sehr zufällig ist, weil eine Reihe in dieser Reihenfolge wiederholt. Der wahre Weg, es zu tun ist, Sequenzen miteinander zu vergleichen. Ich schrieb dies ein Python-Skript zu tun.

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)
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top