Zufällig ist kaum zufällig?

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?

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.

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 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 . 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.

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.

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

Als Antwort auf die Antwort von Nimbuz:

http://xkcd.com/221/

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 ...

Die zufällige Implementierung von Python ist tatsächlich auf dem neuesten Stand der Technik:

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

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

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 .

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.

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

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)