Dlaczego ta losowa wartość ma rozkład 25/75 zamiast 50/50?

139

Edycja: Więc w zasadzie to, co próbuję napisać, to 1-bitowy hash double.

Chcę zmapować doubledo truelub falsez szansą 50/50. W tym celu napisałem kod, który wybiera losowe liczby (tak jak na przykład, chcę tego użyć na danych z regularnościami i nadal otrzymuję wynik 50/50) , sprawdza ich ostatni bit i przyrosty, yjeśli wynosi 1, lub njeśli jest 0.

Jednak ten kod stale daje 25% yi 75% n. Dlaczego nie jest to 50/50? A skąd taka dziwna, ale prosta (1/3) dystrybucja?

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);
    }
}

Przykładowe dane wyjściowe:

250167 749833
gvlasov
źródło
43
Naprawdę mam nadzieję, że odpowiedź jest czymś fascynującym w losowym generowaniu zmiennych zmiennoprzecinkowych, a nie „LCG ma niską entropię w niskich bitach”.
Sneftel
4
Jestem bardzo ciekawy, jaki jest cel „1-bitowego skrótu za podwójny”? Naprawdę nie mogę wymyślić żadnego uzasadnionego zastosowania takiego wymogu.
corsiKa
3
@corsiKa W obliczeniach geometrii często szukamy dwóch przypadków, aby wybrać jedną z dwóch możliwych odpowiedzi (np. czy jest to punkt na lewo czy na prawo od linii?), a czasami wprowadza trzeci, zdegenerowany przypadek (punkt to bezpośrednio w wierszu), ale masz tylko dwie dostępne odpowiedzi, więc w takim przypadku musisz pseudolosowo wybrać jedną z dostępnych odpowiedzi. Najlepszym sposobem, jaki mogłem wymyślić, jest zrobienie 1-bitowego skrótu jednej z podanych podwójnych wartości (pamiętaj, że są to obliczenia geometrii, więc wszędzie są podwojenie).
gvlasov
2
@corsiKa (komentarz podzielony na dwie części, ponieważ jest zbyt długi) Moglibyśmy zacząć od czegoś prostszego doubleValue % 1 > 0.5, ale byłoby to zbyt gruboziarniste, ponieważ w niektórych przypadkach może wprowadzić widoczne regularności (wszystkie wartości mieszczą się w zakresie długości 1). Jeśli jest zbyt gruboziarnisty, czy powinniśmy prawdopodobnie spróbować mniejszych zakresów, na przykład doubleValue % 1e-10 > 0.5e-10? No tak. Przyjmowanie ostatniego kawałka jako skrótu doublejest tym, co dzieje się, gdy postępujesz zgodnie z tym podejściem do końca, z najmniejszym możliwym modulo.
gvlasov
1
@kmote wtedy nadal miałbyś mocno obciążony najmniej znaczący bit, a drugi bit go nie kompensuje - w rzeczywistości jest również odchylony w kierunku zera (ale mniej), z dokładnie tego samego powodu. Więc rozkład wyniósłby około 50, 12,5, 25, 12,5. (lastbit & 3) == 0zadziała, choć to dziwne.
harold

Odpowiedzi:

165

Ponieważ nextDouble działa tak: ( źródło )

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

next(x)tworzy xlosowe bity.

Dlaczego to ma znaczenie? Ponieważ około połowa liczb generowanych przez pierwszą część (przed podziałem) jest mniejsza niż 1L << 52, a zatem ich znaczenie nie wypełnia całkowicie 53 bitów, które mogłaby wypełnić, co oznacza, że ​​najmniej znaczący bit znaczenia jest zawsze równy zeru.


Ze względu na ilość uwagi, którą to poświęca, oto dodatkowe wyjaśnienie, jak doublenaprawdę wygląda a w Javie (i wielu innych językach) i dlaczego ma to znaczenie w tym pytaniu.

Zasadniczo doublewygląda to tak: ( źródło )

podwójny układ

Bardzo ważnym szczegółem niewidocznym na tym rysunku jest to, że liczby są „znormalizowane” 1 tak, że 53-bitowy ułamek zaczyna się od 1 (wybierając taki wykładnik, że tak jest), a następnie 1 jest pomijany. Dlatego na rysunku ułamek (znacznik) przedstawia 52 bity, ale faktycznie zawiera on 53 bity.

Normalizacja oznacza, że ​​jeśli w kodzie dla nextDouble53. bitu jest ustawiony, ten bit jest niejawną wiodącą 1 i odchodzi, a pozostałe 52 bity są kopiowane dosłownie do znacznika wyniku double. Jeśli jednak ten bit nie zostanie ustawiony, pozostałe bity należy przesunąć w lewo, aż zostanie ustawiony.

Średnio połowa wygenerowanych liczb przypada na przypadek, w którym istotność nie została w ogóle przesunięta w lewo (a około połowa z nich ma 0 jako najmniej znaczący bit), a druga połowa jest przesunięta o co najmniej 1 (lub po prostu całkowicie zero), więc ich najmniej znaczący bit jest zawsze równy 0.

1: nie zawsze, oczywiście nie można tego zrobić dla zera, które nie ma najwyższego 1. Liczby te nazywane są liczbami denormalnymi lub subnormalnymi, patrz wikipedia: liczba denormalna .

harold
źródło
16
Brawo! Właśnie to, na co liczyłem.
Sneftel
3
@Matt Przypuszczalnie jest to optymalizacja prędkości. Alternatywą byłoby wygenerowanie wykładnika z rozkładem geometrycznym, a następnie osobno mantysy.
Sneftel
7
@Matt: Zdefiniuj „najlepszy”. random.nextDouble()jest zazwyczaj „najlepszym” sposobem na to, do czego jest przeznaczony, ale większość ludzi nie próbuje tworzyć 1-bitowego skrótu z losowego podwójnego skrótu. Szukasz jednolitego rozkładu, odporności na kryptoanalizę, czy co?
StriplingWarrior
1
Ta odpowiedź sugeruje, że gdyby OP pomnożył liczbę losową przez 2 ^ 53 i sprawdził, czy wynikowa liczba całkowita jest nieparzysta, istniałby rozkład 50/50.
rici
4
@ The111 mówi tutaj, że nextmusi zwrócić an int, więc i tak może mieć tylko 32 bity
harold
48

Z dokumentów :

Metoda nextDouble jest implementowana przez klasę Random tak, jakby przez:

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

Ale stwierdza również, co następuje (podkreślenie moje):

[We wczesnych wersjach Java wynik był nieprawidłowo obliczany jako:

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

Może się to wydawać równoważne, jeśli nie lepsze, ale w rzeczywistości wprowadziło dużą niejednorodność ze względu na odchylenie w zaokrąglaniu liczb zmiennoprzecinkowych: było trzy razy bardziej prawdopodobne, że najniższy bit znaczenia będzie wynosił 0 niż to, że będzie 1 ! Ta niejednorodność prawdopodobnie nie ma większego znaczenia w praktyce, ale dążymy do doskonałości.]

Ta notatka pojawiła się przynajmniej od Javy 5 (dokumenty dla Javy <= 1.4 są za zaporą logowania, zbyt leniwe, by je sprawdzić). To ciekawe, bo problem najwyraźniej nadal istnieje nawet w Javie 8. Być może „poprawiona” wersja nigdy nie była testowana?

Tomasz
źródło
4
Dziwne. Właśnie odtworzyłem to na Javie 8.
aioobe,
1
To interesujące, ponieważ właśnie przekonywałem, że błąd nadal dotyczy nowej metody. Czy się mylę?
harold
3
@harold: Nie, myślę, że masz rację, a ktokolwiek próbował naprawić to nastawienie, mógł popełnić błąd.
Thomas
6
@harold Czas wysłać e-mail do facetów z Javy.
Daniel
8
„Być może poprawiona wersja nigdy nie była testowana?” Właściwie, po ponownym przeczytaniu tego, myślę, że doktor był o innym problemie. Zauważ, że wspomina o zaokrąglaniu , co sugeruje, że nie uważali „trzy razy bardziej prawdopodobnego” za problem bezpośrednio, ale raczej, że prowadzi to do niejednolitego rozkładu, gdy wartości są zaokrąglane . Zwróć uwagę, że w mojej odpowiedzi podane przeze mnie wartości są równomiernie rozłożone, ale najniższy bit reprezentowany w formacie IEEE nie jest jednolity. Myślę, że problem, który naprawili, był związany z ogólną jednolitością, a nie jednolitością niskiego wędzidła.
ajb
33

Ten wynik nie dziwi mnie, biorąc pod uwagę sposób reprezentacji liczb zmiennoprzecinkowych. Załóżmy, że mamy bardzo krótki typ zmiennoprzecinkowy z tylko 4 bitami dokładności. Gdybyśmy mieli wygenerować liczbę losową z przedziału od 0 do 1, rozłożoną równomiernie, byłoby 16 możliwych wartości:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Jeśli tak wyglądali w maszynie, możesz przetestować mniej zamówiony bit, aby uzyskać dystrybucję 50/50. Jednak pływaki IEEE są reprezentowane jako potęga 2 razy mantysy; jedno pole w liczbie zmiennoprzecinkowej to potęga 2 (plus stałe przesunięcie). Potęga 2 jest tak dobrana, aby część „mantysy” była zawsze liczbą> = 1,0 i <2,0. Oznacza to, że w efekcie liczby inne niż 0.0000byłyby przedstawione w następujący sposób:

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

( 1Przed punktem binarnym jest domniemana wartość; dla 32- i 64-bitowych liczb zmiennoprzecinkowych żaden bit nie jest faktycznie przydzielany do przechowywania tego 1).

Ale patrząc na powyższe powinno pokazać, dlaczego, jeśli przekonwertujesz reprezentację na bity i spojrzysz na niski bit, otrzymasz zero w 75% przypadków. Wynika to z faktu, że wszystkie wartości mniejsze niż 0,5 (binarne 0.1000), co stanowi połowę możliwych wartości, mają przesunięte mantysy, powodując pojawienie się 0 w niskim bicie. Sytuacja jest zasadniczo taka sama, gdy mantysa ma 52 bity (nie licząc domniemanej 1) jak a double.

(Właściwie, jak zasugerował @sneftel w komentarzu, moglibyśmy uwzględnić więcej niż 16 możliwych wartości w dystrybucji, generując:

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

Ale nie jestem pewien, czy jest to rodzaj dystrybucji, którego spodziewałaby się większość programistów, więc prawdopodobnie nie jest to opłacalne. Poza tym niewiele zyskujesz, gdy wartości są używane do generowania liczb całkowitych, ponieważ często są to losowe wartości zmiennoprzecinkowe).

ajb
źródło
5
Używanie zmiennoprzecinkowych do uzyskiwania losowych bitów / bajtów / czegokolwiek sprawia, że ​​i tak drżę. Nawet dla losowych rozkładów między 0 a n mamy lepsze alternatywy (spójrz na arc4random_uniform) niż losowe * n…
mirabilos