„Zufälligkeit“ verstehen

829

Ich kann mich nicht darum kümmern, was ist zufälliger?

rand()

ODER :

rand() * rand()

Ich finde es ein echter Rätsel, kannst du mir helfen?


BEARBEITEN:

Intuitiv weiß ich, dass die mathematische Antwort sein wird, dass sie gleich zufällig sind, aber ich kann nicht anders, als zu denken, dass Sie, wenn Sie den Zufallszahlenalgorithmus zweimal ausführen, wenn Sie die beiden miteinander multiplizieren, etwas Zufälligeres schaffen als nur zu tun es einmal.

Trufa
quelle
162
Was meinst du mit "zufälliger"?
dan04
55
Wie andere angegeben haben, haben diese beiden Größen nicht die gleiche Verteilung. Unter mathworld.wolfram.com/UniformProductDistribution.html finden Sie die Verteilung, die Sie tatsächlich erhalten. Vergleichen Sie dies mit einer einzelnen einheitlichen Zufallszahl, bei der alle Werte im Intervall gleich wahrscheinlich sind, sodass die Wahrscheinlichkeitsdichtefunktion eine horizontale gerade Linie ist.
Bnaul
44
Ich empfehle das Lesen Zufalls Dummheits auf der Daily WTF . Lesen Sie besonders diesen Kommentar , in dem sie die Ausgabe dieser neuen Zufallszahl analysieren. Die daraus zu entfernende Botschaft lautet: Beliebige Operationen mit Zufallszahlen führen nicht unbedingt zu einer zufälligen Ausgabe .
Detly
51
Außerdem: Intuitiv weiß ich, dass die mathematische Antwort sein wird, dass sie gleichermaßen zufällig sind - wenn Sie nur durch Intuition
rechnen
92
Bringen

Antworten:

1481

Nur eine Klarstellung

Obwohl die vorherigen Antworten immer dann richtig sind, wenn Sie versuchen, die Zufälligkeit einer Pseudozufallsvariablen oder ihre Multiplikation zu erkennen, sollten Sie sich bewusst sein, dass Random () normalerweise gleichmäßig verteilt ist, Random () * Random () jedoch nicht.

Beispiel

Dies ist eine Stichprobe mit gleichmäßiger Zufallsverteilung, die durch eine Pseudozufallsvariable simuliert wird:

Histogramm des Zufalls ()

        BarChart[BinCounts[RandomReal[{0, 1}, 50000], 0.01]]

Dies ist zwar die Verteilung, die Sie nach Multiplikation zweier Zufallsvariablen erhalten:

Histogramm von Random () * Random ()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] * 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Beide sind also „zufällig“, aber ihre Verteilung ist sehr unterschiedlich.

Ein anderes Beispiel

Während 2 * Random () gleichmäßig verteilt ist:

Histogramm von 2 * Random ()

        BarChart[BinCounts[2 * RandomReal[{0, 1}, 50000], 0.01]]

Random () + Random () ist nicht!

Histogramm von Random () + Random ()

        BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + 
                                 RandomReal[{0, 1}, 50000], {50000}], 0.01]]

Der zentrale Grenzwertsatz

Der zentrale Grenzwertsatz besagt, dass die Summe von Random () mit zunehmenden Begriffen zu einer Normalverteilung tendiert .

Mit nur vier Begriffen erhalten Sie:

Histogramm von Random () + Random () + Random () + Random ()

BarChart[BinCounts[Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000] +
                   Table[RandomReal[{0, 1}, 50000] + RandomReal[{0, 1}, 50000],
                   {50000}],
         0.01]]  

Und hier können Sie den Weg von einer einheitlichen zu einer normalen Verteilung sehen, indem Sie 1, 2, 4, 6, 10 und 20 gleichmäßig verteilte Zufallsvariablen addieren:

Histogramm einer unterschiedlichen Anzahl von hinzugefügten Zufallsvariablen

Bearbeiten

Ein paar Credits

Vielen Dank an Thomas Ahle für den Hinweis in den Kommentaren, dass die in den letzten beiden Bildern gezeigten Wahrscheinlichkeitsverteilungen als Irwin-Hall-Verteilung bekannt sind

Vielen Dank an Heike für ihre wundervolle zerrissene [] Funktion

Dr. Belisarius
quelle
41
+1. Da das OP wahrscheinlich eine gleichmäßige Verteilung wünschte, sollte dies die akzeptierte Antwort sein. Und wenn Sie dies tun würden rand()+rand(), würden Sie eine Verteilung vom Typ "2W6" mit einem Fettzentrum erhalten.
Thilo
8
Das ist sehr interessant, aber es bringt mich innerlich um, wie anti-intuitiv das ist. Ich werde genauer darauf eingehen, nachdem ich etwas mehr über den Vertrieb gelesen habe. Vielen Dank!
Trufa
46
@Trufa: Vielleicht hilft das bei einem Teil der Intuition, zumindest für Summen. Stellen Sie sich vor, Sie nehmen den "Durchschnitt" eines gewürfelten Würfels. Stellen Sie sich nun vor, Sie nehmen durchschnittlich zwei Würfel. Jetzt hundert. Was passiert mit der Chance, im Durchschnitt eine Eins oder Sechs zu bekommen, wenn Sie mehr Würfel hinzufügen?
Johncip
3
@matt b Die Diagramme sind Einzeiler in Mathematica. Der Code ist der fett gedruckte Text vor jedem Diagramm. Mathematica ist eine großartige Sprache für Plots!
Dr. Belisarius
4
@thenonhacker: Ja, die Histogramme zeigen zwar Voreingenommenheit, aber keine Nicht-Zufälligkeit. Voreingenommene Zufallszahlen sind nicht weniger zufällig. Die richtige Antwort auf die ursprüngliche Frage des Benutzers lautet: "Versuchen Sie nicht, klug zu sein, Sie werden die Dinge nur noch schlimmer machen", und diese Antwort vermittelt diesen Punkt.
Kennet Belenky
151

Ich denke, beide Methoden sind so zufällig, obwohl mein Bauchgefühl sagen würde, dass dies rand() * rand()weniger zufällig ist, weil es mehr Nullen setzen würde. Sobald einer rand()ist 0, wird die Summe0

Janco
quelle
18
Meine Antwort auf alle Antworten mit diesem Streifen lautet: Ich mag Humor, aber es muss CW sein!
Andreas Rejbrand
4
@Andomar: Nein, das ist es nicht. Ganz und gar nicht. Wissen Sie, was CW ist?
Andreas Rejbrand
17
@Andreas Rejbrand: CW ist eine Waffe, die interessante Fragen beantwortet, indem sie denjenigen, die sie beantworten, den Ruf verweigert. Sieht so aus, als hätte es meta.stackexchange.com/questions/392/… nerfed (weshalb vielleicht diese interessante Frage auftaucht!)
Andomar
11
@Andomar - Ja, CW wirft interessante Fragen auf, aber (aus den FAQ ) "Reputation ist ein grobes Maß dafür, wie sehr die Community Ihnen vertraut." Wenn Sie ein lustiges, urheberrechtlich geschütztes Bild in Ihre Antwort aufnehmen, denke ich, dass Ihre Antwort cool ist, und ich denke wahrscheinlich, dass Sie auch cool sind, aber es macht Sie nicht vertrauenswürdiger - daher im Idealfall kein Vertreter sollte vergeben werden. Ob das CW bedeutet oder ob man nicht abstimmen sollte, ist eine andere Frage.
Richard JP Le Guen
13
Der Troll "Zufallsgenerator" im Cartoon könnte nur ein Gelehrter sein, der π rezitiert und gerade den Feynman-Punkt erreicht . Übrigens, sind π Ziffern zufällig? :)
Mykhal
82

Weder ist "zufälliger".

rand()generiert einen vorhersagbaren Satz von Zahlen basierend auf einem pseudozufälligen Startwert (normalerweise basierend auf der aktuellen Zeit, die sich ständig ändert). Das Multiplizieren von zwei aufeinanderfolgenden Zahlen in der Folge erzeugt eine andere, aber gleichermaßen vorhersagbare Folge von Zahlen.

Wenn es darum geht, Kollisionen zu reduzieren, lautet die Antwort nein. Es erhöht tatsächlich die Kollisionen aufgrund des Effekts der Multiplikation von zwei Zahlen, wobei 0 < n < 1. Das Ergebnis ist ein kleinerer Bruchteil, der eine Verzerrung des Ergebnisses zum unteren Ende des Spektrums verursacht.

Einige weitere Erklärungen. Im Folgenden beziehen sich "unvorhersehbar" und "zufällig" auf die Fähigkeit einer Person, zu erraten, wie die nächste Zahl auf vorherigen Zahlen basieren wird, d. H. ein Orakel.

Gegebener xStartwert, der die folgende Werteliste generiert:

0.3, 0.6, 0.2, 0.4, 0.8, 0.1, 0.7, 0.3, ...

rand() generiert die obige Liste und rand() * rand() generiert:

0.18, 0.08, 0.08, 0.21, ...

Beide Methoden erzeugen immer die gleiche Liste von Zahlen für den gleichen Samen und sind daher für ein Orakel gleichermaßen vorhersehbar. Wenn Sie sich jedoch die Ergebnisse für die Multiplikation der beiden Aufrufe ansehen, werden Sie feststellen, dass sie 0.3trotz einer anständigen Verteilung in der ursprünglichen Sequenz alle darunter liegen . Die Zahlen sind aufgrund des Effekts der Multiplikation zweier Brüche voreingenommen. Die resultierende Anzahl ist immer kleiner und daher viel wahrscheinlicher eine Kollision, obwohl sie immer noch genauso unvorhersehbar ist.

Matthew Scharley
quelle
9
+1 Beachten Sie, dass andererseits rand()+rand()+rand()...zunehmend "weniger zufällig" wird (wenn Sie zufällig gleichmäßig verteilt meinen).
Thilo
4
@Thilo Nein, tut es nicht ...? Wenn eine Zufallsvariable im Bereich (0,1) gleichmäßig verteilt ist und Sie die Variable n-mal abtasten und die Summe nehmen, wird sie nur im Bereich (0, n) gleichmäßig verteilt.
user359996
5
@Trufa vertraue einfach darauf rand(), tatsächlich zufällig zu sein, und versuche nicht, die Zufälligkeit zu verbessern. Setzen Sie den Samen nicht mehrmals. Jeder einzelne Samen ist vollkommen in Ordnung, solange er selbst halb zufällig ist. Viele Implementierungen, die ich gesehen habe, verwenden die UNIX-Epoche als Ausgangsbasis, die sich jede Sekunde ändert und bei jeder Änderung einzigartig ist.
Matthew Scharley
61
@ user359996 rand () + rand () ist nicht gleichmäßig verteilt. Fügen Sie zwei Würfel hinzu, Sie erhalten eher 7 als 2.
Liam
4
@thenonhacker Siehe meine Definition von Zufälligkeit in meinem Beitrag. Nur weil Werte zu einem Ende des Spektrums tendieren, erhöht dies nicht die Vorhersagbarkeit der exakten erzeugten Werte, worauf ich mich bezog, als ich das Wort zufällig verwendete. Ich ging dann weiter auf das Problem der Voreingenommenheit ein.
Matthew Scharley
80

Übervereinfachung zur Veranschaulichung eines Punktes.

Angenommen, Ihre Zufallsfunktion gibt nur 0oder aus 1.

random()ist einer von (0,1), ist aber random()*random()einer von(0,0,0,1)

Sie können deutlich sehen, dass die Chancen, 0im zweiten Fall eine zu bekommen, in keiner Weise denen entsprechen, die eine bekommen 1.


Als ich diese Antwort zum ersten Mal veröffentlichte, wollte ich sie so kurz wie möglich halten, damit eine Person, die sie liest, auf einen Blick den Unterschied zwischen random()und versteht random()*random(), aber ich kann mich nicht davon abhalten, die ursprüngliche Ad-Litteram-Frage zu beantworten:

Welches ist zufälliger?

Unter diesen Umständen sind random(), random()*random(), random()+random(), (random()+1)/2oder jede andere Kombination , die zu einem festen Ergebnis nicht die gleiche Quelle der Entropie führen (oder den gleichen Ausgangszustand im Fall von Pseudo - Zufalls - Generatoren), die Antwort wäre, dass sie ebenso zufällig (Der Unterschied ist in ihrer Verteilung). Ein perfektes Beispiel, das wir uns ansehen können, ist das Craps-Spiel. Die Zahl, die Sie erhalten, wäre random(1,6)+random(1,6)und wir alle wissen, dass das Erhalten von 7 die höchste Chance hat, aber das bedeutet nicht, dass das Ergebnis des Würfelns von zwei mehr oder weniger zufällig ist als das Ergebnis des Würfelns eines Würfels.

Alin Purcaru
quelle
+1 für die Verdichtung von etwas teuflisch Kniffligem zu "gleich zufällig über verschiedene Verteilungen". Sehr elegant.
Jens Roland
3
Technisch gesehen ist (random () * 0 + 9) gleichermaßen zufällig, da es zufällig einen Wert aus der 1-Element-Menge zurückgibt: [9]. Der Dilbert-Cartoon hatte recht.
Jens Roland
2
@Jens Rolan "jede andere Kombination, die nicht zu einem festen Ergebnis führt";). 999999 <i> wahrscheinlich </ i> wird nicht zufällig generiert und die Wahrscheinlichkeit, dass es zufällig generiert wurde, kann berechnet werden.
Alin Purcaru
69

Hier ist eine einfache Antwort. Betrachten Sie Monopol. Sie würfeln zwei sechsseitige Würfel (oder 2W6 für diejenigen unter Ihnen, die die Spielnotation bevorzugen) und nehmen ihre Summe. Das häufigste Ergebnis ist 7, da es 6 Möglichkeiten gibt, eine 7 zu würfeln (1,6 2,5 3,4 4,3 5,2 und 6,1). Während eine 2 nur auf 1,1 gewürfelt werden kann. Es ist leicht zu erkennen, dass das Würfeln von 2W6 anders ist als das Würfeln von 1W12, auch wenn die Reichweite gleich ist (wenn man ignoriert, dass man auf 1W12 eine 1 erhalten kann, bleibt der Punkt derselbe). Wenn Sie Ihre Ergebnisse multiplizieren, anstatt sie hinzuzufügen, werden sie auf ähnliche Weise verzerrt, wobei die meisten Ihrer Ergebnisse in der Mitte des Bereichs liegen. Wenn Sie versuchen, Ausreißer zu reduzieren, ist dies eine gute Methode, die jedoch keine gleichmäßige Verteilung ermöglicht.

(Und seltsamerweise erhöht es auch die Anzahl der niedrigen Würfe. Angenommen, Ihre Zufälligkeit beginnt bei 0, dann sehen Sie eine Spitze bei 0, da dadurch, was auch immer der andere Wurf ist, eine 0 wird. Betrachten Sie zwei Zufallszahlen zwischen 0 und 1 (einschließlich) ) und multiplizieren. Wenn eines der Ergebnisse eine 0 ist, wird das Ganze zu einer 0, unabhängig vom anderen Ergebnis. Die einzige Möglichkeit, eine 1 daraus zu ziehen, besteht darin, dass beide Würfe eine 1 sind. In der Praxis wäre dies wahrscheinlich nicht wichtig aber es ergibt einen seltsamen Graphen.)

Valadil
quelle
4
"Wenn Sie Ihre Ergebnisse multiplizieren, anstatt sie hinzuzufügen, werden sie auf ähnliche Weise verzerrt, wobei die meisten Ihrer Ergebnisse in der Mitte des Bereichs liegen." - Überprüfen Sie diese Behauptung anhand des zweiten Diagramms in der Antwort von Belisarius.
Daniel Earwicker
52

Die obligatorische xkcd ...
return 4;  // durch fairen Würfelwurf ausgewählt, garantiert zufällig.

Krone
quelle
7
danmn dies erscheint immer dann, wenn das Wort "zufällig erscheint" :) Ich habe darauf gewartet !!
Trufa
9
Ich mag Humor, aber es muss CW sein.
Andreas Rejbrand
2
@Andreas Rejbrand - warum sollte diese "Humor" -Antwort CW sein?
Warren
16
Wenn es nicht CW ist, wird der Ruf jedes Mal, wenn es hochgestimmt wird, als Poster der Antwort gewürdigt (bisher 160 Wiederholungen). Jetzt ist der Ruf wie eine Schulnote - er sollte ein Zertifikat für technische (in diesem Fall Programmier-) Kenntnisse sein. Daher sollte man nicht in der Lage sein, sich einen Ruf zu verschaffen, indem man etwas veröffentlicht, das leicht zu bewerten ist, aber keine solche Fachkenntnis benötigt. Darüber hinaus bestimmt der Reputationswert auch die Berechtigungen des Benutzers. Bei einer Punktzahl von 10 000 erhält der Benutzer beispielsweise Zugriff auf Moderationstools bei StackOverflow.
Andreas Rejbrand
35

Es könnte hilfreich sein, dies in diskreteren Zahlen zu betrachten. Überlegen Sie, ob Sie Zufallszahlen zwischen 1 und 36 generieren möchten, damit Sie entscheiden, dass der einfachste Weg darin besteht, zwei faire, 6-seitige Würfel zu werfen. Du bekommst das:

     1    2    3    4    5    6
  -----------------------------
1|   1    2    3    4    5    6
2|   2    4    6    8   10   12
3|   3    6    9   12   15   18
4|   4    8   12   16   20   24   
5|   5   10   15   20   25   30
6|   6   12   18   24   30   36

Wir haben also 36 Zahlen, aber nicht alle sind fair vertreten, und einige kommen überhaupt nicht vor. Zahlen in der Nähe der mittleren Diagonale (linke untere Ecke bis obere rechte Ecke) treten mit der höchsten Häufigkeit auf.

Die gleichen Prinzipien, die die ungerechte Verteilung zwischen Würfeln beschreiben, gelten auch für Gleitkommazahlen zwischen 0,0 und 1,0.

Julia
quelle
3
+1, um die Änderung der Verteilung beim Multiplizieren der Zufallszahlen konkreter darzustellen. Die Matrix half mehr als nur die Wörter oder sogar ein Verteilungsdiagramm.
Marjan Venema
26

Einige Dinge über "Zufälligkeit" sind nicht intuitiv.

Unter der Annahme einer flachen Verteilung von rand()erhalten Sie Folgendes, um eine nicht flache Verteilung zu erhalten:

  • hohe Voreingenommenheit: sqrt(rand(range^2))
  • Bias Peaking in der Mitte: (rand(range) + rand(range))/2
  • niedrig: Voreingenommenheit: range - sqrt(rand(range^2))

Es gibt viele andere Möglichkeiten, um bestimmte Vorspannungskurven zu erstellen. Ich habe einen kurzen Test durchgeführt rand() * rand()und Sie erhalten eine sehr nichtlineare Verteilung.

staticsan
quelle
24

Die meisten rand () - Implementierungen haben einen gewissen Zeitraum. Dh nach einer enormen Anzahl von Aufrufen wiederholt sich die Sequenz. Die Reihenfolge der Ausgänge vonrand() * rand() Wiederholungen in der Hälfte der Zeit, so ist es in diesem Sinne "weniger zufällig".

Ohne sorgfältige Konstruktion führt das Durchführen von Arithmetik für zufällige Werte tendenziell zu weniger Zufälligkeit. Ein oben genanntes Poster mit dem Vermerk " rand()+ rand()+ rand()..." (z. B. k-mal), das tatsächlich zum k-fachen des Mittelwerts des Wertebereichs tendiertrand() zurück. (Es ist ein zufälliger Spaziergang mit Schritten, die symmetrisch zu diesem Mittelwert sind.)

Nehmen Sie der Vollständigkeit halber an, dass Ihre rand () -Funktion eine gleichmäßig verteilte reelle Zufallszahl im Bereich [0,1] zurückgibt. (Ja, dieses Beispiel ermöglicht eine unendliche Genauigkeit. Dies ändert nichts am Ergebnis.) Sie haben keine bestimmte Sprache ausgewählt und verschiedene Sprachen können unterschiedliche Aktionen ausführen. Die folgende Analyse gilt jedoch für Änderungen für jede nicht perverse Implementierung von rand ( ). Das Produkt rand() * rand()liegt ebenfalls im Bereich [0,1], ist aber nicht mehr gleichmäßig verteilt. Tatsächlich liegt das Produkt wahrscheinlich genauso im Intervall [0,1 / 4) wie im Intervall [1 / 4,1). Eine stärkere Multiplikation führt dazu, dass das Ergebnis noch weiter in Richtung Null verschoben wird. Dies macht das Ergebnis vorhersehbarer. In breiten Strichen vorhersehbarer == weniger zufällig.

Nahezu jede Folge von Operationen mit gleichmäßig zufälligen Eingaben ist ungleich zufällig, was zu einer erhöhten Vorhersagbarkeit führt. Mit Vorsicht kann man diese Eigenschaft überwinden, aber dann wäre es einfacher gewesen, eine gleichmäßig verteilte Zufallszahl in dem Bereich zu generieren, den Sie tatsächlich wollten, als Zeit mit Arithmetik zu verschwenden.

Eric Towers
quelle
Ich hatte auch den Gedanken, dass es die Zufallsgeneratorperiode doppelt so schnell durchlaufen würde.
Jared Updike
3
Die Sequenzlänge wird nur halbiert, wenn sie gerade ist. Wenn es ungerade ist, erhalten Sie r1 * r2, r3 * r4, ..., rn * r1, r2 * r3, r4 * r5 und die Gesamtlänge ist gleich.
Jander
23

"zufällig" vs. "zufälliger" ist ein bisschen wie die Frage, welche Null mehr null ist.

In diesem Fall randhandelt es sich um ein PRNG, also nicht völlig zufällig. (in der Tat ziemlich vorhersehbar, wenn der Samen bekannt ist). Das Multiplizieren mit einem anderen Wert macht es nicht mehr oder weniger zufällig.

Ein echtes RNG vom Krypto-Typ ist tatsächlich zufällig. Und das Ausführen von Werten durch irgendeine Art von Funktion kann keine weitere Entropie hinzufügen und kann sehr wahrscheinlich Entropie entfernen, wodurch sie nicht mehr zufällig wird.

abelenky
quelle
3
Beachten Sie, dass dies kein Quadrat ist, da jeder Aufruf mit einem anderen Wert zurückgibt. Alles andere ist jedoch korrekt.
Matthew Scharley
2
@thenonhacker: Nach Ihrer eigenen Beschreibung ist die Sequenz "1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10 , 1,2,3,4,5,6,7,8,9,10 ... "ist zufällig. Es ist gleichmäßig verteilt, wobei alle Zahlen eine faire Chance bekommen. Es gibt keine Spitzen oder Vorspannungen. Betrachten Sie diese Sequenz wirklich als zufällig ??? Sie müssen Ihre Definition ändern. Bei Random geht es nicht um die Ausgabe, bei Random geht es um den Prozess , mit dem die Ausgabe erstellt wird.
Abelenky
2
@CurtainDog: Durch die Textkomprimierung wird der Entropiepegel gleich gehalten, während die Anzahl der Bits verringert wird, die erforderlich sind, um den gleichen Entropiebetrag auszudrücken.
Kennet Belenky
4
@thenonhacker, @abelenky: Auch Distributionen sind einfach. Was bei einem Zufallszahlengenerator zählt, ist die Anzahl der Bits im Zustand des Zufallszahlengenerators. Ein Zufallszahlengenerator mit Nullzustand (z. B. 4, 4, 4, 4, 4, ...) ist vollständig vorhersehbar. Ein One-Time-Pad hat so viel Status wie die Anzahl der erzeugten Werte, so dass eine Vorhersage unmöglich ist. Eine Faltung von zwei PNRGs erzeugt ein PNRG mit so vielen Entropiebits, wie sie beide enthalten, abzüglich ihrer Kovarianz.
Kennet Belenky
1
@Kennet - Danke, du hast das für mich sehr geklärt. @abelenky - cool, ich verstehe dich jetzt.
CurtainDog
20

Das Konzept, nach dem Sie suchen, ist "Entropie", der "Grad" der Störung einer Folge von Bits. Die Idee ist im Hinblick auf das Konzept der "maximalen Entropie" am einfachsten zu verstehen.

Eine ungefähre Definition einer Bitfolge mit maximaler Entropie besteht darin, dass sie nicht exakt in Form einer kürzeren Bitfolge ausgedrückt werden kann (dh unter Verwendung eines Algorithmus, um die kleinere Zeichenfolge wieder auf die ursprüngliche Zeichenfolge zu erweitern).

Die Relevanz der maximalen Entropie für die Zufälligkeit ergibt sich aus der Tatsache, dass Sie, wenn Sie eine Zahl "zufällig" auswählen, mit ziemlicher Sicherheit eine Zahl auswählen, deren Bitfolge nahe an der maximalen Entropie liegt, dh nicht komprimiert werden kann. Dies ist unser bestes Verständnis dessen, was eine "Zufallszahl" auszeichnet.

Wenn Sie also aus zwei Zufallsstichproben eine Zufallszahl machen möchten, die "doppelt" so zufällig ist, würden Sie die beiden Bitfolgen miteinander verketten . Praktisch würden Sie die Samples einfach in die hohe und niedrige Hälfte eines Wortes mit doppelter Länge füllen.

Praktischer gesagt, wenn Sie sich mit einem beschissenen Rand () satteln, kann es manchmal hilfreich sein, ein paar Samples zusammen zu xorieren - obwohl selbst dieses Verfahren nicht hilft, wenn es wirklich kaputt ist.

Dickhäuterpuncher
quelle
2
Ich hatte noch nie über Zufallsgenerationen über xor nachgedacht, aber ich denke, Sie können das Konzept ziemlich weit bringen ( en.wikipedia.org/wiki/Mersenne_twister )! Danke für die Antwort.
Gabriel Mitchell
1
Ich kämpfe wirklich darum, diese Antwort zu finden ... Wird die maximale Entropie nicht durch die Antworten in stackoverflow.com/questions/3956478/understanding-randomness/… und stackoverflow.com/questions/3956478/understanding-randomness/… besiegt ? . In diesen Fällen kann die ausgewählte Nummer nicht komprimiert werden, aber es fällt Ihnen schwer, sie zufällig zu nennen.
CurtainDog
1
+1 Schön wie die akzeptierte Antwort lautet, das ist mein Favorit. Denken Sie bei Computern immer in Teilen - viel weniger verwirrend und relevanter als der Versuch, real zu denken. (Ich habe meine Antwort geschrieben und dann diese bemerkt, also ist meine nichts weiter als eine Erweiterung dieser - vielleicht mit etwas Entropie).
Daniel Earwicker
1
Die Zufallszahl 4oder Binärzahl von @CurtainDog xkcd 0100kann auf Null Bit komprimiert werden. Das Dekomprimierungsprogramm würde einfach '4' zurückgeben. Es wird nicht weniger zufällig. Das Problem mit Dilbert ist, dass wir nicht wissen, ob wir es auf Null Bits komprimieren können (Dekomprimieren, indem wir immer 'Neun' zurückgeben). Es könnte auch acht zurückgeben, dann könnten wir auf 1 Bit komprimieren. Dekomprimieren um: 0-> neun, 1-> acht. Wir hätten 1 zufälliges Bit.
Ishtar
14

Die akzeptierte Antwort ist sehr schön, aber es gibt noch eine andere Möglichkeit, Ihre Frage zu beantworten. Die Antwort von PachydermPuncher verwendet bereits diesen alternativen Ansatz, und ich werde ihn nur ein wenig erweitern.

Der einfachste Weg, über Informationstheorie nachzudenken, ist die kleinste Informationseinheit, ein einzelnes Bit.

Gibt in der C-Standardbibliothek rand()eine Ganzzahl im Bereich von 0 bis zurückRAND_MAX , eine Grenze, die je nach Plattform unterschiedlich definiert werden kann. Angenommen, es wird RAND_MAXzufällig definiert, 2^n - 1wo neine Ganzzahl ist (dies ist in der Microsoft-Implementierung der Fall, wo n15 ist). Dann würden wir sagen, dass eine gute Implementierung nInformationen zurückgeben würde.

Stellen Sie sich vor, Sie rand()konstruieren Zufallszahlen, indem Sie eine Münze werfen, um den Wert eines Bits zu ermitteln, und dann wiederholen, bis sie einen Stapel von 15 Bits enthält. Dann sind die Bits unabhängig (der Wert eines Bits beeinflusst nicht die Wahrscheinlichkeit, dass andere Bits in demselben Stapel einen bestimmten Wert haben). Jedes Bit, das unabhängig betrachtet wird, ist also wie eine Zufallszahl zwischen 0 und einschließlich 1 und ist über diesen Bereich "gleichmäßig verteilt" (wahrscheinlich 0 bis 1).

Die Unabhängigkeit der Bits stellt sicher, dass die durch Bitstapel dargestellten Zahlen auch gleichmäßig über ihren Bereich verteilt werden. Dies ist intuitiv offensichtlich: Wenn 15 Bits vorhanden sind, ist der zulässige Bereich Null bis2^15 - 1 = 32767. Jede Zahl in diesem Bereich ist ein eindeutiges Bitmuster, z.

010110101110010

und wenn die Bits unabhängig sind, ist es wahrscheinlicher, dass kein Muster auftritt als irgendein anderes Muster. Alle möglichen Zahlen im Bereich sind also gleich wahrscheinlich. Und so ist das Gegenteil der Fall: Wenn rand()gleichmäßig verteilte ganze Zahlen erzeugt werden, bestehen diese Zahlen aus unabhängigen Bits.

Also denk dran rand() eine Produktionslinie für die Herstellung von Bits vor, die diese zufällig in Chargen beliebiger Größe liefert. Wenn Ihnen die Größe nicht gefällt, teilen Sie die Stapel in einzelne Bits auf und setzen Sie sie dann in beliebigen Mengen wieder zusammen (wenn Sie jedoch einen bestimmten Bereich benötigen, der keine Zweierpotenz ist, müssen Sie Ihre Zahlen verkleinern und bei weitem der einfachste Weg, dies zu tun, ist die Konvertierung in Gleitkomma).

Kehren Sie zu Ihrem ursprünglichen Vorschlag zurück, nehmen Sie an, Sie möchten von 15er-Chargen zu 30er-Chargen rand()wechseln , nach der ersten Zahl fragen , sie um 15 Stellen bitverschieben und dann eine weitere hinzufügen rand(). Auf diese Weise können zwei Anrufe kombiniert werden, rand()ohne eine gleichmäßige Verteilung zu stören. Dies funktioniert einfach, weil es keine Überlappung zwischen den Stellen gibt, an denen Sie die Informationsbits platzieren.

Dies unterscheidet sich stark vom "Strecken" des Bereichs von rand() durch Multiplizieren mit einer Konstanten. Wenn Sie beispielsweise die Reichweite verdoppeln möchten, können rand()Sie diese mit zwei multiplizieren - aber jetzt erhalten Sie immer nur gerade und niemals ungerade Zahlen! Das ist nicht gerade eine reibungslose Verteilung und kann je nach Anwendung ein ernstes Problem sein, z. B. ein Roulette-ähnliches Spiel, das angeblich ungerade / gerade Wetten zulässt. (Wenn Sie in Bits denken, vermeiden Sie diesen Fehler intuitiv, da Sie erkennen, dass das Multiplizieren mit zwei gleichbedeutend ist mit dem Verschieben der Bits nach links (größere Bedeutung) um eine Stelle und dem Ausfüllen der Lücke mit Null. Die Menge an Informationen ist also offensichtlich die gleiche - sie haben sich nur ein wenig bewegt.)

Solche Lücken in Zahlenbereichen können in Gleitkommazahlenanwendungen nicht berücksichtigt werden, da Gleitkommabereiche von Natur aus Lücken aufweisen, die einfach überhaupt nicht dargestellt werden können: In der Lücke zwischen jeweils zwei darstellbaren Gleitkommazahlen gibt es unendlich viele fehlende reelle Zahlen Punktnummern! Wir müssen also sowieso nur lernen, mit Lücken zu leben.

Wie andere gewarnt haben, ist Intuition in diesem Bereich riskant, insbesondere weil Mathematiker dem Reiz reeller Zahlen nicht widerstehen können, die schrecklich verwirrende Dinge voller knorriger Unendlichkeiten und offensichtlicher Paradoxien sind.

Aber zumindest, wenn Sie denken, dass es sich um Kleinigkeiten handelt, könnte Ihre Intuition Sie ein wenig weiter bringen. Bits sind wirklich einfach - sogar Computer können sie verstehen.

Daniel Earwicker
quelle
3
+1: Tatsächlich fehlen mehr Zahlen zwischen zwei IEEE-Floats mit doppelter Genauigkeit als Zahlen in der gesamten (mathematischen) Ganzzahl.
Donal Fellows
13

Wie andere gesagt haben, lautet die einfache kurze Antwort: Nein, es ist nicht zufälliger, aber es ändert die Verteilung.

Angenommen, Sie haben ein Würfelspiel gespielt. Sie haben einige völlig faire, zufällige Würfel. Wären die Würfelwürfe "zufälliger", wenn Sie vor jedem Würfelwurf zuerst zwei Würfel in eine Schüssel geben, sie herumschütteln, einen der Würfel zufällig auswählen und dann diesen würfeln? Klar würde es keinen Unterschied machen. Wenn beide Würfel Zufallszahlen ergeben, macht die zufällige Auswahl eines der beiden Würfel keinen Unterschied. In beiden Fällen erhalten Sie eine Zufallszahl zwischen 1 und 6 mit gleichmäßiger Verteilung auf eine ausreichende Anzahl von Rollen.

Ich nehme an, im wirklichen Leben könnte ein solches Verfahren nützlich sein, wenn Sie den Verdacht haben, dass die Würfel NICHT fair sind. Wenn zum Beispiel die Würfel leicht unausgeglichen sind, so dass einer dazu neigt, 1 häufiger als 1/6 der Zeit zu geben, und ein anderer dazu neigt, ungewöhnlich oft 6 zu geben, würde eine zufällige Auswahl zwischen den beiden dazu neigen, die Vorspannung zu verschleiern. (Obwohl in diesem Fall 1 und 6 immer noch mehr als 2, 3, 4 und 5 ergeben würden. Nun, ich denke, abhängig von der Art des Ungleichgewichts.)

Es gibt viele Definitionen von Zufälligkeit. Eine Definition einer Zufallsreihe ist, dass es sich um eine Reihe von Zahlen handelt, die durch einen Zufallsprozess erzeugt werden. Nach dieser Definition ist das eine zufällige Reihe, wenn ich fünfmal einen fairen Würfel würfle und die Zahlen 2, 4, 3, 2, 5 erhalte. Wenn ich dann den gleichen fairen Würfel noch 5 Mal würfle und 1, 1, 1, 1, 1 bekomme, dann ist das auch eine zufällige Serie.

Mehrere Poster haben darauf hingewiesen, dass zufällige Funktionen auf einem Computer nicht wirklich zufällig, sondern pseudozufällig sind und dass sie vollständig vorhersehbar sind, wenn Sie den Algorithmus und den Startwert kennen. Dies ist wahr, aber meistens völlig irrelevant. Wenn ich ein Kartenspiel mische und es dann einzeln umdrehe, sollte dies eine zufällige Serie sein. Wenn jemand auf die Karten schaut, ist das Ergebnis vollständig vorhersehbar, aber nach den meisten Definitionen von Zufälligkeit wird dies nicht weniger zufällig sein. Wenn die Serie statistische Zufälligkeitstests besteht, ändert die Tatsache, dass ich auf die Karten geschaut habe, nichts an dieser Tatsache. In der Praxis ist die Tatsache, dass Sie einen Blick auf die Karten geworfen haben, von großer Bedeutung, wenn wir große Geldsummen auf Ihre Fähigkeit setzen, die nächste Karte zu erraten. Wenn wir die Serie verwenden, um die Menüauswahl der Besucher unserer Website zu simulieren, um die Leistung des Systems zu testen, macht die Tatsache, dass Sie einen Blick darauf geworfen haben, überhaupt keinen Unterschied. (Solange Sie das Programm nicht ändern, um dieses Wissen zu nutzen.)

BEARBEITEN

Ich glaube nicht, dass ich meine Antwort auf das Monty Hall-Problem in einen Kommentar umwandeln könnte, also werde ich meine Antwort aktualisieren.

Für diejenigen, die den Belisarius-Link nicht gelesen haben, lautet das Wesentliche: Ein Game-Show-Teilnehmer hat die Wahl zwischen drei Türen. Hinter einem steckt ein wertvoller Preis, hinter den anderen etwas Wertloses. Er nimmt Tür Nr. 1. Bevor der Gastgeber verrät, ob es sich um einen Gewinner oder einen Verlierer handelt, öffnet er Tür 3, um zu verraten, dass es sich um einen Verlierer handelt. Anschließend gibt er dem Teilnehmer die Möglichkeit, zu Tür 2 zu wechseln. Sollte der Teilnehmer dies tun oder nicht?

Die Antwort, die die Intuition vieler Menschen verletzt, ist, dass er wechseln sollte. Die Wahrscheinlichkeit, dass seine ursprüngliche Wahl der Gewinner war, beträgt 1/3, die andere Tür ist der Gewinner, ist 2/3. Meine anfängliche Intuition, zusammen mit der vieler anderer Leute, ist, dass es keinen Gewinn beim Wechseln geben würde, dass die Chancen gerade auf 50:50 geändert wurden.

Nehmen wir doch an, jemand hat den Fernseher eingeschaltet, kurz nachdem der Gastgeber die Verlierertür geöffnet hat. Diese Person würde zwei verbleibende geschlossene Türen sehen. Angenommen, er kennt die Natur des Spiels, würde er sagen, dass es eine halbe Chance gibt, dass jede Tür den Preis versteckt. Wie können die Chancen für den Zuschauer 1/2: 1/2 sein, während die Chancen für den Teilnehmer 1/3: 2/3 sind?

Ich musste wirklich darüber nachdenken, um meine Intuition in Form zu bringen. Um dies in den Griff zu bekommen, verstehen Sie, dass wir, wenn wir über Wahrscheinlichkeiten in einem solchen Problem sprechen, die Wahrscheinlichkeit meinen, die Sie angesichts der verfügbaren Informationen zuweisen. Für ein Mitglied der Besatzung, das den Preis beispielsweise hinter Tür 1 platziert hat, beträgt die Wahrscheinlichkeit, dass sich der Preis hinter Tür 1 befindet, 100% und die Wahrscheinlichkeit, dass er sich hinter einer der beiden anderen Türen befindet, Null.

Die Gewinnchancen des Besatzungsmitglieds unterscheiden sich von den Gewinnchancen des Teilnehmers, da er etwas weiß, was der Teilnehmer nicht weiß, nämlich hinter welcher Tür er den Preis platziert hat. Ebenso unterscheiden sich die Chancen des Teilnehmers von denen des Zuschauers, da er etwas weiß, was der Betrachter nicht weiß, nämlich welche Tür er ursprünglich ausgewählt hat. Dies ist nicht irrelevant, da die Wahl des Gastgebers, welche Tür geöffnet werden soll, nicht zufällig ist. Er wird die Tür, die der Teilnehmer ausgewählt hat, nicht öffnen, und er wird die Tür nicht öffnen, die den Preis verbirgt. Wenn dies dieselbe Tür ist, bleiben ihm zwei Möglichkeiten. Wenn es sich um verschiedene Türen handelt, bleibt nur eine übrig.

Wie kommen wir also auf 1/3 und 2/3? Als der Teilnehmer ursprünglich eine Tür auswählte, hatte er eine 1/3 Chance, den Gewinner auszuwählen. Ich denke, dass vieles offensichtlich ist. Das heißt, es gab eine 2/3 Chance, dass eine der anderen Türen der Gewinner ist. Wenn der Gastgeber ihm die Möglichkeit geben würde, ohne zusätzliche Informationen zu wechseln, gäbe es keinen Gewinn. Auch dies sollte offensichtlich sein. Aber eine Möglichkeit, es zu betrachten, ist zu sagen, dass es eine 2/3 Chance gibt, dass er durch einen Wechsel gewinnen würde. Aber er hat 2 Alternativen. Jeder hat also nur 2/3 geteilt durch 2 = 1/3 Chance, der Gewinner zu sein, was nicht besser ist als seine ursprüngliche Wahl. Natürlich kannten wir das Endergebnis bereits, dies berechnet es nur anders.

Aber jetzt verrät der Gastgeber, dass eine dieser beiden Möglichkeiten nicht der Gewinner ist. Von der 2/3 Chance, dass eine Tür, die er nicht ausgewählt hat, der Gewinner ist, weiß er jetzt, dass 1 der 2 Alternativen es nicht ist. Der andere könnte oder könnte nicht sein. Er hat also nicht mehr 2/3 geteilt durch 2. Er hat Null für die offene Tür und 2/3 für die geschlossene Tür.

Jay
quelle
Sehr gute Analogien! Ich denke, dies ist eine sehr gute einfache englische Erklärung, und im Gegensatz zu vielen anderen haben Sie meine Frage tatsächlich beantwortet :)
Trufa
@Trufa @Jay Die Verwirrung zwischen möglicher Vorkenntnis der Ereignisse und Zufälligkeit ist SEHR häufig. Lassen Sie mich diese interessante Geschichte über eine Frau mit Ihnen teilen, die ein Problem gelöst und einige der besseren Mathematiker der Akademie beschämt hat. Sie sagten viele Dinge, die sie später bereuen sollten (wie "Sie haben einen Fehler gemacht, aber sehen Sie sich die positive Seite an. Wenn all diese Doktorarbeiten falsch wären, würde das Land in ernsthafte Schwierigkeiten geraten."). Also hier ist die Geschichte, die sich auf Ihre Überlegungen bezieht ... viel Spaß! marilynvossavant.com/articles/gameshow.html
Dr. belisarius
@ Belisarius yep. Ich sage blackjack21 :) nur ein Scherz, ich verstehe dich!
Trufa
@belisarius Übrigens habe ich das nie bekommen, ich werde es jetzt noch einmal versuchen!
Trufa
@Trufa Und hier ist ein Artikel, der die akademische Reaktion auf Marilyns Aussage query.nytimes.com/gst/… (SEHR SEHR lustig) zeigt
Dr. belisarius
11

Stellen Sie sich vor, Sie haben ein einfaches Münzwurfproblem, bei dem gerade als Kopf und ungerade als Schwänze betrachtet werden. Die logische Implementierung ist:

rand() mod 2

Bei einer ausreichend großen Verteilung sollte die Anzahl der geraden Zahlen der Anzahl der ungeraden Zahlen entsprechen.

Betrachten Sie nun eine kleine Änderung:

rand() * rand() mod 2

Wenn eines der Ergebnisse gerade ist, sollte das gesamte Ergebnis gerade sein. Betrachten Sie die 4 möglichen Ergebnisse (gerade * gerade = gerade, gerade * ungerade = gerade, ungerade * gerade = gerade, ungerade * ungerade = ungerade). Bei einer ausreichend großen Verteilung sollte die Antwort sogar 75% der Zeit sein.

Ich würde Köpfe wetten, wenn ich du wäre.

Dieser Kommentar ist eher eine Erklärung dafür, warum Sie keine benutzerdefinierte Zufallsfunktion basierend auf Ihrer Methode implementieren sollten, als eine Diskussion über die mathematischen Eigenschaften der Zufälligkeit.

user479885
quelle
1
In acht nehmen! rand()%2kann nicht sehr zufällig sein; Das hängt wirklich von der Zufälligkeit des niedrigen Bits ab, und einige PRNGs sind auf diese Weise nicht sehr gut. (Natürlich erhalten Sie in einigen Sprachen ein Gleitkomma-Ergebnis, rand()so dass Sie es überhaupt nicht so machen können…)
Donal Fellows
10

Wenn Sie sich nicht sicher sind, was mit den Kombinationen Ihrer Zufallszahlen passieren wird, können Sie die Lehren aus der statistischen Theorie ziehen.

In der Situation von OP möchte er wissen, was das Ergebnis von X * X = X ^ 2 ist, wobei X eine Zufallsvariable ist, die entlang Uniform [0,1] verteilt ist. Wir werden die CDF-Technik verwenden, da es sich nur um eine Eins-zu-Eins-Zuordnung handelt.

Da X ~ Uniform [0,1] ist, ist cdf: f X (x) = 1 Wir wollen die Transformation Y <- X ^ 2, also y = x ^ 2 Finden Sie das inverse x (y): sqrt (y) = x dies gibt uns x als Funktion von y. Als nächstes finden Sie die Ableitung dx / dy: d / dy (sqrt (y)) = 1 / (2 sqrt (y))

Die Verteilung von Y ist gegeben als: f Y (y) = f X (x (y)) | dx / dy | = 1 / (2 sqrt (y))

Wir sind noch nicht fertig, wir müssen die Domäne von Y erhalten, da 0 <= x <1, 0 <= x ^ 2 <1, also liegt Y im Bereich [0, 1). Wenn Sie überprüfen möchten, ob das PDF von Y tatsächlich ein PDF ist, integrieren Sie es über die Domäne: Integrieren Sie 1 / (2 sqrt (y)) von 0 bis 1, und es wird tatsächlich als 1 angezeigt. Beachten Sie auch die Form des Diese Funktion sieht aus wie das, was belisarious gepostet hat.

Was Dinge wie X 1 + X 2 + ... + X n betrifft (wobei X i ~ Uniform [0,1]), können wir uns einfach auf den zentralen Grenzwertsatz berufen, der für jede Verteilung funktioniert, deren Momente existieren. Deshalb gibt es den Z-Test tatsächlich.

Andere Techniken zur Bestimmung des resultierenden PDFs umfassen die Jacobi-Transformation (die verallgemeinerte Version der cdf-Technik) und die MGF-Technik.

EDIT: Zur Verdeutlichung beachten Sie, dass ich über die Verteilung der resultierenden Transformation und nicht über ihre Zufälligkeit spreche . Das ist eigentlich für eine separate Diskussion. Was ich tatsächlich abgeleitet habe, war auch für (rand ()) ^ 2. Für rand () * rand () ist es viel komplizierter, was auf keinen Fall zu einer gleichmäßigen Verteilung führt.

Wil
quelle
9

Es ist nicht genau offensichtlich, aber rand()in der Regel eher zufällig als rand()*rand(). Wichtig ist, dass dies für die meisten Anwendungen nicht sehr wichtig ist.

Aber zuerst produzieren sie unterschiedliche Verteilungen. Dies ist kein Problem, wenn Sie dies möchten, aber es spielt eine Rolle. Wenn Sie eine bestimmte Verteilung benötigen, ignorieren Sie die gesamte Frage „Was ist zufälliger?“. Warum ist rand()mehr zufällig?

Der Kern des Warum rand()Zufälliger ist (unter der Annahme, dass Gleitkomma-Zufallszahlen mit dem sehr häufigen Bereich [0..1] erzeugt werden), dass Sie erhalten, wenn Sie zwei FP-Zahlen mit vielen Informationen in der Mantisse multiplizieren ein gewisser Informationsverlust am Ende; Es gibt einfach nicht genug Bit in einem IEEE-Float mit doppelter Genauigkeit, um alle Informationen zu speichern, die in zwei IEEE-Floats mit doppelter Genauigkeit enthalten waren, die gleichmäßig zufällig aus [0..1] ausgewählt wurden, und diese zusätzlichen Informationsbits gehen verloren. Natürlich spielt es keine Rolle, da Sie diese Informationen (wahrscheinlich) nicht verwenden würden, aber der Verlust ist real. Es spielt auch keine Rolle, welche Distribution Sie produzieren (dh welche Operation Sie für die Kombination verwenden). Jede dieser Zufallszahlen enthält (bestenfalls) 52 Bit Zufallsinformationen - das '

Die meisten Verwendungen von Zufallszahlen verwenden nicht einmal annähernd so viel Zufälligkeit, wie tatsächlich in der Zufallsquelle verfügbar ist. Holen Sie sich ein gutes PRNG und machen Sie sich nicht zu viele Sorgen. (Der Grad der „Güte“ hängt davon ab, was Sie damit machen. Sie müssen vorsichtig sein, wenn Sie Monte-Carlo-Simulationen oder Kryptografien durchführen. Andernfalls können Sie wahrscheinlich das Standard-PRNG verwenden, da dies normalerweise viel schneller ist.)

Donal Fellows
quelle
1
Diese Antwort muss wirklich in Verbindung mit Belisarius 'großartiger Antwort gelesen werden. Sie decken verschiedene Aspekte des Problems ab.
Donal Fellows
7

Floating Randoms basieren im Allgemeinen auf einem Algorithmus, der eine Ganzzahl zwischen Null und einem bestimmten Bereich erzeugt. Wenn Sie also rand () * rand () verwenden, sagen Sie im Wesentlichen int_rand () * int_rand () / rand_max ^ 2 - was bedeutet, dass Sie jede Primzahl / rand_max ^ 2 ausschließen.

Das verändert die randomisierte Verteilung erheblich.

rand () ist auf den meisten Systemen gleichmäßig verteilt und bei ordnungsgemäßer Aussaat schwer vorherzusagen. Verwenden Sie dies, es sei denn, Sie haben einen bestimmten Grund, damit zu rechnen (dh die Verteilung auf eine benötigte Kurve zu formen).

Fordi
quelle
@belisarius: Das ist nur der Fall, wenn 1 ein mögliches Ergebnis des zufälligen Prozesses ist.
Joris Meys
Ich musste die Antworten lange durchlesen, bevor ich diese fand. Sie geben ein klares Problem an: Der Ergebnisraum (Anzahl möglicher Werte) von rand()*rand()ist kleiner als der Ergebnisraum von rand()- da Primzahlen ausgeschlossen sind. Erhält meine Stimme ...
Floris
7

Das Multiplizieren von Zahlen würde je nach Computerarchitektur in einem kleineren Lösungsbereich enden.

Wenn auf dem Display Ihres Computers 16 Ziffern angezeigt werden, würde rand()0,1234567890123 multipliziert mit einer Sekunde rand()0,1234567890123 0,0152415 ergeben, was Sie definitiv weniger Lösungen finden würden, wenn Sie das Experiment 10 ^ 14 Mal wiederholen würden.

Huub
quelle
3

Die meisten dieser Verteilungen treten auf, weil Sie die Zufallszahl begrenzen oder normalisieren müssen.

Wir normalisieren, dass alles positiv ist, in einen Bereich passt und sogar in die Einschränkungen der Speichergröße für den zugewiesenen Variablentyp passt.

Mit anderen Worten, da wir den Zufallsaufruf zwischen 0 und X begrenzen müssen (X ist die Größenbeschränkung unserer Variablen), haben wir eine Gruppe von "Zufallszahlen" zwischen 0 und X.

Wenn Sie nun die Zufallszahl zu einer anderen Zufallszahl hinzufügen, liegt die Summe irgendwo zwischen 0 und 2X ... dies verzerrt die Werte von den Randpunkten weg (die Wahrscheinlichkeit, zwei kleine Zahlen zusammen und zwei große Zahlen zusammen zu addieren, ist sehr gering, wenn Sie haben zwei Zufallszahlen über einen großen Bereich).

Stellen Sie sich den Fall vor, in dem Sie eine Zahl nahe Null hatten und diese mit einer anderen Zufallszahl addieren. Sie wird sicherlich größer und von 0 entfernt (dies gilt sowohl für große Zahlen als auch für zwei große Zahlen (Zahlen nahe X) werden von der Zufallsfunktion zweimal zurückgegeben.

Wenn Sie nun die Zufallsmethode mit negativen und positiven Zahlen (die sich gleichmäßig über die Nullachse erstrecken) einrichten würden, wäre dies nicht mehr der Fall.

Nehmen RandomReal({-x, x}, 50000, .01)wir zum Beispiel an, Sie würden eine gleichmäßige Verteilung der Zahlen auf der negativen und einer positiven Seite erhalten, und wenn Sie die Zufallszahlen addieren würden, würden sie ihre "Zufälligkeit" beibehalten.

Jetzt bin ich mir nicht sicher, was Random() * Random()mit der negativen bis positiven Spanne passieren würde ... das wäre eine interessante Grafik ... aber ich muss jetzt wieder Code schreiben. :-P

user479538
quelle
2
  1. Es gibt nicht so etwas wie mehr zufällig. Es ist entweder zufällig oder nicht. Zufällig bedeutet "schwer vorherzusagen". Es bedeutet nicht nicht deterministisch. Sowohl random () als auch random () * random () sind gleichermaßen zufällig, wenn random () zufällig ist. Die Verteilung ist für die Zufälligkeit irrelevant. Wenn eine ungleichmäßige Verteilung auftritt, bedeutet dies nur, dass einige Werte wahrscheinlicher sind als andere. Sie sind immer noch unvorhersehbar.

  2. Da es sich um Pseudozufälligkeit handelt, sind die Zahlen sehr deterministisch. In Zufallsmodellen und Simulationen ist jedoch häufig eine Pseudozufälligkeit ausreichend. Es ist ziemlich bekannt, dass die Kompliziertheit eines Pseudozufallszahlengenerators die Analyse nur erschwert. Es ist unwahrscheinlich, dass sich die Zufälligkeit verbessert. es führt häufig dazu, dass statistische Tests fehlschlagen.

  3. Die gewünschten Eigenschaften der Zufallszahlen sind wichtig: Wiederholbarkeit und Reproduzierbarkeit, statistische Zufälligkeit, (normalerweise) gleichmäßig verteilt, und ein großer Zeitraum sind nur einige wenige.

  4. In Bezug auf Transformationen auf Zufallszahlen: Wie jemand sagte, führt die Summe von zwei oder mehr gleichmäßig verteilten zu einer Normalverteilung. Dies ist der additive zentrale Grenzwertsatz. Sie gilt unabhängig von der Quelldistribution, solange alle Distributionen unabhängig und identisch sind. Das MultiplikativDer zentrale Grenzwertsatz besagt, dass das Produkt von zwei oder mehr unabhängigen und indentisch verteilten Zufallsvariablen lognormal ist. Das Diagramm, das jemand anderes erstellt hat, sieht exponentiell aus, ist aber sehr normal. Random () * random () ist also logarithmisch verteilt (obwohl es möglicherweise nicht unabhängig ist, da Zahlen aus demselben Stream gezogen werden). Dies kann in einigen Anwendungen wünschenswert sein. In der Regel ist es jedoch besser, eine Zufallszahl zu generieren und in eine logarithmisch normal verteilte Zahl umzuwandeln. Random () * random () ist möglicherweise schwer zu analysieren.

Weitere Informationen finden Sie in meinem Buch unter www.performorama.org. Das Buch befindet sich im Aufbau, aber das relevante Material ist da. Beachten Sie, dass sich die Kapitel- und Abschnittsnummern im Laufe der Zeit ändern können. Kapitel 8 (Wahrscheinlichkeitstheorie) - Abschnitte 8.3.1 und 8.3.3, Kapitel 10 (Zufallszahlen).

Tom
quelle
1

Wir können zwei Reihen von Zahlen hinsichtlich der Zufälligkeit unter Verwendung der Kolmogorov-Komplexität vergleichen. Wenn die Folge von Zahlen nicht komprimiert werden kann, ist es die zufälligste, die wir bei dieser Länge erreichen können ... Ich weiß, dass diese Art der Messung eher eine theoretische ist Möglichkeit...

HamoriZ
quelle
1

Eigentlich, wenn Sie darüber nachdenken, rand() * rand()ist weniger zufällig alsrand() . Hier ist der Grund.

Im Wesentlichen gibt es die gleiche Anzahl von ungeraden Zahlen wie gerade Zahlen. Und zu sagen, dass 0,04325 ungerade ist und wie 0,388 gerade ist und 0,4 gerade ist und 0,15 ungerade ist,

Das bedeutet, dass rand()die gleiche Chance besteht, eine gerade oder ungerade Dezimalstelle zu sein .

Auf der anderen Seite sind rand() * rand()die Gewinnchancen etwas anders gestapelt. Sagen wir:

double a = rand();
double b = rand();
double c = a * b;

aund bbeide haben eine 50% ige Chance, gerade oder ungerade zu sein. Wissend, dass

  • gerade * gerade = gerade
  • gerade * ungerade = gerade
  • ungerade * ungerade = ungerade
  • ungerade * gerade = gerade

bedeutet, dass es eine 75% ige Chance gibt , die gerade cist, während nur eine 25% ige Chance ungerade ist, was den Wert rand() * rand()vorhersehbarer macht als rand(), also weniger zufällig.

John S.
quelle
rand()Gibt normalerweise eine Zahl zwischen 0 und 1 an. Ist es sinnvoll, darüber zu sprechen, ob es gerade oder ungerade ist?
Teepeemm
1
Eigentlich 0.2*0.2=0.04, was darauf hindeutet , einen grundlegenden Fehler bei diesem Ansatz: die 53 Bits von zwei Doppel - Multiplikation wird etwa 100 Bits im Ergebnis. Die letzte Hälfte dieser Bits wird jedoch verworfen. Wenn Sie also zwei Doppel mit einer 1 als niedrigstwertigem Bit nehmen, können Sie nichts über das niedrigstwertige Bit ihres Produkts sagen.
Teepeemm
Oder anders ausgedrückt, Sie haben angenommen, dass die Definition von "gerade" und "ungerade", die für die Verteilung von sinnvoll rand()ist, die gleichen ist wie die Definitionen von "gerade" und "ungerade", die für die Verteilung sinnvoll sind von rand()*rand(). Ist dies nicht der Fall, schlägt dieses Argument fehl. Das gilt für ganze Zahlen, aber dies sind keine ganzen Zahlen.
David Schwartz
0

Verwenden Sie ein lineares Rückkopplungsschieberegister (LFSR), das ein primitives Polynom implementiert.

Das Ergebnis ist eine Folge von 2 ^ n Pseudozufallszahlen, dh keine Wiederholung in der Folge, wobei n die Anzahl der Bits im LFSR ist .... was zu einer gleichmäßigen Verteilung führt.

http://en.wikipedia.org/wiki/Linear_feedback_shift_register http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf

Verwenden Sie einen "zufälligen" Startwert basierend auf Mikrosekunden Ihrer Computeruhr oder eine Teilmenge des md5-Ergebnisses für einige sich ständig ändernde Daten in Ihrem Dateisystem.

Beispielsweise generiert ein 32-Bit-LFSR 2 ^ 32 eindeutige Zahlen nacheinander (Nr. 2 gleich), beginnend mit einem bestimmten Startwert. Die Sequenz wird immer in der gleichen Reihenfolge sein, aber der Startpunkt wird (offensichtlich) für einen anderen Samen unterschiedlich sein. Wenn also eine sich möglicherweise wiederholende Sequenz zwischen den Aussaat kein Problem darstellt, ist dies möglicherweise eine gute Wahl.

Ich habe 128-Bit-LFSRs verwendet, um zufällige Tests in Hardware-Simulatoren unter Verwendung eines Startwerts zu generieren, der die md5-Ergebnisse bei sich ständig ändernden Systemdaten darstellt.

Johnny
quelle
0

Angenommen, es wird rand()eine Zahl zwischen zurückgegeben [0, 1), die offensichtlich rand() * rand()auf 0 vorgespannt ist. Dies liegt daran, dass das Multiplizieren xmit einer Zahl zwischen [0, 1)eine Zahl kleiner als ergibt x. Hier ist die Verteilung von 10000 weiteren Zufallszahlen:

Wenn rand()eine Ganzzahl zwischen zurückgegeben [x, y]wird, haben Sie die folgende Verteilung. Beachten Sie die Anzahl der ungeraden und geraden Werte:

Salman A.
quelle
-1

OK, also werde ich versuchen, einen Mehrwert hinzuzufügen, um andere Antworten zu ergänzen, indem ich sage, dass Sie einen Zufallszahlengenerator erstellen und verwenden.

Zufallszahlengeneratoren sind Geräte (im allgemeinen Sinne) mit mehreren Eigenschaften, die an einen bestimmten Zweck angepasst werden können. Einige von ihnen (von mir) sind:

  • Entropie: wie bei Shannon Entropy
  • Verteilung: statistische Verteilung (Poisson, Normal usw.)
  • Typ: Woher stammen die Zahlen (Algorithmus, Naturereignis, Kombination usw.) und der angewendete Algorithmus?
  • Effizienz: Schnelligkeit oder Komplexität der Ausführung.
  • Muster: Periodizität, Sequenzen, Läufe usw.
  • und wahrscheinlich mehr ...

In den meisten Antworten steht hier die Verteilung im Mittelpunkt des Interesses. Durch Mischen und Anpassen von Funktionen und Parametern schaffen Sie jedoch neue Methoden zum Generieren von Zufallszahlen mit unterschiedlichen Merkmalen, für die die Bewertung auf den ersten Blick möglicherweise nicht offensichtlich ist.

Loki
quelle
-1

Es ist leicht zu zeigen, dass die Summe der beiden Zufallszahlen nicht unbedingt zufällig ist. Stellen Sie sich vor, Sie haben einen 6-seitigen Würfel und Wurf. Jede Zahl hat eine Chance von 1/6 zu erscheinen. Angenommen, Sie hatten 2 Würfel und summierten das Ergebnis. Die Verteilung dieser Beträge beträgt nicht 1/12. Warum? Weil bestimmte Zahlen häufiger erscheinen als andere. Es gibt mehrere Partitionen von ihnen. Zum Beispiel ist die Zahl 2 nur die Summe von 1 + 1, aber 7 kann durch 3 + 4 oder 4 + 3 oder 5 + 2 usw. gebildet werden, so dass die Wahrscheinlichkeit größer ist, dass sie auftaucht.

Das Anwenden einer Transformation, in diesem Fall das Hinzufügen einer Zufallsfunktion, macht sie daher nicht zufälliger oder bewahrt notwendigerweise die Zufälligkeit. Im Fall der obigen Würfel ist die Verteilung auf 7 verzerrt und daher weniger zufällig.

Sashang
quelle
-1

Wie andere bereits betont haben, ist diese Frage schwer zu beantworten, da jeder von uns sein eigenes Bild von Zufälligkeit im Kopf hat.

Aus diesem Grund würde ich Ihnen wärmstens empfehlen, sich etwas Zeit zu nehmen und diese Website durchzulesen, um eine bessere Vorstellung von Zufälligkeit zu erhalten:

Um auf die eigentliche Frage zurückzukommen. Es gibt keinen mehr oder weniger zufälligen Begriff:

beides erscheint nur zufällig !

In beiden Fällen - nur rand () oder rand () * rand () - ist die Situation dieselbe: Nach einigen Milliarden Zahlen wiederholt sich die Sequenz (!) . Es erscheint dem Betrachter zufällig, weil er nicht die gesamte Sequenz kennt, aber der Computer keine echte Zufallsquelle hat - also kann er auch keine Zufälligkeit erzeugen.

zB: Ist das Wetter zufällig? Wir haben nicht genügend Sensoren oder Kenntnisse, um festzustellen, ob das Wetter zufällig ist oder nicht.

Fabian Bigler
quelle
-2

Die Antwort wäre, es kommt darauf an, hoffentlich wäre rand () * rand () zufälliger als rand (), aber als:

  • Beide Antworten hängen von der Bitgröße Ihres Werts ab
  • dass in den meisten Fällen Sie in Abhängigkeit von einem Pseudozufallsalgorithmus generieren (der meistens ein Zahlengenerator ist, der von Ihrer Computeruhr abhängt und nicht so viel zufällig ist).
  • Machen Sie Ihren Code lesbarer (und rufen Sie mit dieser Art von Mantra keinen zufälligen Voodoo-Gott des Zufalls auf).

Nun, wenn Sie eines der oben genannten Punkte überprüfen, schlage ich vor, dass Sie sich für das einfache "rand ()" entscheiden. Weil Ihr Code besser lesbar wäre (ich würde mich nicht fragen, warum Sie das geschrieben haben, für ... nun ... mehr als 2 Sekunden), einfach zu warten (wenn Sie Ihre Rand-Funktion durch einen super_rand ersetzen möchten).

Wenn Sie einen besseren Zufall wünschen, würde ich Ihnen empfehlen, ihn von jeder Quelle zu streamen, die genügend Rauschen ( Radio Static ) liefert , und dann sollte ein einfacher rand()ausreichen.

dvhh
quelle