Was ist Zufälligkeit wirklich?

Ich bin Informatikstudent und derzeit im Kurs Systemsimulation & Modellierung eingeschrieben. Es geht darum, mit alltäglichen Systemen um uns herum umzugehen und sie in verschiedenen Szenarien zu simulieren, indem Zufallszahlen in verschiedenen Verteilungskurven wie zum Beispiel IID, Gauß usw. erzeugt werden. Ich habe am Boids-Projekt gearbeitet und mir ist gerade die Frage aufgefallen, was genau "zufällig" wirklich ist. Ich meine zum Beispiel, dass jede Zufallszahl, die wir generieren, auch in unseren Programmiersprachen wie über die Math.random()Methode in Java, im Wesentlichen nach einem "Algorithmus" generiert wird.

Woher wissen wir wirklich, dass eine Folge von Zahlen, die wir produzieren, tatsächlich zufällig ist, und würde es uns helfen, ein bestimmtes Modell so genau wie möglich zu simulieren?

Die kurze Antwort ist, dass niemand weiß, was echte Zufälligkeit ist oder ob so etwas existiert. Wenn Sie die Zufälligkeit eines diskreten Objekts quantifizieren oder messen möchten, wenden Sie sich normalerweise der Komplexität von Kolmogorov zu . Vor der Komplexität von Kolmogorov hatten wir keine Möglichkeit, die Zufälligkeit einer Zahlenfolge zu quantifizieren, ohne den Prozess zu berücksichtigen, der sie hervorgebracht hat.

Hier ist ein intuitives Beispiel, das die Leute damals wirklich nervte. Betrachten Sie eine Folge von Münzwürfen. Das Ergebnis eines Wurfs ist entweder Kopf ( ) oder Zahl ( ). Nehmen wir an, wir machen zwei Experimente, bei denen wir 10 Mal eine Münze werfen. Das erste Experiment gibt uns . Das zweite Experiment gibt uns . Nachdem Sie das Ergebnis gesehen haben, könnten Sie versucht sein, zu behaupten, dass etwas mit der Münze in stimmt , oder zumindest aus irgendeinem seltsamen Grund, dass das, was Sie erhalten haben, nicht zufällig ist. Wenn Sie jedoch annehmen, dass sowohl als auch wahrscheinlich sind (die Münze ist fair), ist die Wahrscheinlichkeit, dass Sie eines von beiden erhalten, gleich$H$$T$$E_1$$H,H,H,H,H,H,H,H,H,H$$E_2$$T,T,H,T,H,T,T,H,T,H$$E_1$$H$$T$$E_1$ oder ist gleich . In der Tat ist das Erhalten einer bestimmten Sequenz so wahrscheinlich wie jede andere! Dennoch fühlt sich zufällig an und nicht.$E_2$$(1/2)^{10}$$E_2$ $E_1$

Da die Kolmogorov-Komplexität nicht berechenbar ist, kann man im Allgemeinen nicht berechnen, wie zufällig eine Folge von Zahlen ist, unabhängig davon, welche Art von behauptetem "völlig zufälligem" Prozess sie hervorgebracht hat.

Im Fall von Java (oder ähnlichen Sprachen) kennen wir den Algorithmus, der zum Erstellen der Zufallszahlen verwendet wird. Wenn es mit einem einzelnen Startwert beginnt, sind die Zahlen überhaupt nicht zufällig, dh wenn wir in einer Folge a 0 , … , a n kennen , kennen wir ein i + 1 , oder als bedingte Wahrscheinlichkeit angegeben: ∀ k , l , i : P ( a i + 1 = k ≤ a i = l ) ≤ { 0 $a_i$$a_0,\dots,a_n$$a_{i+1}$

Trotzdem können diese Reihen Eigenschaften erfüllen (siehe zB WP: Autokorrelation ), die Zufallszahlen erfüllen, und diese Eigenschaften reichen oft aus, um Aufgaben zu erfüllen, bei denen wir "echte" (zB durch einen physikalischen Prozess erzeugte) Zufallszahlen verwenden möchten, können aber t bemühe sie.

Es ist unmöglich sicher zu wissen, ob eine bestimmte Sequenz zufällig ist oder nicht. Sie können jedoch Merkmale (oder Parameter) einer Sequenz betrachten und die Wahrscheinlichkeit einer solchen Sequenz bei gegebener Interessensverteilung berechnen.

Wenn Sie mit Ihrem Zufallsgenerator eine unendlich lange Sequenz erzeugen könnten, sollte diese dieselben Parameter wie die Zufallsverteilung haben. Wenn Sie beispielsweise die Standard-Gauß-Verteilung , sollte sich Ihre Sequenz dem Mittelwert von 0 und der Standardabweichung von 1 nähern . Eine vorläufige Möglichkeit, Ihren Generator zu überprüfen, besteht darin, eine wirklich lange Sequenz zu generieren und zu überprüfen, ob sie sich der gewünschten Zufallsverteilung annähert.$(\mu=0,\sigma=1)$$1$

Sie können weitere Momente der Verteilung (z. B. die Schiefe) hinzufügen, die für die weitere Validierung von Interesse sind. Bei IID-Zahlen können Sie auch versuchen, einen Algorithmus für maschinelles Lernen zu trainieren, um bevorstehende Elemente der Sequenz vorherzusagen, und dann auf die Nullhypothese testen, dass der Verlauf die Leistung verbessert. Keine dieser Methoden kann jedoch beweisen, dass eine Sequenz wirklich zufällig ist und kann bestenfalls erkennen, wenn Sequenzen NICHT zufällig sind (bis zu einem gewissen Grad an Sicherheit).

Die moderne Theorie der rechnerischen Antwort lautet: "Eine Zufallsquelle ist eine Quelle, die für Ihre Lieblingsklasse von Algorithmen zufällig aussieht." Dies ist eine utilitaristische Perspektive: Wenn eine Zufallsquelle für alle Algorithmen, die Sie interessieren, wie echte Zufälligkeit aussieht, ist nichts anderes von Bedeutung. Sie können Ihre Algorithmen analysieren, als ob sie wirklich zufällige Münzwürfe erhalten, und Ihre Analyse gibt die richtigen Antworten.

$\mathcal{A}$$\mathcal{A}$

• Alle Turingmaschinen, die immer anhalten
• alle Polynomgrößenschaltungsfamilien
• alle Polynomzeit Turingmaschinen
• alle logspace Turingmaschinen

$\mathcal{A}$$(X_n)$$X_n$$\{0, 1\}^n$$\epsilon$$\mathcal{A}$$A \in \mathcal{A}$

Diese Idee steht hinter jeder modernen formalen Vorstellung von Pseudozufälligkeit.

Hier sind noch zwei Cent.

Eine Möglichkeit, sich randomisierte Algorithmen vorzustellen, besteht darin, sich eine Box vorzustellen, die Eingaben nimmt, mysteriöse Dinge mit diesen Eingaben ausführt und eine ("unvorhersehbare") Ausgabe erzeugt.

Stattdessen kann es hilfreich sein, sie als deterministische Algorithmen zu betrachten, die zwei Eingaben annehmen: die "wahre" Eingabe und einige "zufällige" Eingaben, die wir von Funktionen wie erhalten Math.Random().

$[0,1]$$n \log n$

$[0,1]$$n \log n$

Wie Jonathan und Frafl erwähnen, gibt es Möglichkeiten zu überprüfen, ob sich eine zufällige Quelle "zufällig" verhält. Aber alles, was sie tun werden, ist zu beeinflussen, was Sie über zukünftige Informationen glauben, die aus dieser zufälligen Quelle stammen. Wenn Sie der Meinung sind, dass jedes Bit unabhängig von den vorherigen Bits gleich wahrscheinlich null oder eins ist, dann ist diese Quelle nach bestem Wissen und Gewissen einheitlich und unabhängig zufällig und daher nach bestem Wissen und Gewissen. es wird schnell laufen oder richtig sein oder so weiter. Das ist jedenfalls meine philosophische Einstellung.

Wir können keine wirklich zufälligen Zahlen erzeugen. Es gibt verschiedene Methoden zur Erzeugung von Pseudozufallszahlen unter Verwendung einer angegebenen Gleichung und eines bestimmten Startwerts. Die zufällige Reihenfolge der Zahlen hängt also vom Startwert ab. Sobald wir den Startwert kennen, können wir vorhersagen, wie die Sequenz aussehen wird. Abgesehen davon gibt es andere Methoden zur Erzeugung von Zufallszahlen. Die Leute verwenden jetzt einige Methoden, um echte Zufallszahlen zu generieren, wie die Verwendung der Bewegungszeit des Plattenkopfs und andere physikalische Methoden, die in einen Computer integriert werden können. Siehe: http://en.wikipedia.org/wiki/Random_number_generation#Generation_methods

durch die gegebene Methode, wie Sie sagten,
Math.random () in Java
Randomize; Zufällig (n); in Delphi

Sie können Ihre eigene Struktur und Logik implementieren, um Zufallszahlen zu generieren,
wobei ein solcher "Algorithmus" anhand Ihrer vorgegebenen Spezifikationen für bessere Zufallsergebnisse ausgeführt werden kann.
und baue darauf die Logik auf.

Vielen Dank.

Andere Antworten sind gut, hier sind einige andere Gesichtspunkte zu dieser sehr wichtigen / ungewollt tiefen Frage. Informatiker beschäftigen sich seit Jahrzehnten mit Zufälligkeiten und werden diese wahrscheinlich auch weiterhin untersuchen. Es hat viele tiefe Verbindungen und vor allem offene Fragen, die auf dem gesamten Gebiet noch offen sind. hier sind ein paar hinweise.

• "echte / reale Zufälligkeit" tritt bei physikalischen Prozessen auf niedriger Ebene und "Rauschen" auf, wie in Zenerdioden, Quantenmechanik usw., die in hardwarebasierten RNGs genutzt werden können

• andere im Computerraum erzeugte Zahlen sind sogenannte "Pseudozufälle", die simuliert werden und niemals mit "wahrer Zufälligkeit" übereinstimmen können. Dies sind sogenannte PRNGs

• Es gibt ein wichtiges Gefühl der "kryptografischen Härte von Zufallszahlengeneratoren", das in gewissem Sinne ihre "Qualität" oder "Sicherheit" misst, siehe z . B. kryptografisch sicheres PRNG . Grundsätzlich hat ein "schwacher" Generator nicht so viel Rechenaufwand wie ein "harter" Generator und ein "schwacher" Generator ist leichter zu brechen.

• $O(n)$$O(n^2)$$\stackrel{?}{=}$$\neq$NP-Beweise müssen eine gewisse "Komplexität" aufweisen, sonst könnte dieselbe Analysetechnik zum Aufbrechen von PRNGs verwendet werden, und darüber hinaus tun es die meisten oder vielleicht alle zu diesem Zeitpunkt (oder möglicherweise sogar danach ) bekannten Trennungen / Techniken für Komplexitätsklassen nicht über ausreichende Komplexität verfügen.

• Ein wichtiges Forschungsthema in TCS sind randomisierte und derandomisierte Algorithmen . Die Idee besteht grob darin, zu untersuchen, wie stark sich der Algorithmus verändert, indem "echte Zufälligkeit" durch ein PRNG ersetzt wird, und es gibt verschiedene tiefe Theoreme zu diesem Thema. Hier ist eine hochrangige cstheory.se-Frage, die einen gewissen Einblick in die Forschung in diesem Bereich gibt: effiziente und einfache randomisierte Algorithmen, bei denen Determinismus schwierig ist

• ein weiteres wichtiges verwandtes Thema in TCS ist eine Information Entropie - ursprünglich in eingeführte Physik lange AGO , die ein eng verwandtes Konzept der „Informations dis Ordnung“ und wie einige anderen wichtigen Konzepte in (T) CS Studien scheint eine der wichtigsten Ideen sein , dass Ablängschnitte die Grenze zwischen angewandter und theoretischer Analyse, auch einige der Formeln sind gleich .

• Ein weiteres Indiz für den Status aktiver Forschung sind andere hochrangige Fragen auf cstheory.se, die sich auf diese Frage beziehen. hier ist einer nah dran, fast derselbe: Ist ein wahrer Zufallsgenerator für Turing berechenbar