Frage "Zufälligkeit" verstehen


Ich kann das nicht verstehen, was zufälliger ist?

rand()

ODER

rand() * rand()

Ich finde es eine echte Denkaufgabe, könntest du mir helfen?

BEARBEITEN:

Intuitiv weiß ich, dass die mathematische Antwort sein wird, dass sie gleichermaßen zufällig sind, aber ich kann nicht anders als zu denken, dass, wenn Sie den Zufallszahlenalgorithmus zweimal ausführen, wenn Sie die zwei zusammen multiplizieren, Sie etwas zufälliger als nur tun es einmal.


822
2017-10-18 03:40


Ursprung


Antworten:


Nur eine Klarstellung

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

Beispiel

Das ist ein uniform Zufallsverteilung Probe simuliert durch eine Pseudozufallsvariable:

Histogram of Random() 

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

Während dies die Verteilung ist, die Sie erhalten, nachdem Sie zwei zufällige Variablen multipliziert haben:

Histogram of 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 * Zufall () ist gleichmäßig verteilt:

Histogram of 2 * Random()

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

Random () + Random () ist nicht!

Histogram of Random() + Random()

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

Der zentrale Grenzwertsatz

Das Zentraler Grenzwertsatz gibt an, dass die Summe von Zufällig() neigt zu a Normalverteilung wie Begriffe zunehmen.

Mit nur vier Begriffen erhalten Sie:

Histogram of 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 die Straße von einer Uniform zu einer Normalverteilung sehen, indem Sie 1, 2, 4, 6, 10 und 20 gleichmäßig verteilte Zufallsvariablen addieren:

Histogram of different numbers of random variables added

Bearbeiten

Ein paar Credits

Dank an Thomas Ahle in den Kommentaren darauf hinweisen, dass die Wahrscheinlichkeitsverteilungen in den letzten beiden Bildern als die bekannt sind Irwin-Hall-Verteilung 

Dank an Heike für sie wunderbar zerrissene [] Funktion


1464
2017-10-18 04:03



Ich denke beide Methoden sind so zufällig, obwohl mein Bauchgefühl das sagen würde rand() * rand() ist weniger zufällig, weil es mehr Nullen enthält. Sobald man rand() ist 0, wird die Summe 0 


151
2017-10-18 03:45



Weder ist "mehr zufällig".

rand() erzeugt eine vorhersagbare Menge von Zahlen basierend auf einem pseudozufälligen Startwert (normalerweise basierend auf der aktuellen Zeit, die sich immer ändert). Die Multiplikation zweier aufeinanderfolgender Zahlen in der Sequenz erzeugt eine andere, aber ebenso vorhersagbare Folge von Zahlen.

Wenn man anspricht, ob dadurch Kollisionen reduziert werden, lautet die Antwort nein. Es wird tatsächlich Kollisionen aufgrund der Wirkung der Multiplikation von zwei Zahlen erhöhen 0 < n < 1. Das Ergebnis wird ein kleinerer Bruchteil sein, was zu einer Verzerrung des Ergebnisses gegenüber dem unteren Ende des Spektrums führen wird.

Einige weitere Erklärungen. Im Folgenden beziehen sich "unvorhersehbar" und "zufällig" auf die Fähigkeit von jemandem, zu erraten, wie die nächste Zahl auf früheren Zahlen basiert, d. ein Orakel.

Gegebene Samen x welches die folgende Liste von Werten erzeugt:

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

rand() erzeugt die obige Liste und rand() * rand() wird erzeugen:

0.18, 0.08, 0.08, 0.21, ...

Beide Methoden werden immer die gleiche Liste von Zahlen für denselben Keim erzeugen und sind daher von einem Orakel gleichermaßen vorhersagbar. Aber wenn Sie sich die Ergebnisse für die Multiplikation der beiden Anrufe ansehen, werden Sie sehen, dass sie alle unter sind 0.3trotz einer anständigen Verteilung in der ursprünglichen Reihenfolge. Die Zahlen sind wegen des Effekts der Multiplikation zweier Fraktionen verzerrt. Die resultierende Zahl ist immer kleiner und daher viel wahrscheinlicher eine Kollision, obwohl sie immer noch genauso unberechenbar ist.


81
2017-10-20 22:43



Übersimplikation zur Veranschaulichung eines Punktes. 

Angenommen, Ihre Zufallsfunktion gibt nur aus 0 oder 1.

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

Sie können klar sehen, dass die Chancen, einen zu bekommen 0 im zweiten Fall sind sie nicht gleich denen, um ein zu bekommen 1.


Als ich diese Antwort zum ersten Mal gepostet habe, wollte ich sie so kurz wie möglich halten, so dass eine Person, die sie liest, den Unterschied zwischen ihnen auf einen Blick erkennen kann random() und random()*random(), aber ich kann mich nicht davon abhalten, die ursprüngliche Frage zu beantworten:

Was ist zufälliger?


78
2017-10-18 15:31



Hier ist eine einfache Antwort. Betrachte Monopoly. Sie würfeln zwei sechsseitige Würfel (oder 2D6 für diejenigen von Ihnen, die Spielnotation bevorzugen) und nehmen ihre Summe. Das häufigste Ergebnis ist 7, weil es 6 Möglichkeiten gibt, wie man eine 7 würfeln kann (1,6 2,5 3,4 4,3 5,2 und 6,1). Wohingegen eine 2 nur auf 1,1 gerollt werden kann. Es ist leicht zu sehen, dass das Rollen von 2W6 anders als das Rollen von WS12 ist, auch wenn die Reichweite die gleiche ist (ungeachtet dessen, dass man eine 1 auf 1W12 bekommen kann, bleibt der Punkt gleich). Wenn Sie Ihre Ergebnisse multiplizieren, anstatt sie hinzuzufügen, werden sie auf ähnliche Weise verzerrt, wobei die meisten Ihrer Ergebnisse in der Mitte liegen. Wenn Sie versuchen, Ausreißer zu reduzieren, ist dies eine gute Methode, aber es wird nicht helfen, eine gleichmäßige Verteilung zu erreichen.

(Und seltsamerweise erhöht es auch niedrige Würfe. Angenommen, Ihre Zufälligkeit beginnt bei 0, sehen Sie eine Spitze bei 0, weil sie sich dreht, was immer die andere Rolle in eine 0 ist. Betrachten Sie zwei Zufallszahlen zwischen 0 und 1 (inklusive Wenn eines der Ergebnisse eine 0 ist, wird das Ganze zu einer 0, unabhängig vom anderen Ergebnis, und die einzige Möglichkeit, eine 1 zu erhalten, besteht darin, dass beide Rollen eine 1 sind. In der Praxis wäre das wahrscheinlich egal aber es macht eine seltsame Grafik.)


67
2017-10-18 20:25



Das ist obligatorisch xkcd ...
return 4; // chosen by fair dice roll, guaranteed to be random.


51
2017-10-18 04:03



Es kann hilfreich sein, in diskreteren Zahlen darüber nachzudenken. Stellen Sie sich vor, Sie möchten Zufallszahlen zwischen 1 und 36 generieren, also entscheiden Sie, dass der einfachste Weg zwei faire, sechsseitige Würfel ist. 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 davon sind ziemlich dargestellt, und einige treten gar nicht auf. Zahlen in der Nähe der mittleren Diagonalen (untere linke Ecke bis obere rechte Ecke) werden mit der höchsten Häufigkeit auftreten.

Dieselben Prinzipien, die die ungerechte Verteilung zwischen Würfeln beschreiben, gelten auch für Gleitkommazahlen zwischen 0.0 und 1.0.


34
2017-10-18 03:45



Manche Dinge über "Zufälligkeit" sind kontraintuitiv.

Annahme einer flachen Verteilung von rand()Im Folgenden erhalten Sie nicht flache Verteilungen:

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

Es gibt viele andere Möglichkeiten, um spezielle Bias-Kurven zu erstellen. Ich habe einen schnellen Test gemacht rand() * rand()und es bekommt eine sehr nicht-lineare Verteilung.


26
2017-10-18 04:10



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

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

Ein echter RNG vom Krypto-Typ wird tatsächlich zufällig sein. Und das Ausführen von Werten durch irgendeine Art von Funktion kann nicht mehr Entropie hinzufügen und kann sehr wahrscheinlich die Entropie entfernen, so dass sie nicht zufälliger wird.


23
2017-10-18 19:01



Die meisten rand () Implementierungen haben einen gewissen Zeitraum. I.e. nach einer enormen Anzahl von Anrufen wiederholt sich die Sequenz. Die Reihenfolge der Ausgaben von rand() * rand() wiederholt sich in der Hälfte der Zeit, also ist es "weniger zufällig" in diesem Sinne.

Ohne sorgfältige Konstruktion führt das Ausführen von Arithmetik an zufälligen Werten dazu, weniger Zufälligkeit zu verursachen. Ein oben zitiertes Poster "rand() + rand() + rand() ... "(k mal, sagen wir), die tatsächlich zu k mal dem Mittelwert des Wertebereichs tendieren wird rand() kehrt zurück. (Es ist ein zufälliger Spaziergang mit Schritten symmetrisch zu diesem Mittelwert.)

Nehmen wir an, dass Ihre Funktion rand () eine gleichmäßig verteilte zufällige reelle Zahl im Bereich [0,1] liefert. (Ja, dieses Beispiel erlaubt unendliche Genauigkeit. Dies wird das Ergebnis nicht verändern.) Sie haben keine bestimmte Sprache gewählt und verschiedene Sprachen können verschiedene Dinge tun, aber die folgende Analyse gilt mit Modifikationen für jede nicht-perverse Implementierung von rand ( ). Das Produkt rand() * rand() liegt auch im Bereich [0,1], ist aber nicht mehr gleichmäßig verteilt. Tatsächlich liegt das Produkt wahrscheinlich im Intervall [0,1 / 4] wie im Intervall [1 / 4,1]. Mehr Multiplikation wird das Ergebnis noch weiter gegen Null verschieben. Dies macht das Ergebnis berechenbarer. In groben Zügen besser vorhersehbar == weniger zufällig.

So ziemlich jede Abfolge von Operationen bei einer gleichmßig zufälligen Eingabe wird ungleichmäßig zufällig sein, was zu einer erhöhten Vorhersagbarkeit führt. Mit Bedacht kann man diese Eigenschaft überwinden, aber dann wäre es einfacher gewesen, eine gleichmäßig verteilte Zufallszahl in dem Bereich zu erzeugen, den Sie eigentlich wollten, anstatt Zeit mit Arithmetik zu verschwenden.


23
2017-10-19 12:02