Warum hat dieser Zufallswert eine Verteilung von 25/75 anstelle von 50/50?

139

Bearbeiten: Also im Grunde ist das, was ich zu schreiben versuche, ein 1-Bit-Hash für double.

Ich möchte eine doublezu trueoder falsemit einer 50/50-Chance zuordnen. Dafür habe ich Code geschrieben, der einige Zufallszahlen auswählt (nur als Beispiel möchte ich dies für Daten mit Regelmäßigkeiten verwenden und trotzdem ein 50/50-Ergebnis erhalten) , ihr letztes Bit überprüft und inkrementiert, yob es 1 ist oder nob es ist 0.

Dieser Code führt jedoch ständig zu 25% yund 75% n. Warum ist es nicht 50/50? Und warum so eine seltsame, aber unkomplizierte (1/3) Verteilung?

public class DoubleToBoolean {
    @Test
    public void test() {

        int y = 0;
        int n = 0;
        Random r = new Random();
        for (int i = 0; i < 1000000; i++) {
            double randomValue = r.nextDouble();
            long lastBit = Double.doubleToLongBits(randomValue) & 1;
            if (lastBit == 1) {
                y++;
            } else {
                n++;
            }
        }
        System.out.println(y + " " + n);
    }
}

Beispielausgabe:

250167 749833
gvlasov
quelle
43
Ich hoffe wirklich, dass die Antwort etwas Faszinierendes an der zufälligen Erzeugung von Gleitkommavariablen ist und nicht "LCG hat eine niedrige Entropie in den niedrigen Bits".
Sneftel
4
Ich bin sehr neugierig, was ist der Zweck eines "1-Bit-Hash für Double"? Ich kann mir ernsthaft keine legitime Anwendung einer solchen Anforderung vorstellen.
CorsiKa
3
@corsiKa Bei Geometrieberechnungen gibt es oft zwei Fälle, nach denen wir suchen, um aus zwei möglichen Antworten zu wählen (z. B. Punkt links oder rechts von der Linie?), und manchmal wird der dritte, entartete Fall eingeführt (Punkt ist direkt in der Zeile), aber Sie haben nur zwei verfügbare Antworten, so dass Sie in diesem Fall pseudozufällig eine der verfügbaren Antworten auswählen müssen. Der beste Weg, den ich mir vorstellen kann, ist, einen 1-Bit-Hash von einem der angegebenen Doppelwerte zu nehmen (denken Sie daran, das sind Geometrieberechnungen, also gibt es überall Doppelwerte).
Gvlasov
2
@corsiKa (Kommentar zweigeteilt, weil er zu lang ist) Wir könnten mit etwas Einfacherem beginnen doubleValue % 1 > 0.5, aber das wäre zu grobkörnig, da es in einigen Fällen sichtbare Regelmäßigkeiten einführen kann (alle Werte liegen im Bereich der Länge 1). Wenn das zu grobkörnig ist, sollten wir dann wahrscheinlich kleinere Bereiche ausprobieren, wie z doubleValue % 1e-10 > 0.5e-10. Nun ja. Und nur das letzte Bit als Hash von a zu nehmen, doublepassiert, wenn Sie diesem Ansatz bis zum Ende mit dem geringstmöglichen Modulo folgen.
Gvlasov
1
@kmote dann hätten Sie immer noch das stark voreingenommene niedrigstwertige Bit, und das andere Bit kompensiert es nicht - tatsächlich ist es aus genau dem gleichen Grund auch gegen Null voreingenommen (aber weniger). Die Verteilung wäre also ungefähr 50, 12,5, 25, 12,5. (lastbit & 3) == 0würde aber funktionieren, seltsam wie es ist.
Harold

Antworten:

165

Weil nextDouble so funktioniert: ( Quelle )

public double nextDouble()
{
    return (((long) next(26) << 27) + next(27)) / (double) (1L << 53);
}

next(x)macht xzufällige Bits.

Warum ist das wichtig? Weil ungefähr die Hälfte der vom ersten Teil (vor der Division) erzeugten Zahlen kleiner als 1L << 52ist und daher ihr Signifikand die 53 Bits, die er füllen könnte, nicht vollständig ausfüllt, was bedeutet, dass das niedrigstwertige Bit des Signifikanten für diese immer Null ist.


Aufgrund der Aufmerksamkeit, die dies erhält, finden Sie hier eine zusätzliche Erklärung, wie ein doublein Java (und vielen anderen Sprachen) wirklich aussieht und warum es in dieser Frage wichtig ist.

Grundsätzlich doublesieht a so aus: ( Quelle )

doppeltes Layout

Ein sehr wichtiges Detail, das in diesem Bild nicht sichtbar ist, ist, dass Zahlen 1 "normalisiert" werden, so dass der 53-Bit-Bruch mit einer 1 beginnt (indem der Exponent so gewählt wird, dass es so ist), dass 1 dann weggelassen wird. Aus diesem Grund zeigt das Bild 52 Bit für den Bruch (Signifikand), aber es enthält effektiv 53 Bit.

Die Normalisierung bedeutet, dass, wenn im Code für nextDoubledas 53. Bit gesetzt ist, dieses Bit die implizite führende 1 ist und weggeht und die anderen 52 Bits buchstäblich auf den Signifikanten des Ergebnisses kopiert werden double. Wenn dieses Bit jedoch nicht gesetzt ist, müssen die verbleibenden Bits nach links verschoben werden, bis es gesetzt wird.

Im Durchschnitt fällt die Hälfte der generierten Zahlen in den Fall, in dem der Signifikand überhaupt nicht nach links verschoben wurde (und etwa die Hälfte davon hat eine 0 als niedrigstwertiges Bit), und die andere Hälfte ist um mindestens 1 verschoben (oder ist nur vollständig Null), so dass ihr niedrigstwertiges Bit immer 0 ist.

1: nicht immer, klar, es kann nicht für Null gemacht werden, die keine höchste 1 hat. Diese Zahlen werden als denormale oder subnormale Zahlen bezeichnet, siehe Wikipedia: denormale Zahl .

Harold
quelle
16
Hurra! Genau das, was ich mir erhofft hatte.
Sneftel
3
@Matt Vermutlich handelt es sich um eine Geschwindigkeitsoptimierung. Die Alternative wäre, den Exponenten mit einer geometrischen Verteilung und dann die Mantisse separat zu erzeugen.
Sneftel
7
@Matt: Definieren Sie "am besten". random.nextDouble()ist normalerweise der "beste" Weg für das, wofür es gedacht ist, aber die meisten Leute versuchen nicht, einen 1-Bit-Hash aus ihrem zufälligen Double zu erzeugen. Suchen Sie eine gleichmäßige Verteilung, Resistenz gegen Kryptoanalyse oder was?
StriplingWarrior
1
Diese Antwort legt nahe, dass es eine 50/50-Verteilung gegeben hätte, wenn OP die Zufallszahl mit 2 ^ 53 multipliziert und überprüft hätte, ob die resultierende Ganzzahl ungerade war.
Rici
4
@ The111 hier steht, dass ein zurückgegeben werden nextmuss int, so dass es sowieso nur bis zu 32 Bit haben kann
Harold
48

Aus den Dokumenten :

Die Methode nextDouble wird von der Klasse Random wie folgt implementiert:

public double nextDouble() {
  return (((long)next(26) << 27) + next(27))
      / (double)(1L << 53);
}

Es heißt aber auch Folgendes (Hervorhebung von mir):

[In früheren Versionen von Java wurde das Ergebnis falsch berechnet als:

 return (((long)next(27) << 27) + next(27))
     / (double)(1L << 54);

Dies mag äquivalent erscheinen, wenn nicht sogar besser, aber tatsächlich führte es aufgrund der Verzerrung bei der Rundung von Gleitkommazahlen zu einer großen Ungleichmäßigkeit: Es war dreimal so wahrscheinlich, dass das niederwertige Bit des Signifikanten 0 sein würde als das wäre es 1 ! Diese Ungleichmäßigkeit spielt in der Praxis wahrscheinlich keine große Rolle, aber wir streben nach Perfektion.]

Dieser Hinweis ist mindestens seit Java 5 vorhanden (Dokumente für Java <= 1.4 befinden sich hinter einer Loginwall, zu faul zum Überprüfen). Dies ist interessant, da das Problem anscheinend auch in Java 8 noch besteht. Vielleicht wurde die "feste" Version nie getestet?

Thomas
quelle
4
Seltsam. Ich habe dies gerade auf Java 8 reproduziert.
aioobe
1
Das ist interessant, weil ich gerade argumentiert habe, dass die Tendenz immer noch für die neue Methode gilt. Liege ich falsch?
Harold
3
@harold: Nein, ich denke du hast recht und wer auch immer versucht hat, diese Tendenz zu beheben, könnte einen Fehler gemacht haben.
Thomas
6
@harold Zeit, eine E-Mail an die Java-Leute zu senden.
Daniel
8
"Vielleicht wurde die feste Version nie getestet?" Beim erneuten Lesen denke ich, dass es in dem Dokument um ein anderes Problem ging. Beachten Sie, dass die Rundung erwähnt wird , was darauf hindeutet, dass das "dreimal so wahrscheinlich" nicht direkt als Problem angesehen wurde, sondern dass dies zu einer ungleichmäßigen Verteilung führt, wenn die Werte gerundet werden . Beachten Sie, dass in meiner Antwort die von mir aufgelisteten Werte gleichmäßig verteilt sind, das im IEEE-Format dargestellte Bit niedriger Ordnung jedoch nicht einheitlich ist. Ich denke, das Problem, das sie behoben haben, hatte mit der Gesamtgleichmäßigkeit zu tun, nicht mit der Gleichmäßigkeit des niedrigen Bits.
Ajb
33

Dieses Ergebnis überrascht mich nicht, wenn man bedenkt, wie Gleitkommazahlen dargestellt werden. Nehmen wir an, wir hatten einen sehr kurzen Gleitkommatyp mit nur 4 Bit Genauigkeit. Wenn wir eine gleichmäßig verteilte Zufallszahl zwischen 0 und 1 erzeugen würden, gäbe es 16 mögliche Werte:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Wenn sie in der Maschine so aussahen, könnten Sie das Bit niedriger Ordnung testen, um eine 50/50-Verteilung zu erhalten. IEEE-Floats werden jedoch als Potenz von 2 mal einer Mantisse dargestellt; Ein Feld im Float ist die Potenz von 2 (plus einem festen Versatz). Die Potenz von 2 wird so gewählt, dass der "Mantissen" -Teil immer eine Zahl> = 1,0 und <2,0 ist. Dies bedeutet, dass die anderen Zahlen als 0.0000die folgenden dargestellt werden:

0.0001 = 2^(-4) x 1.000
0.0010 = 2^(-3) x 1.000
0.0011 = 2^(-3) x 1.100
0.0100 = 2^(-2) x 1.000
... 
0.0111 = 2^(-2) x 1.110
0.1000 = 2^(-1) x 1.000
0.1001 = 2^(-1) x 1.001
...
0.1110 = 2^(-1) x 1.110
0.1111 = 2^(-1) x 1.111

(Der 1Wert vor dem Binärpunkt ist ein impliziter Wert. Bei 32- und 64-Bit-Floats wird tatsächlich kein Bit zugewiesen, um diesen Wert zu speichern 1.)

Ein Blick auf das Obige sollte jedoch zeigen, warum Sie in 75% der Fälle Null erhalten, wenn Sie die Darstellung in Bits konvertieren und das niedrige Bit betrachten. Dies ist darauf zurückzuführen, dass alle Werte unter 0,5 (binär 0.1000), was der Hälfte der möglichen Werte entspricht, ihre Mantissen verschoben haben und 0 im niedrigen Bit erscheinen. Die Situation ist im Wesentlichen dieselbe, wenn die Mantisse 52 Bits (ohne die implizierte 1) doublehat.

(Wie @sneftel in einem Kommentar vorgeschlagen hat, könnten wir mehr als 16 mögliche Werte in die Verteilung aufnehmen, indem wir Folgendes generieren:

0.0001000 with probability 1/128
0.0001001 with probability 1/128
...
0.0001111 with probability 1/128
0.001000  with probability 1/64
0.001001  with probability 1/64
...
0.01111   with probability 1/32 
0.1000    with probability 1/16
0.1001    with probability 1/16
...
0.1110    with probability 1/16
0.1111    with probability 1/16

Aber ich bin mir nicht sicher, ob es die Art von Distribution ist, die die meisten Programmierer erwarten würden, also lohnt es sich wahrscheinlich nicht. Außerdem bringt es Ihnen nicht viel, wenn die Werte zur Erzeugung von Ganzzahlen verwendet werden, wie dies häufig bei zufälligen Gleitkommawerten der Fall ist.)

ajb
quelle
5
Die Verwendung von Gleitkomma, um zufällige Bits / Bytes / irgendetwas zu erhalten, lässt mich sowieso schaudern. Selbst für zufällige Verteilungen zwischen 0 und n haben wir bessere Alternativen (siehe arc4random_uniform) als zufällige * n…
mirabilos