Wie zu test auf Zufälligkeit (Fall in Punkt - Mischen)
https://stackoverflow.com/questions/56411
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
First off, diese Frage ist herausgerissen aus diese Frage.Ich Tat es, weil ich denke, dieser Teil ist größer als ein sub-Teil eines mehr in Frage zu stellen.Wenn es verletzt, bitte verzeihen Sie mir.
Angenommen, Sie haben einen Algorithmus, der Zufälligkeit erzeugt.Nun, wie können Sie es testen?Oder um genauer zu sein direkt Angenommen, Sie haben einen Algorithmus, der mischt die Karten, wie testen Sie, dass es eine vollkommen zufällige Algorithmus?
Fügen Sie einige Theorie der problem - Die Karten können gemischt werden in 52!(52 Fakultät) verschiedene Möglichkeiten.Nehmen Sie ein deck von Karten, mische es mit der hand und notieren Sie die Reihenfolge aller Karten.Was ist die Wahrscheinlichkeit, dass Sie es hätten genau das shuffle?Antwort:1 / 52!.
Was ist die chance, dass Sie, nach dem mischen, erhalten A, K, Q, J ...von jeder Farbe in eine Sequenz?Antwort 1 / 52!
Also, einfach einmal mischen und betrachten das Ergebnis wird Ihnen absolut keine Informationen über Ihre schlurfenden algorithmen Zufälligkeit.Zweimal-und haben Sie mehr Informationen, Drei-noch mehr...
Wie würdest du black-box-test-ein shuffling-Algorithmus für die Zufälligkeit?
Lösung
Statistiken. Der de-facto-Standard für die Prüfung RNGs ist die Diehard Suite (ursprünglich verfügbar unter http://stat.fsu.edu/pub/diehard ). Alternativ kann das Ent Programm Tests bietet, die einfacher zu interpretieren sind, aber weniger umfassend.
Als Algorithmen für schlurfend, mit einem bekannten Algorithmus wie Fisher-Yates ( aka "Knuth Shuffle"). Der Shuffle wird gleichmäßig zufällig sein, solange die zugrunde liegende RNG gleichmäßig zufällig ist. Wenn Sie Java verwenden, ist dieser Algorithmus in der Standardbibliothek zur Verfügung (siehe Collections.shuffle ).
Es wahrscheinlich nicht für die meisten Anwendungen keine Rolle, aber bewusst sein, dass die meisten RNGs keine ausreichenden Freiheitsgrade jede mögliche Permutation eines 52-Karten-Deck, um (erklärt hier ).
Andere Tipps
Hier ist eine einfache Prüfung, die Sie ausführen können. Es verwendet Zufallszahlen erzeugt Pi zu schätzen. Es ist kein Beweis für die Zufälligkeit, aber schlechte RNGs tun normalerweise nicht gut auf sie (sie wird so etwas wie 2,5 oder 3,8 eher ~ 3,14 zurück).
Im Idealfall würde dies nur eine von vielen Tests, die Sie laufen würden Zufälligkeit zu überprüfen.
Etwas anderes, das Sie überprüfen können, ist die Standardabweichung der Ausgabe. Die erwartete Standardabweichung für eine gleichmäßig verteilte Population von Werten im Bereich 0..n nähert n / sqrt (12).
/**
* This is a rudimentary check to ensure that the output of a given RNG
* is approximately uniformly distributed. If the RNG output is not
* uniformly distributed, this method will return a poor estimate for the
* value of pi.
* @param rng The RNG to test.
* @param iterations The number of random points to generate for use in the
* calculation. This value needs to be sufficiently large in order to
* produce a reasonably accurate result (assuming the RNG is uniform).
* Less than 10,000 is not particularly useful. 100,000 should be sufficient.
* @return An approximation of pi generated using the provided RNG.
*/
public static double calculateMonteCarloValueForPi(Random rng,
int iterations)
{
// Assumes a quadrant of a circle of radius 1, bounded by a box with
// sides of length 1. The area of the square is therefore 1 square unit
// and the area of the quadrant is (pi * r^2) / 4.
int totalInsideQuadrant = 0;
// Generate the specified number of random points and count how many fall
// within the quadrant and how many do not. We expect the number of points
// in the quadrant (expressed as a fraction of the total number of points)
// to be pi/4. Therefore pi = 4 * ratio.
for (int i = 0; i < iterations; i++)
{
double x = rng.nextDouble();
double y = rng.nextDouble();
if (isInQuadrant(x, y))
{
++totalInsideQuadrant;
}
}
// From these figures we can deduce an approximate value for Pi.
return 4 * ((double) totalInsideQuadrant / iterations);
}
/**
* Uses Pythagoras' theorem to determine whether the specified coordinates
* fall within the area of the quadrant of a circle of radius 1 that is
* centered on the origin.
* @param x The x-coordinate of the point (must be between 0 and 1).
* @param y The y-coordinate of the point (must be between 0 and 1).
* @return True if the point is within the quadrant, false otherwise.
*/
private static boolean isInQuadrant(double x, double y)
{
double distance = Math.sqrt((x * x) + (y * y));
return distance <= 1;
}
Erstens ist es unmöglich ist, sicher zu wissen, ob eine bestimmte endliche Ausgang „wirklich zufällig“ ist da, wie Sie darauf hinweisen, jeder Ausgang ist möglich .
Was getan werden kann, ist eine Folge von Ausgaben zu nehmen und verschiedene Messungen dieser Sequenz vor überprüfen, was wahrscheinlicher ist. Sie können eine Art von Vertrauen ableiten erzielen, dass der Erzeugungsalgorithmus, einen guten Job macht.
Zum Beispiel könnten Sie die Ausgabe von 10 verschiedenen schlurft überprüfen. Zuweisen eine Nummer 0-51, um jede Karte, und den Durchschnitt der Karte in Position 6 über die mischt. Der konvergente Durchschnitt 25,5, so dass Sie würden überrascht sein, einen Wert von 1 hier zu sehen. Sie könnten den zentralen Grenzwertsatz verwenden, um eine Schätzung zu bekommen, wie wahrscheinlich jeder Durchschnitt für eine bestimmte Position ist.
Aber wir sollten hier nicht stoppen! Da dieser Algorithmus könnte durch ein System täuschen, die nur zwischen zwei schlurft abwechselt, das den genauen durchschnittlich 25.5 an jeder Position zu geben, ist so konzipiert. Wie können wir besser machen?
Wir erwarten, dass eine gleichmäßige Verteilung (gleiche Wahrscheinlichkeit für eine gegebene Karte) an jeder Position, über verschiedene schlurft. So unter dem 10 schlurft, könnten wir versuchen, dass die Entscheidungen zu überprüfen ‚Look Uniform.‘ Dies ist im Grunde nur eine reduzierte Version des ursprünglichen Problems. Sie könnten prüfen, ob die Standardabweichung vernünftig aussieht, dass die min angemessen ist, und der Maximalwert als auch. Man könnte auch, dass andere Werte überprüfen, wie die nächsten zwei Karten (von unseren vergebenen Nummern), die auch Sinn machen.
Wir können aber auch nicht nur verschiedene Messungen wie diese ad infinitum hinzufügen, da genügend Statistiken gegeben, eine bestimmte Shuffle höchst unwahrscheinlich, aus irgendeinem Grund erscheint (zB das eines der wenigen schlurft, in dem Karten X, Y, Z erscheinen in dieser Reihenfolge). Die große Frage ist: welche das Recht der Messungen eingestellt ist zu nehmen? Hier muss ich zugeben, dass ich nicht weiß, die beste Antwort. Wenn Sie jedoch eine bestimmte Anwendung im Auge haben, können Sie einen guten Satz von Eigenschaften / Messungen wählen zu testen, und mit denen arbeiten -. Dies scheint die Art und Weise entcoders Dinge handhaben zu sein
Es gibt eine Menge Theorie auf Tests Zufälligkeit. Für einen sehr einfachen Test auf einer Karte Misch-Algorithmus könnte man viel schlurft zu tun und dann eine Chi-Quadrat-Test durchgeführt, dass die Wahrscheinlichkeit von jeder Karte in jeder Position Uniform war Aufdrehen. Aber das Testen nicht, dass aufeinanderfolgende Karten nicht korreliert sind, so würden Sie auch auf, dass die Tests machen wollen.
Volume 2 von Knuth Art of Computer Programming gibt eine Reihe von Tests, die Sie in den Abschnitten 3.3.2 (Empirische Tests) und 3.3.4 (Der Spectral Test) und die Theorie hinter ihnen nutzen könnten.
Mische viel, und dann die Ergebnisse aufzeichnen (wenn im dies richtig zu lesen). Ich erinnere mich, Vergleiche von „Zufallszahlengeneratoren“ zu sehen. Sie testen es einfach immer wieder, dann die Ergebnisse grafisch darzustellen.
Wenn es wirklich zufällig ist, wird der Graph meist sogar sein.
Der einzige Weg, auf Zufälligkeit zu testen ist, ein Programm zu schreiben, die ein Vorhersagemodell für die Daten zu bauen versucht, getestet, und dann dieses Modell verwenden, um zu versuchen, zukünftige Daten vorherzusagen, und zeigt dann, dass die Unsicherheit, oder Entropie, Vorhersagen ihrer neigen zu Maximum (dh der gleichmäßigen Verteilung) über die Zeit. Natürlich, werden Sie immer unsicher sein, ob Ihr Modell alle notwendigen Kontext erfasst hat; ein Modell gegeben, wird es immer möglich sein, ein zweites Modell zu bauen, die nicht-zufällige Daten erzeugt, die mit dem ersten Zufall aussehen. Aber solange man akzeptieren, dass die Umlaufbahn des Pluto auf den Ergebnissen des Misch-Algorithmus einen unwesentlichen Einfluss hat, dann sollten Sie in der Lage sein, sich zu vergewissern, dass die Ergebnisse sind in akzeptabler Weise zufällig.
Natürlich, wenn Sie dies tun, könnten Sie auch Ihr Modell verwenden generativ , um tatsächlich die Daten erstellen Sie wollen. Und wenn Sie das tun, dann bist du wieder auf Platz eins.
Ich bin nicht ganz nach Ihrer Frage. Sie sagen,
Angenommen, Sie einen Algorithmus haben, die Zufälligkeit erzeugt. Nun, wie testen Sie es?
Was meinst du damit? Wenn Sie vorausgesetzt, Sie Zufälligkeit erzeugen kann, gibt es keine Notwendigkeit, es zu testen.
Sobald Sie einen guten Zufallszahlengenerator haben, eine zufällige Permutation zu schaffen ist einfach (z Rufen Sie Ihre Karten 1-52. Generieren 52 Zufallszahl Zuordnen jeder auf eine Karte, um, und dann sortiert nach Ihrer 52 randoms). Du wirst nicht durch das Erzeugen Ihrer Permutation der Zufälligkeit Ihrer guten RNG zu zerstören.
Die schwierige Frage ist, ob Sie Ihre RNG vertrauen können. Hier einer Probe Link zu den Menschen, diese Frage in einem bestimmten diskutieren Kontext.
Testing 52! Möglichkeiten sind natürlich unmöglich. Stattdessen versuchen Sie Ihre Shuffle auf eine kleinere Anzahl von Karten, wie 3, 5 und 10. Dann können Sie Milliarden von Shuffles testen und ein Histogramm und die Chi-Quadrat-statistischen Test zu beweisen, verwenden, dass jede Permutation up kommt eine „even“ Nummer mal.
No Code so weit, also ich einen Testteil von meine Antwort auf die ursprüngliche Frage.
// ...
int main() {
typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
Map freqs;
Deck d;
const size_t ntests = 100000;
// compute frequencies of events: card at position
for (size_t i = 0; i < ntests; ++i) {
d.shuffle();
size_t pos = 0;
for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos)
++freqs[std::make_pair(pos, *j)];
}
// if Deck.shuffle() is correct then all frequencies must be similar
for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
std::cout << "pos=" << j->first.first << " card=" << j->first.second
<< " freq=" << j->second << std::endl;
}
Dieser Code testet nicht Zufälligkeit des zugrunde liegenden Pseudozufallszahlengenerators. PRNG Zufälligkeit Testen ist ein ganzer Zweig der Wissenschaft.
Für einen schnellen Test, können Sie immer versuchen, es zu komprimieren. Wenn es nicht komprimieren ist, dann kann man auf anderen Tests bewegen.
Ich habe versucht, dieharder aber es weigert sich, für einen Shuffle zu arbeiten. Alle Tests fehlschlagen. Es ist auch wirklich schwer verdaulich, es wird nicht Sie den Wertebereich lassen geben Sie wollen oder so etwas.
es selbst Erwägen, was ich tun würde, ist so etwas wie:
Setup (Pseudo-Code)
// A card has a Number 0-51 and a position 0-51
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values
ShuffleCards();
ForEach (card in Cards) {
StatMatrix[Card.Position][Card.Number]++;
}
Das gibt uns eine Matrix 52x52 angibt, wie oft eine Karte an einer bestimmten Position beendet hat. Wiederholen Sie diesen Vorgang eine große Anzahl von Zeiten (ich würde mit 1000 beginnen, aber die Menschen besser auf Statistiken als ich kann eine bessere Nummer geben).
Analyse der Matrix
Wenn wir perfekte Zufälligkeit haben und die Shuffle eine unendliche Anzahl von Zeiten führen Sie dann für jede Karte und für jede Position der Anzahl der Male der Karte in dieser Position am Ende ist die gleiche wie für jede andere Karte. Zu sagen, die gleiche Sache auf eine andere Weise:
statMatrix[position][card] / numberOfShuffle = 1/52.
So würde ich berechnen, wie weit von dieser Zahl sind wir.
