dqsample: Eine faire Alternative zu ‚base::sample‘

Das Erzeugen von zufälligen Stichproben eines Datensatzes wird in der Statistik oder Data Science oft angewendet. Für diese Aufgabe gibt es in R die Funktion base::sample. Leider ist der dabei verwendete Algorithmus nicht vollständig fair. Dies wurde zuletzt auf R-devel diskutiert, was auch die Motivation für das dqsample Paket darstellt. Derzeit ist dqsample nicht auf CRAN, kann aber über drat installiert werden:

Beispiel

Wählt man viele Zahlen zufällig aus, so sollten die Dichten der geraden und ungerade Zahlen in etwa gleich und konstant sein. Mit base::sample ist dies jedoch nicht er Fall:

plot of chunk base

Oder mit verändertem Parameter:

plot of chunk base-oszi

Dieses spezielle Beispiel stammt von Duncan Murdoch.

Daniel Lemire (2018, <arXiv:1805.1094>) hat einen alternativen Algorithmus vorgeschlagen, der in dqsample verwendet wird. Mit diesem Algorithmus gibt es keine Asymmetrie zwischen geraden und ungeraden Zahlen:

plot of chunk dqsample

Ursachenforschung

Intern benötigt die base::sample() Funktion zufällige ganze Zahlen die gleichmäßig in dem halb-offenen Bereich [0, n) verteilt sind.Um diese zu erzeugen, verwendet R zufällige Gleitkommazahlen aus [0, 1), multipliziert mit n und schneidet den Nachkommateil ab. Mit reellen Zahlen im mathematischen Sinn wäre das korrekt. Aber das ist hier nicht der Fall.

Standardmäßig verwendet R einen 32 bit Mersenne-Twister zum Erzeugen von Zufallszahlen. Dieser erzeugt ganze Zahlen aus [0, 2^32), die durch 2^32geteilt werden um Gleitkommazahlen aus [0, 1) zu erhalten.Wenn wir das oben beschriebene Verfahren invertieren, so können wir sehen wie viele mögliche Zufallszahlen zu einem Ergebnis gehören.  Mit sample(6, 10, replace = TRUE) kann man zum Beispiel den Wurf von zehn Würfeln simulieren. Da 2^32 kein Vielfaches von sechs ist, kann die Verteilung aber nicht gleichverteilt sein:

Eins und vier haben eine minimal geringere Wahrscheinlichkeit als die übrigen Zahlen. Dieser Effekt steigt mit der Größe des Datensatzes, aus dem gewählt wird. Verwenden wir das oben definierte m so können wir sehen, woher die ungleiche Verteilung gerader und ungerader Zahlen herkommt:

Während jeweils zwei Zahlen auf eine der ungeraden Zahlen abgebildet werden, sind es drei Zahlen für jede gerade Zahl. Dieses Muster verschiebt sich bei der Hälfte der möglichen Ergebnisse, was das erste Bild oben erklärt. Das Muster verschiebt sich öfter, wenn man sich von m entfernt, was die Oszillationen im zweiten Bild erklärt. Irgendwann werden die Oszillationen zu schnell, um sie in der Dichte sehen zu können. Das bedeutet aber nicht, dass die Verteilung fair ist. Für m - 2^20verschiebt sich das Muster beispielsweise zwischen 982 und 983:

Vorher sind gerade Zahlen wahrscheinlicher als ungerade Zahlen. Danach ist es umgekehrt.

Zusammenfassung

Der von base::sample verwendet Algorithmus ist nicht fair, was zusammen mit großen Datenmengen einen merkbaren Effekt haben kann. Das dqsample Paket stellt für die wichtigsten Anwendungsfälle einen fairen Algorithmus bereit. Es kann als direkter Ersatz für base::sample verwendet werden.