Das Verständnis des "Zufalls"

Question

Ich kann mir das nicht erklären, was ist zufälliger?

rand()

OR :

rand() * rand()

Ich finde es eine echte Denksportaufgabe, könnten Sie mir helfen?

---

EDITAR:

Intuitiv weiß ich, dass die mathematische Antwort lauten wird, dass sie gleichermaßen zufällig sind, aber ich kann mir nicht helfen, aber ich denke, dass, wenn man den "Zufallszahlenalgorithmus" zweimal laufen lässt, wenn man die beiden miteinander multipliziert, etwas Zufälligeres entsteht als wenn man es nur einmal macht.

Answer 1

Das Konzept, nach dem Sie suchen, ist "Entropie", der "Grad" der Unordnung einer Kette von Bits. Die Idee ist am einfachsten zu verstehen, wenn man das Konzept der "maximalen Entropie" verwendet.

Eine ungefähre Definition einer Bitfolge mit maximaler Entropie ist, dass sie nicht genau durch eine kürzere Bitfolge ausgedrückt werden kann (d. h. mit einem Algorithmus, der die kleinere Zeichenfolge wieder in die ursprüngliche Zeichenfolge zu zerlegen).

Die Bedeutung der maximalen Entropie für die Zufälligkeit ergibt sich aus der Tatsache, dass wenn man eine Zahl "zufällig" auswählt, wird man mit ziemlicher Sicherheit eine Zahl auswählen deren Bitfolge nahe an der maximalen Entropie liegt, d. h. sie kann nicht komprimiert werden. Dies ist unser bestes Verständnis dessen, was eine "zufällige" Zahl ausmacht.

Wenn Sie also aus zwei Zufallsstichproben eine Zufallszahl erzeugen wollen, die "doppelt" so zufällig ist zufällig ist, würde man verketten die beiden Bitstrings zusammen. Praktisch würde man einfach die Samples in die obere und untere Hälfte eines Wortes mit doppelter Länge stecken.

Wenn Sie mit einem miserablen rand() zu kämpfen haben, kann es manchmal helfen kann es manchmal helfen, ein paar Samples zusammen zu xorieren --- obwohl, wenn es wirklich kaputt ist, wird sogar dieses Verfahren nicht helfen wird.

Answer 2

Die akzeptierte Antwort ist sehr schön, aber es gibt auch eine andere Möglichkeit, Ihre Frage zu beantworten. PachydermPuncher's Antwort verfolgt bereits diesen alternativen Ansatz, und ich werde ihn nur ein wenig ausweiten.

Am einfachsten lässt sich die Informationstheorie in Bezug auf die kleinste Informationseinheit, ein einzelnes Bit, betrachten.

In der C-Standardbibliothek, rand() gibt eine Ganzzahl im Bereich von 0 bis RAND_MAX , eine Grenze, die je nach Plattform unterschiedlich definiert sein kann. Angenommen, RAND_MAX wird zufällig definiert als 2^n - 1 donde n eine ganze Zahl ist (dies ist bei der Implementierung von Microsoft der Fall, wo n ist 15). Dann würden wir sagen, dass eine gute Implementierung Folgendes zurückgeben würde n Bits an Informationen.

Stellen Sie sich das vor rand() konstruiert Zufallszahlen, indem es eine Münze wirft, um den Wert eines Bits zu ermitteln, und dies dann so lange wiederholt, bis es einen Stapel von 15 Bits hat. Dann sind die Bits unabhängig (der Wert eines Bits hat keinen Einfluss auf die Wahrscheinlichkeit, dass andere Bits im selben Stapel einen bestimmten Wert haben). Jedes Bit, das unabhängig betrachtet wird, ist also eine Zufallszahl zwischen 0 und 1, die "gleichmäßig" über diesen Bereich verteilt ist (mit gleicher Wahrscheinlichkeit 0 wie 1).

Die Unabhängigkeit der Bits stellt sicher, dass die durch Bits dargestellten Zahlen auch gleichmäßig über ihren Bereich verteilt sind. Dies ist intuitiv offensichtlich: Bei 15 Bits ist der zulässige Bereich Null bis 2^15 - 1 = 32767. Jede Zahl in diesem Bereich ist ein einzigartiges Muster von Bits, wie z. B:

010110101110010

und wenn die Bits unabhängig sind, ist kein Muster wahrscheinlicher als ein anderes. Alle möglichen Zahlen in dem Bereich sind also gleich wahrscheinlich. Umgekehrt ist es genauso: Wenn rand() gleichmäßig verteilte ganze Zahlen erzeugt, dann bestehen diese Zahlen aus unabhängigen Bits.

Denken Sie also an rand() als Produktionslinie für die Herstellung von Bits, die zufällig in Stapeln beliebiger Größe ausgeliefert werden. Wenn Ihnen die Größe nicht gefällt, zerlegen Sie die Stapel in einzelne Bits und setzen Sie sie dann in beliebiger Menge wieder zusammen (wenn Sie allerdings einen bestimmten Bereich benötigen, der keine Potenz von 2 ist, müssen Sie Ihre Zahlen schrumpfen, und das geht bei weitem am einfachsten, indem Sie sie in Fließkommazahlen umwandeln).

Um auf Ihren ursprünglichen Vorschlag zurückzukommen, nehmen wir an, Sie möchten von 15 auf 30 Chargen umsteigen und fragen rand() für die erste Zahl, verschiebt sie um 15 Stellen und fügt dann eine weitere rand() dazu. Dies ist eine Möglichkeit, zwei Aufrufe zu kombinieren rand() ohne eine gleichmäßige Verteilung zu stören. Es funktioniert einfach, weil es keine Überschneidungen zwischen den Orten gibt, an denen Sie die Informationen platzieren.

Dies ist etwas ganz anderes als die "Ausdehnung" der Reichweite von rand() durch Multiplikation mit einer Konstante. Wenn Sie zum Beispiel den Bereich von rand() könnte man mit zwei multiplizieren - aber dann würde man immer nur gerade und nie ungerade Zahlen erhalten! Das ist nicht gerade eine gleichmäßige Verteilung und könnte je nach Anwendung ein ernsthaftes Problem darstellen, z. B. bei einem rouletteähnlichen Spiel, das angeblich ungerade/gerade Wetten zulässt. (Wenn man in Bits denkt, würde man diesen Fehler intuitiv vermeiden, denn man würde erkennen, dass die Multiplikation mit zwei dasselbe ist wie das Verschieben der Bits nach links (größere Bedeutung) um eine Stelle und das Auffüllen der Lücke mit Null. Die Informationsmenge ist also dieselbe - sie hat sich nur ein wenig verschoben).

Solche Lücken in Zahlenbereichen können in Fließkommazahlenanwendungen nicht beanstandet werden, da Fließkommazahlenbereiche von Natur aus Lücken aufweisen, die einfach überhaupt nicht dargestellt werden können: eine unendlich Anzahl der fehlenden reellen Zahlen in der Lücke zwischen jeweils zwei darstellbaren Gleitkommazahlen existieren! Wir müssen also sowieso lernen, mit Lücken zu leben.

Wie schon andere gewarnt haben, ist Intuition in diesem Bereich riskant, vor allem weil Mathematiker dem Reiz der reellen Zahlen nicht widerstehen können, die furchtbar verwirrend sind und voller knorriger Unendlichkeiten und scheinbarer Paradoxien.

Aber wenn man in Bits denkt, kommt man mit seiner Intuition vielleicht ein Stück weiter. Bits sind wirklich einfach - sogar Computer sie verstehen können.

Answer 3

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

Angenommen, Sie spielen ein Würfelspiel. Sie haben ein paar völlig faire, zufällige Würfel. Wären die Würfelwürfe "zufälliger", wenn Sie vor jedem Wurf zwei Würfel in eine Schale legen, diese schütteln, einen der Würfel zufällig auswählen und dann diesen würfeln würden? Es würde eindeutig keinen Unterschied machen. Wenn beide Würfel zufällige Zahlen ergeben, dann macht es keinen Unterschied, wenn man einen der beiden Würfel zufällig auswählt. In jedem Fall erhält man eine Zufallszahl zwischen 1 und 6 mit gleichmäßiger Verteilung über eine ausreichende Anzahl von Würfen.

Ich nehme an, im wirklichen Leben könnte ein solches Verfahren nützlich sein, wenn man vermutet, dass die Würfel NICHT fair sind. Wenn, sagen wir, die Würfel etwas unausgewogen sind, so dass einer dazu neigt, häufiger als 1/6 der Zeit eine 1 zu ergeben, und ein anderer dazu neigt, ungewöhnlich oft eine 6 zu ergeben, dann würde eine zufällige Auswahl zwischen den beiden dazu tendieren, die Verzerrung zu verschleiern. (Obwohl in diesem Fall 1 und 6 immer noch häufiger vorkommen würden als 2, 3, 4 und 5. Nun, das hängt wohl von der Art des Ungleichgewichts ab.)

Es gibt viele Definitionen von Zufälligkeit. Eine Definition einer Zufallsreihe lautet, dass es sich um eine Reihe von Zahlen handelt, die durch einen Zufallsprozess erzeugt werden. Wenn ich einen fairen Würfel fünfmal werfe und die Zahlen 2, 4, 3, 2, 5 erhalte, ist das nach dieser Definition eine Zufallsreihe. Wenn ich dann denselben fairen Würfel noch fünfmal werfe und 1, 1, 1, 1, 1 erhalte, dann ist das auch eine Zufallsreihe.

Mehrere Poster haben darauf hingewiesen, dass Zufallsfunktionen auf einem Computer nicht wirklich zufällig sind, sondern eher pseudozufällig, und dass sie völlig vorhersehbar sind, wenn man den Algorithmus und den Seed kennt. Das stimmt zwar, ist aber in den meisten Fällen völlig irrelevant. Wenn ich ein Kartenspiel mische und dann eine Karte nach der anderen umdrehe, sollte dies eine zufällige Folge sein. Wenn jemand einen Blick auf die Karten wirft, wird das Ergebnis völlig vorhersehbar sein, aber nach den meisten Definitionen von Zufall wird es dadurch nicht weniger zufällig. Wenn die Serie statistische Zufallstests besteht, ändert die Tatsache, dass ich in die Karten geschaut habe, nichts an dieser Tatsache. Wenn wir in der Praxis große Geldsummen auf Ihre Fähigkeit setzen, die nächste Karte zu erraten, ist die Tatsache, dass Sie einen Blick auf die Karten geworfen haben, sehr wichtig. Wenn wir die Serie verwenden, um die Kartenwahl der Besucher unserer Website zu simulieren, um die Leistung des Systems zu testen, dann macht die Tatsache, dass Sie die Karten angeschaut haben, überhaupt keinen Unterschied. (Solange Sie das Programm nicht verändern, um sich dieses Wissen zunutze zu machen).

EDIT

Ich glaube nicht, dass ich meine Antwort auf das Monty-Hall-Problem in einen Kommentar packen konnte, also werde ich meine Antwort aktualisieren.

Für diejenigen, die den Link von Belisarius nicht gelesen haben, hier die Quintessenz: Ein Kandidat einer Spielshow hat die Wahl zwischen 3 Türen. Hinter einer befindet sich ein wertvoller Preis, hinter den anderen etwas Wertloses. Er wählt Tür Nr. 1. Bevor der Moderator verrät, ob es sich um einen Gewinner oder einen Verlierer handelt, öffnet er Tür Nr. 3, um zu verraten, dass es sich um einen Verlierer handelt. Dann gibt er dem Teilnehmer die Möglichkeit, zu Tür 2 zu wechseln. Sollte der Kandidat dies tun oder nicht?

Die Antwort, die die Intuition vieler Menschen verletzt, lautet, dass er wechseln sollte. Die Wahrscheinlichkeit, dass sein ursprünglicher Tipp der Gewinner ist, liegt bei 1/3, die Wahrscheinlichkeit, dass die andere Tür der Gewinner ist, bei 2/3. Meine anfängliche Intuition und die vieler anderer Leute ist, dass es keinen Vorteil bringt, zu tauschen, dass die Chancen gerade auf 50:50 geändert wurden.

Angenommen, jemand schaltet den Fernseher ein, kurz nachdem der Gastgeber die Verlierertür geöffnet hat. Diese Person würde zwei verbleibende geschlossene Türen sehen. Unter der Annahme, dass er die Natur des Spiels kennt, würde er sagen, dass es eine 1/2 Chance gibt, dass jede Tür den Preis verbirgt. Wie kann die Chance für den Zuschauer 1/2 : 1/2 sein, während die Chance für den Teilnehmer 1/3 : 2/3 ist?

Ich musste wirklich darüber nachdenken, um meine Intuition auf Vordermann zu bringen. Um das Problem in den Griff zu bekommen, muss man sich klarmachen, dass wir, wenn wir bei einem Problem wie diesem von Wahrscheinlichkeiten sprechen, die Wahrscheinlichkeit meinen, die man angesichts der verfügbaren Informationen zuordnet. Für ein Mitglied der Mannschaft, das den Preis hinter, sagen wir, Tür Nr. 1 gelegt hat, ist die Wahrscheinlichkeit, dass sich der Preis hinter Tür Nr. 1 befindet, 100 % und die Wahrscheinlichkeit, dass er sich hinter einer der beiden anderen Türen befindet, ist Null.

Die Chancen des Besatzungsmitglieds unterscheiden sich von denen des Teilnehmers, weil er etwas weiß, was der Teilnehmer nicht weiß, nämlich, hinter welcher Tür er den Preis versteckt hat. Ebenso sind die Quoten des Teilnehmers anders als die des Zuschauers, weil er etwas weiß, was der Zuschauer nicht weiß, nämlich, welche Tür er ursprünglich gewählt hat. Dies ist jedoch nicht irrelevant, denn die Entscheidung des Gastgebers, welche Tür er öffnet, ist nicht zufällig. Er wird nicht die Tür öffnen, die der Teilnehmer gewählt hat, und er wird nicht die Tür öffnen, hinter der sich der Preis verbirgt. Wenn es sich um dieselbe Tür handelt, hat er zwei Möglichkeiten. Wenn es verschiedene Türen sind, 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 zu wählen. Ich denke, so viel ist klar. Das bedeutet, dass eine 2/3 Chance besteht, dass eine der anderen Türen der Gewinner ist. Wenn der Moderator ihm die Möglichkeit geben würde, die Tür zu tauschen, ohne zusätzliche Informationen zu geben, würde es keinen Gewinn geben. Auch dies sollte offensichtlich sein. Man kann es aber auch so sehen, dass es eine 2/3 Chance gibt, dass er durch einen Wechsel gewinnen würde. Aber er hat 2 Alternativen. Also hat jede von ihnen nur eine Chance von 2/3 geteilt durch 2 = 1/3, zu gewinnen, was nicht besser ist als seine ursprüngliche Wahl. Natürlich kannten wir das Endergebnis bereits, hier wird es nur anders berechnet.

Doch nun verrät der Gastgeber, dass eine der beiden Möglichkeiten nicht der Gewinner ist. Von den 2/3 Chancen, dass eine Tür, die er nicht ausgewählt hat, gewinnt, weiß er nun, dass eine der beiden Alternativen nicht die richtige ist. Die andere könnte es sein oder auch nicht. 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.

Answer 4

Nehmen wir an, Sie haben ein einfaches Münzwurfproblem, bei dem gerade als Kopf und ungerade als Zahl gilt. Die logische Umsetzung 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, dann sollte das gesamte Ergebnis gerade sein. Betrachten wir 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 in 75 % der Fälle gerade sein.

Ich würde an Ihrer Stelle auf Kopf setzen.

Dieser Kommentar ist eigentlich eher eine Erklärung, warum Sie keine benutzerdefinierte Zufallsfunktion auf der Grundlage Ihrer Methode implementieren sollten, als eine Diskussion über die mathematischen Eigenschaften des Zufalls.

Answer 5

Bei Zweifeln darüber, was mit den Kombinationen Ihrer Zufallszahlen geschehen wird, können Sie die Lektionen aus der statistischen Theorie anwenden.

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 der Uniform[0,1] verteilt ist. Wir verwenden die CDF-Technik, da es sich um eine Eins-zu-Eins-Abbildung handelt.

Da X ~ Uniform[0,1] ist, lautet seine cdf: f _X (x) = 1 Wir wollen die Transformation Y <- X^2 also y = x^2 Finde die Umkehrung x(y): sqrt(y) = x Dies gibt uns x als Funktion von y. Finden Sie nun 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 noch den Bereich von Y bestimmen. Da 0 <= x < 1, 0 <= x^2 < 1 also liegt Y im Bereich [0, 1). Wenn Sie prüfen wollen, ob die pdf von Y tatsächlich eine pdf ist, integrieren Sie sie über den Bereich: Integriere 1/(2 sqrt(y)) von 0 bis 1+from+0+to+1) und in der Tat erscheint sie als 1. Beachten Sie auch, dass die Form der besagten Funktion wie die von belisarious gepostete aussieht.

Was Dinge wie X betrifft ₁ + X ₂ + ... + X _n (wobei X _i ~ Uniform[0,1]) können wir uns einfach auf den zentralen Grenzwertsatz berufen, der für jede Verteilung gilt, deren Momente existieren. Das ist der Grund, warum es den Z-Test überhaupt gibt.

Andere Techniken zur Bestimmung der sich ergebenden pdf umfassen die Jacobi-Transformation (die die verallgemeinerte Version der cdf-Technik ist) und die MGF-Technik.

EDIT: Zur Klarstellung sei angemerkt, dass ich über die Vertrieb der resultierenden Transformation und nicht deren Zufälligkeit . Das ist eigentlich ein Thema für eine andere Diskussion. Außerdem habe ich eigentlich für (rand())^2 abgeleitet. Für rand() * rand() ist es viel komplizierter, was auf jeden Fall nicht zu einer gleichmäßigen Verteilung irgendeiner Art führen wird.