Gefälschte einheitliche Zufallszahlen: Gleichmäßiger verteilt als echte einheitliche Daten

43

Ich suche nach einer Möglichkeit, Zufallszahlen zu generieren , die gleichmäßig verteilt zu sein scheinen - und jeder Test zeigt, dass sie einheitlich sind - mit der Ausnahme, dass sie gleichmäßiger verteilt sind als echte einheitliche Daten .

Das Problem, das ich mit den "wahren" einheitlichen Zufällen habe, ist, dass sie sich gelegentlich zusammenballen. Dieser Effekt ist bei einer geringen Stichprobengröße stärker. Grob gesagt: Wenn ich in U [0; 1] zwei Gleichförmige Zufälle zeichne, liegt die Wahrscheinlichkeit bei 10%, dass sie in einem Bereich von 0,1 liegen, und bei 1%, dass sie in einem Bereich von 0,01 liegen.

Daher suche ich nach einer guten Möglichkeit, um Zufallszahlen zu generieren, die gleichmäßiger verteilt sind als gleichmäßige Zufälle .

Anwendungsbeispiel: Angenommen, ich mache ein Computerspiel und möchte einen Schatz nach dem Zufallsprinzip auf einer Karte platzieren (ohne Rücksicht auf irgendetwas anderes). Ich möchte nicht, dass der Schatz an einem Ort ist, er sollte überall auf der Karte sein. Wenn ich mit einheitlichen Zufällen beispielsweise 10 Objekte platziere, sind die Chancen nicht so gering, dass es 5 oder so nahe beieinander gibt. Dies kann einem Spieler einen Vorteil gegenüber einem anderen verschaffen. Denken Sie an Minensucher, die Chancen stehen gut, dass Sie wirklich Glück haben und mit einem Klick gewinnen.

Ein sehr naiver Ansatz für mein Problem besteht darin, die Daten in ein Raster aufzuteilen. Solange die Anzahl groß genug ist (und Faktoren hat), kann man auf diese Weise eine zusätzliche Gleichförmigkeit erzwingen. Anstatt also 12 Zufallsvariablen aus U [0; 1] zu ziehen, kann ich 6 aus U [0; 0,5] und 6 aus U [0,5; 1] oder 4 aus U [0; 1/3] + 4 ziehen von U [1/3; 2/3] + 4 von U [2/3; 1].

Gibt es eine bessere Möglichkeit, diese zusätzliche Gleichmäßigkeit in die Uniform zu bringen? Es funktioniert wahrscheinlich nur für Batch-Zufälle (beim Zeichnen eines einzelnen Zufalls muss ich natürlich den gesamten Bereich berücksichtigen). Insbesondere kann ich die Datensätze danach erneut mischen (es sind also nicht die ersten vier ab dem ersten Drittel).

Wie wäre es inkrementell? Also ist die erste auf U [0; 1], dann zwei von jeder Hälfte, eine von jeder dritten, eine von jeder vierten? Wurde dies untersucht und wie gut ist es? Möglicherweise muss ich vorsichtig sein, um unterschiedliche Generatoren für x und y zu verwenden, damit sie nicht korrelieren (das erste xy befindet sich immer in der unteren Hälfte, das zweite in der linken Hälfte und im unteren Drittel, das dritte im mittleren Drittel und im oberen Drittel. Es ist also zumindest eine zufällige Bin-Permutation erforderlich, und auf lange Sicht wird es wohl zu gleichmäßig sein.

Gibt es als Nebenknoten einen bekannten Test, ob eine Verteilung zu gleichmäßig ist, um wirklich gleichmäßig zu sein? Testen Sie also "echte Uniform" im Vergleich zu "jemand hat die Daten durcheinander gebracht und die Artikel gleichmäßiger verteilt". Wenn ich mich richtig erinnere, kann Hopkins Statistic dies messen, aber kann es auch zum Testen verwendet werden? Auch ein etwas inverser KS-Test: Liegt die größte Abweichung unter einem bestimmten erwarteten Schwellenwert, sind die Daten zu gleichmäßig verteilt?

Anony-Mousse
quelle
7
Hast du von Halton-Sequenzen gehört ? Für "zu gleichmäßig" haben die Leute (beginnend mit der Untersuchung von Mendels Erbsenversuchsergebnissen durch Fisher) die (übliche) Chi-Quadrat-Statistik auf den unteren Schwanz einer Chi-Quadrat-Verteilung bezogen.
Whuber
Eine Möglichkeit , dies zu formalisieren wäre eine Verteilung wollen , so dass (1) g ( ) marginalisiert zu 1 über x 1 , . . . , X n - 1 , (2) g symmetrisch ist, dh , X 1 , . . . , X n austauschbar sind, und (3) g ( x 1 , .G(X1,...,Xn)G()1X1,...,Xn-1GX1,...,Xn groß istwenn x 1 , . . . , x n sind dispergiert. Ich denke, es gibt ein echtes Problem mit (2) und (3), da unendliche austauschbare Sequenzen in R nicht negativ korreliert werden können. Je größer n wir verwenden möchten, desto weniger Abstoßung können wir erzwingen. Andererseitssollten wirfür großes n sowieso eine gute Streuung haben. G(X1,...,Xn)X1,...,XnRnn
Kerl
Halton-Sequenzen kommen dem Ansatz, an den ich gedacht habe, ziemlich nahe. Einschließlich des Überspringens der ersten Einträge, um das Korrelationsrisiko zu verringern. Ich habe auch darüber nachgedacht, für jedes Level eine zufällige Permission zu verwenden. Vielen Dank für diesen Hinweis, da ich hiermit nach ähnlichen Methoden suchen kann!
Anony-Mousse
wrt. Wieder Halton-Sequenzen. Ich muss sie nicht deterministisch haben, zumindest mit Ausnahme eines anfänglichen Samens. Ich sehe hier zwei Möglichkeiten. Ich kann eine zyklische Verschiebung um einen zufälligen Versatz + einen zufälligen Startversatz + eine Schrittgröße durchführen. Das Problem ist natürlich, dass der "Schatz", der zum Spielbeispiel verbleibt, auch nicht jedes Mal in den gleichen Positionen zueinander sein sollte. Oder ich könnte diesen Ansatz mit Uniform-from-Subintervall verwenden, den ich in meiner Frage hatte, um etwas "zufällige Drehung" hinzuzufügen. Sozusagen: Halton scheint mir wieder zu vorhersehbar und regelmäßig zu sein.
Anony-Mousse
3
en.wikipedia.org/wiki/Low-discrepancy_sequence oder mathworld.wolfram.com/QuasirandomSequence.html . Einige der gebräuchlichen Tests für einheitliche RNGs (wie die in den Diehard / Dieharder-Testbatterien) sind für solche Dinge empfindlich; Beispielsweise gibt es zu wenige "kleine Abstände" zwischen Punkten.
Glen_b

Antworten:

60

Ja , es gibt viele Möglichkeiten, eine Folge von Zahlen zu erzeugen, die gleichmäßiger verteilt sind als zufällige Uniformen. Tatsächlich gibt es ein ganzes Feld , das dieser Frage gewidmet ist. es ist das Rückgrat von Quasi-Monte Carlo (QMC). Im Folgenden finden Sie eine kurze Einführung in die absoluten Grundlagen.

Gleichmäßigkeit messen

Es gibt viele Möglichkeiten, dies zu tun, aber die gängigste Methode hat einen starken, intuitiven, geometrischen Geschmack. Angenommen, wir wollen Punkte x 1 , x 2 , ... , x n in [ 0 , 1 ] d für eine positive ganze Zahl d erzeugen . Definiere D n : = sup R RnX1,X2,,Xn[0,1]dd Wo R ein Rechteck ist [ a 1 , b 1 ] × × [ a d , b d ] in [ 0 , 1 ] d , so dass 0 a ib i1 , und R ist der Satz alle solchen Rechtecke . Der erste TermInnern des Moduls ist der „beobachtet“ Anteil der Punkte innerhalb R und die zweiten Term ist das Volumen der R , v o

Dn: =supRR|1nich=1n1(XichR)-vOl(R)|,
R[ein1,b1]××[eind,bd][0,1]d0einichbich1RRR .vOl(R)=ich(bich-einich)

Die Größe wird oft als Diskrepanz oder extreme Diskrepanz der Punktmenge ( x i ) bezeichnet . Intuitiv finden wir das "schlechteste" Rechteck R, in dem der Anteil der Punkte am stärksten von dem abweicht, was wir bei perfekter Gleichförmigkeit erwarten würden.Dn(Xich)R

Dies ist in der Praxis unhandlich und schwer zu berechnen. In den meisten Fällen ziehen es die Menschen zur Arbeit mit dem Stern Diskrepanz , Der einzige Unterschied ist die Menge A, über die das Supremum genommen wird. Es ist die Menge derverankertenRechtecke (am Ursprung), dh wo a 1 = a 2 = = a d = 0 .

Dn=supREIN|1nich=1n1(XichR)-vOl(R)|.
EINein1=ein2==eind=0

Lemma : für alle n , d . Beweis . Die linke Hand gebunden ist offensichtlich , da AR . Die rechte Schranke folgt, weil jedes R R über Vereinigungen, Schnittpunkte und Komplemente von nicht mehr als 2 d verankerten Rechtecken (dh in A ) zusammengesetzt werden kann.DnDn2dDnnd
EINRRR2dEIN

Wir sehen also, dass und D n in dem Sinne äquivalent sind, dass wenn einer so klein ist, wie n wächst, der andere es auch ist. Hier ist ein (Cartoon-) Bild, das Kandidatenrechtecke für jede Diskrepanz zeigt.DnDnn

Extrem- und Sternendifferenz

Beispiele für "gute" Sequenzen

Sequenzen mit nachweislich geringer Sterndiskrepanz werden häufig als Sequenzen mit geringer Diskrepanz bezeichnet .Dn

van der Corput . Dies ist vielleicht das einfachste Beispiel. Für werden die Van-der-Corput-Folgen gebildet, indem die ganze Zahl i binär erweitert wird und dann die Ziffern um den Dezimalpunkt "wiedergegeben" werden. Formal geschieht dies mit der Radikalumkehrfunktion in der Base b , ϕ b ( i ) = k = 0 a k b - k - 1d=1ichb wobei i = k = 0 a k b k und a k die Ziffern in derErweiterungder Basis b von i sind . Diese Funktion bildet auch die Basis für viele andere Sequenzen. Zum Beispiel ist 41 in der Binärdatei 101001, und so ist a 0 = 1 , a 1 = 0 , a 2 = 0 , a 3 = 1 , a 4 = 0

ϕb(ich)=k=0einkb-k-1,
ich=k=0einkbkeinkbich41101001a0=1a1=0a2=0a3=1a4=0und . Daher ist der Punkt 41. in der van der Corput Sequenz x 41 = φ 2 ( 41 ) = 0,100101a5=1 .X41=ϕ2(41)=0,100101(Basis 2)=37/64

Man beachte , dass , da das niedrigstwertige Bit der zwischen oszilliert 0 und 1 , die Punkte x i für ungerade i sind in [ 1 / 2 , 1 ) , wohingegen die Punkte x i für noch i sind in ( 0 , 1 / 2 ) .ich01Xichich[1/2,1)Xichich(0,1/2)

Halton-Sequenzen . Zu den beliebtesten klassischen Sequenzen mit geringer Diskrepanz gehören Erweiterungen der Van-der-Corput-Sequenz auf mehrere Dimensionen. Sei die j kleinste Primzahl. Dann ist der i- te Punkt x i der d- dimensionalen Halton-Sequenz x i = ( ϕ p 1 ( i ) , ϕ p 2 ( i ) , , ϕ p d ( i ) )pjjichXichd Für niedrige d funktionieren diese recht gut, haben aberProbleme in höheren Dimensionen.

Xich=(ϕp1(ich),ϕp2(ich),,ϕpd(ich)).
d

Halton-Sequenzen erfüllen . Sie sind auch deshalb schön, weil sie dahingehend erweiterbar sind, dass die Konstruktion der Punkte nicht von der Wahl der Länge der Sequenz n im Voraus abhängt .Dn=O(n-1(Logn)d)n

Hammersley-Sequenzen . Dies ist eine sehr einfache Modifikation der Halton-Sequenz. Wir verwenden stattdessen Vielleicht überraschend ist der Vorteil, dass sie eine bessere Sternendifferenz D n = O ( n - 1 ( log n ) d - 1 ) haben .

Xich=(ich/n,ϕp1(ich),ϕp2(ich),,ϕpd-1(ich)).
Dn=O(n-1(Logn)d-1)

Hier ist ein Beispiel für die Halton- und Hammersley-Sequenzen in zwei Dimensionen.

Halton und Hammersley

icheinkich0b-1

β1,,βd-1

Xich=(ich/n,{ichβ1/n},,{ichβd-1/n}),
{y}yβ

Gute und schlechte Gitter

(t,m,s)(t,m,s)bbt-m[0,1]sbtt(t,m,s)(t,m,s)(t,m,s)

Xich[0,1]dUU(0,1)X^ich={Xich+U}[0,1]d

Hier ist ein Beispiel, bei dem die blauen Punkte die ursprünglichen Punkte und die roten Punkte die gedrehten Punkte sind, die durch Linien verbunden sind (und gegebenenfalls umbrochen dargestellt sind).

Cranley Patterson

(uich)[0,1]d(Xich)s=3X1=(u1,u2,u3)X2=(u2,u3,u4) s1Dn(X1,,Xn)0(uich)Dn

s=2X2ich(0,1/2)×[1/2,1)X2ich-1[1/2,1)×(0,1/2)(0,1/2)×(0,1/2)s=2Dn1/4n

Standard Referenzen

Die Monographie von Niederreiter (1992) und der Text von Fang und Wang (1994) sind Orte, an denen man sich weiter auseinandersetzen kann.

Kardinal
quelle
4
Diese Antwort ist ausgezeichnet und ich wollte nur die Mühen würdigen, die Sie in sie gesteckt haben. Danke!
Anony-Mousse
1
Eine kleine Anschlussfrage. Halton-Sequenzen sehen gut aus, weil sie auch nicht zu regelmäßig erscheinen. Das Gittermaterial ist für mich viel zu regelmäßig, und auch die Hammersley-Sequenz scheint viele Objekte auf Linien durch den Ursprung zu haben. Was ist ein guter Weg, um ein Gleichgewicht zwischen echter Uniform und gefälschter Uniform zu kontrollieren? Nehmen Sie einfach 80% Beitrag von Halton + 20% zufällige Uniform?
Anony-Mousse
1
+ 10k und definitiv mit einem Rekordtief (87 !!!!) beantwortet! Oh, und ich mag diesen Beitrag sehr. Ich habe die Frage deswegen mit einem Lesezeichen versehen. Gut gemacht, Kardinal.
Makro
@Macro: Danke für so einen netten Kommentar! Du bist sehr nett. Ich denke, dass dieses 10-km-Ding für mich vorübergehend sein kann. Ich vermute, dass ich weit unter 10K fallen kann, sobald die Stimmen von Procrastinator zurückgenommen werden. Ich bin überrascht, dass das noch nicht passiert ist. Ich glaube, sie haben fast 3000 Stimmen auf dieser Seite abgegeben. Danke auch für die Veröffentlichung hier; irgendwie habe ich Anony-Mousses Folgefragen nie gesehen!
Kardinal
DD
3

Ein Weg, dies zu tun, wäre, einheitliche Zufallszahlen zu generieren, dann mit einer beliebigen Methode auf "Nähe" zu testen und dann zufällige Gegenstände zu löschen, die zu nahe bei anderen sind, und einen anderen Satz zufälliger Uniformen zu wählen, um diese auszugleichen.

Würde eine solche Verteilung jede Homogenitätsprüfung bestehen? Ich hoffe sicher nicht! Es ist nicht mehr gleichmäßig verteilt, es ist jetzt eine andere Verteilung.

Ein nicht intuitiver Aspekt der Wahrscheinlichkeit ist, dass der Zufall klumpig ist. Es gibt mehr zufällige Datenläufe, als die Leute vermuten. Ich glaube, Twerski hat einige Nachforschungen angestellt (er hat jedoch so viel Nachforschungen angestellt, dass es schwer fällt, sich daran zu erinnern).

Peter Flom - Wiedereinsetzung von Monica
quelle
2
Eines der (vielen) Probleme bei diesem Ansatz ist, dass es sehr schwierig ist, die resultierende Verteilung zu charakterisieren.
whuber
Das OP scheint sich am meisten mit kleinen Stichproben zu befassen. Dies würde bedeuten, dass er sich nicht um die gesamte Verteilung kümmern muss. Angenommen, Sie haben einen Satz von Koordinaten, Sie generieren einen weiteren und berechnen dann den euklidischen Abstand zu allen anderen. Wenn der kleinste Abstand unter einem Schwellenwert liegt, werfen Sie die Zahl heraus und generieren Sie eine neue. Ich denke, Peters Lösung funktioniert gut.
John
@whuber Er scheint nicht daran interessiert zu sein, obwohl ich mich irren könnte.
Peter Flom - Reinstate Monica
2
Lassen Sie mich meinen Einwand etwas klarer formulieren, Peter: Wenn Sie Pseudozufallswerte ad hoc entfernen und / oder anpassen, um eine gewünschte Eigenschaft, wie z alle wünschenswerten Eigenschaften. Könnten Sie uns zum Beispiel mit Ihrer Methode sogar sagen, was der erste Moment des resultierenden Prozesses sein würde? (Kannst du uns überhaupt versichern, dass die Intensität gleichmäßig ist?) Was ist mit dem zweiten Moment? In der Regel stellen diese die Mindestinformationen dar, die erforderlich sind, um die Sequenzen effektiv für Rückschlüsse zu verwenden.
whuber
2
OK, aber im Beispiel in der Frage möchte er einen Schatz auf einer Karte in einem Spiel platzieren. Das wird keine Schlussfolgerungen oder Momente oder ähnliches beinhalten. Ich gebe zu, dass meine Methode für viele Zwecke nicht gut ist, aber ich denke, sie passt zum Beispiel. Natürlich ist das Beispiel vielleicht nicht das, was er will ... Vielleicht will er etwas Formaleres, in diesem Fall sollten alle anderen Antworten geprüft werden.
Peter Flom - Wiedereinsetzung von Monica
3

Dies ist als ein "Hard-Core" -Poisson-Point-Prozess bekannt, der in den 1970er-Jahren von Brian Ripley so genannt wurde. Das heißt, Sie möchten, dass es zufällig ist, aber Sie möchten nicht, dass Punkte zu nahe beieinander liegen. Der "harte Kern" kann als Pufferzone betrachtet werden, um die andere Punkte nicht eindringen können.

Stellen Sie sich vor, Sie zeichnen die Position einiger Autos in einer Stadt auf - aber Sie zeichnen nur den Punkt in der nominalen Mitte des Autos auf. Während sie auf der Straße sind, können sich keine zwei Punktepaare annähern, da die Punkte durch den "harten Kern" der Karosserie geschützt werden - die mögliche Superposition in Parkhäusern werden wir ignorieren :-)

Es gibt Verfahren zum Generieren solcher Punktprozesse - eine Möglichkeit besteht darin, Punkte einheitlich zu generieren und zu nahe beieinander liegende Punkte zu entfernen!

Für einige Details zu solchen Prozessen wird zum Beispiel darauf verwiesen

Sean
quelle
2

p1N

In Bezug auf die inkrementelle Generierung suchen Sie im Wesentlichen eine Reihe mit einer moderat negativen Autokorrelation. Ich bin mir nicht sicher, wie ich das am besten machen soll, da ich nur sehr wenig Erfahrung mit Zeitreihen habe, aber ich vermute, dass es dafür bereits Algorithmen gibt.

p>(1-α)

gung - Wiedereinsetzung von Monica
quelle
1

[0,1]nf(X)e(1kichj|Xich-Xj|k)1kk<0

Ein einfacher Weg, solche Vektoren zu erzeugen, ist die Gibbs-Abtastung.

Neil G
quelle
Können Sie das näher erläutern? Gibbs-Abtastung scheint hier nicht zu helfen, da bedingte Verteilung = marginale Verteilung = gleichförmig? Oder ist Ihr Vorschlag, die vorherigen Proben zu verwenden, um "Löcher" in der Verteilung zu erzeugen, aus der Sie Proben entnehmen können?
Anony-Mousse
ichXichrf(X)r