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.
math
language-agnostic
random
Trufa
quelle
quelle
Antworten:
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:
Dies ist zwar die Verteilung, die Sie nach Multiplikation zweier Zufallsvariablen erhalten:
Beide sind also „zufällig“, aber ihre Verteilung ist sehr unterschiedlich.
Ein anderes Beispiel
Während 2 * Random () gleichmäßig verteilt ist:
Random () + Random () ist nicht!
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:
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:
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
quelle
rand()+rand()
, würden Sie eine Verteilung vom Typ "2W6" mit einem Fettzentrum erhalten.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 einerrand()
ist0
, wird die Summe0
quelle
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
x
Startwert, der die folgende Werteliste generiert:rand()
generiert die obige Liste undrand() * rand()
generiert: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.3
trotz 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.quelle
rand()+rand()+rand()...
zunehmend "weniger zufällig" wird (wenn Sie zufällig gleichmäßig verteilt meinen).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.Übervereinfachung zur Veranschaulichung eines Punktes.
Angenommen, Ihre Zufallsfunktion gibt nur
0
oder aus1
.random()
ist einer von(0,1)
, ist aberrandom()*random()
einer von(0,0,0,1)
Sie können deutlich sehen, dass die Chancen,
0
im zweiten Fall eine zu bekommen, in keiner Weise denen entsprechen, die eine bekommen1
.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 verstehtrandom()*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)/2
oder 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ärerandom(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.quelle
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.)
quelle
Die obligatorische xkcd ...
quelle
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:
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.
quelle
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:sqrt(rand(range^2))
(rand(range) + rand(range))/2
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.quelle
Die meisten rand () - Implementierungen haben einen gewissen Zeitraum. Dh nach einer enormen Anzahl von Aufrufen wiederholt sich die Sequenz. Die Reihenfolge der Ausgänge von
rand() * 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.
quelle
"zufällig" vs. "zufälliger" ist ein bisschen wie die Frage, welche Null mehr null ist.
In diesem Fall
rand
handelt 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.
quelle
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.
quelle
4
oder Binärzahl von @CurtainDog xkcd0100
kann 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.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 wirdRAND_MAX
zufällig definiert,2^n - 1
won
eine Ganzzahl ist (dies ist in der Microsoft-Implementierung der Fall, won
15 ist). Dann würden wir sagen, dass eine gute Implementierungn
Informationen 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 bis
2^15 - 1
= 32767. Jede Zahl in diesem Bereich ist ein eindeutiges Bitmuster, z.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ügenrand()
. 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önnenrand()
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.
quelle
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.
quelle
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:
Bei einer ausreichend großen Verteilung sollte die Anzahl der geraden Zahlen der Anzahl der ungeraden Zahlen entsprechen.
Betrachten Sie nun eine kleine Änderung:
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.
quelle
rand()%2
kann 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…)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.
quelle
Es ist nicht genau offensichtlich, aber
rand()
in der Regel eher zufällig alsrand()*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.)
quelle
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).
quelle
rand()*rand()
ist kleiner als der Ergebnisraum vonrand()
- da Primzahlen ausgeschlossen sind. Erhält meine Stimme ...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 Sekunderand()
0,1234567890123 0,0152415 ergeben, was Sie definitiv weniger Lösungen finden würden, wenn Sie das Experiment 10 ^ 14 Mal wiederholen würden.quelle
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. :-Pquelle
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.
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.
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.
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).
quelle
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...
quelle
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:a
undb
beide haben eine 50% ige Chance, gerade oder ungerade zu sein. Wissend, dassbedeutet, dass es eine 75% ige Chance gibt , die gerade
c
ist, während nur eine 25% ige Chance ungerade ist, was den Wertrand() * rand()
vorhersehbarer macht alsrand()
, also weniger zufällig.quelle
rand()
Gibt normalerweise eine Zahl zwischen 0 und 1 an. Ist es sinnvoll, darüber zu sprechen, ob es gerade oder ungerade ist?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.rand()
ist, die gleichen ist wie die Definitionen von "gerade" und "ungerade", die für die Verteilung sinnvoll sind vonrand()*rand()
. Ist dies nicht der Fall, schlägt dieses Argument fehl. Das gilt für ganze Zahlen, aber dies sind keine ganzen Zahlen.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.
quelle
Angenommen, es wird
rand()
eine Zahl zwischen zurückgegeben[0, 1)
, die offensichtlichrand() * rand()
auf 0 vorgespannt ist. Dies liegt daran, dass das Multiplizierenx
mit einer Zahl zwischen[0, 1)
eine Zahl kleiner als ergibtx
. Hier ist die Verteilung von 10000 weiteren Zufallszahlen:Code-Snippet anzeigen
Wenn
rand()
eine Ganzzahl zwischen zurückgegeben[x, y]
wird, haben Sie die folgende Verteilung. Beachten Sie die Anzahl der ungeraden und geraden Werte:Code-Snippet anzeigen
quelle
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:
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.
quelle
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.
quelle
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.
quelle
Die Antwort wäre, es kommt darauf an, hoffentlich wäre rand () * rand () zufälliger als rand (), aber als:
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.quelle