Mengapa nilai acak ini memiliki distribusi 25/75 bukannya 50/50?

139

Sunting: Jadi pada dasarnya yang ingin saya tulis adalah hash 1 bit double.

Saya ingin memetakan doubleke trueatau falsedengan peluang 50/50. Untuk itu saya menulis kode yang mengambil beberapa angka acak (seperti contoh, saya ingin menggunakan ini pada data dengan keteraturan dan masih mendapatkan hasil 50/50) , memeriksa bit terakhir mereka dan kenaikan yjika itu adalah 1, atau njika itu adalah 0.

Namun, kode ini secara konstan menghasilkan 25% ydan 75% n. Mengapa bukan 50/50? Dan mengapa distribusi yang aneh, tetapi langsung (1/3)?

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

Contoh output:

250167 749833
gvlasov
sumber
43
Saya benar-benar berharap jawabannya adalah sesuatu yang menarik tentang generasi acak dari variabel floating-point, daripada "LCG memiliki entropi rendah dalam bit rendah".
Sneftel
4
Saya sangat ingin tahu, apa tujuan dari "hash 1 bit untuk double"? Saya benar-benar tidak dapat memikirkan aplikasi sah dari persyaratan seperti itu.
corsiKa
3
@corsiKa Dalam perhitungan geometri sering ada dua kasus yang kami cari untuk dipilih dari dua jawaban yang mungkin (mis. adalah titik ke kiri atau ke kanan garis?), dan kadang-kadang memperkenalkan kasus ketiga, kemerosotan (titik adalah tepat di telepon), tetapi Anda hanya memiliki dua jawaban yang tersedia, jadi Anda harus memilih secara acak salah satu jawaban yang tersedia dalam kasus itu. Cara terbaik yang bisa saya pikirkan adalah untuk mengambil 1 bit hash dari salah satu nilai ganda yang diberikan (ingat, itu adalah perhitungan geometri, jadi ada dua kali lipat semua tempat).
gvlasov
2
@corsiKa (komentar dibagi menjadi dua karena terlalu panjang) Kita bisa mulai pada sesuatu yang lebih sederhana seperti doubleValue % 1 > 0.5, tapi itu akan terlalu kasar karena dapat memperkenalkan keteraturan yang terlihat dalam beberapa kasus (semua nilai berada dalam kisaran panjang 1). Jika itu terlalu berbutir kasar, maka haruskah kita mencoba rentang yang lebih kecil, seperti doubleValue % 1e-10 > 0.5e-10? Baiklah. Dan mengambil bit terakhir sebagai hash dari doubleapa yang terjadi ketika Anda mengikuti pendekatan ini sampai akhir, dengan modulo sesedikit mungkin.
gvlasov
1
@kmote maka Anda masih akan memiliki sedikit bias paling signifikan, dan yang lainnya tidak mengimbanginya - bahkan bias juga ke nol (tapi kurang begitu), untuk alasan yang persis sama. Jadi distribusinya sekitar 50, 12.5, 25, 12.5. (lastbit & 3) == 0akan bekerja meskipun aneh.
harold

Jawaban:

165

Karena nextDouble berfungsi seperti ini: ( sumber )

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

next(x)membuat xbit acak.

Sekarang mengapa ini penting? Karena sekitar setengah angka yang dihasilkan oleh bagian pertama (sebelum pembagian) kurang dari 1L << 52, dan karena itu signifikansi mereka tidak sepenuhnya mengisi 53 bit yang bisa diisi, berarti bit paling signifikan dari signifikansi selalu nol untuk mereka.


Karena besarnya perhatian yang diterima ini, berikut adalah beberapa penjelasan tambahan tentang seperti apa bahasa doubleJava (dan banyak bahasa lainnya) dan mengapa itu penting dalam pertanyaan ini.

Pada dasarnya, doubleterlihat seperti ini: ( sumber )

tata letak ganda

Detail yang sangat penting yang tidak terlihat dalam gambar ini adalah bahwa angka-angka "dinormalisasi" 1 sehingga fraksi 53 bit dimulai dengan 1 (dengan memilih eksponen sedemikian rupa), 1 kemudian dihilangkan. Itu sebabnya gambar menunjukkan 52 bit untuk fraksi (signifikansi) tetapi ada efektif 53 bit di dalamnya.

Normalisasi berarti bahwa jika dalam kode untuk nextDoublebit ke -53 diatur, bit itu adalah yang terdepan 1 dan hilang, dan 52 bit lainnya disalin secara harfiah ke signifikansi yang dihasilkan double. Namun, jika bit itu tidak disetel, bit yang tersisa harus digeser ke kiri sampai ditetapkan.

Rata-rata, setengah angka yang dihasilkan masuk ke dalam kasus di mana signifikansi tidak bergeser ke kiri sama sekali (dan sekitar setengahnya memiliki 0 sebagai bit paling signifikan), dan setengah lainnya digeser oleh setidaknya 1 (atau hanya sepenuhnya nol) jadi bit paling signifikan mereka selalu 0.

1: tidak selalu, jelas itu tidak dapat dilakukan untuk nol, yang tidak memiliki angka tertinggi 1. Angka-angka ini disebut angka denormal atau subnormal, lihat wikipedia: nomor denormal .

Harold
sumber
16
Hore! Apa yang saya harapkan.
Sneftel
3
@ Matt Mungkin ini adalah optimasi kecepatan. Alternatifnya adalah menghasilkan eksponen dengan distribusi geometris, dan kemudian mantissa secara terpisah.
Sneftel
7
@ Mat: Tentukan "terbaik." random.nextDouble()biasanya merupakan cara "terbaik" untuk apa yang dimaksudkan, tetapi kebanyakan orang tidak mencoba untuk menghasilkan hash 1-bit dari double acak mereka. Apakah Anda mencari distribusi yang seragam, resistensi terhadap kriptanalisis, atau apa?
StriplingWarrior
1
Jawaban ini menunjukkan bahwa jika OP telah mengalikan angka acak dengan 2 ^ 53 dan memeriksa apakah bilangan bulat yang dihasilkan ganjil, akan ada distribusi 50/50.
rici
4
@ The111 dikatakan di sini bahwa nextharus mengembalikan int, sehingga hanya dapat memiliki hingga 32 bit
harold
48

Dari dokumen :

Metode nextDouble diimplementasikan oleh kelas Acak seolah-olah oleh:

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

Tapi itu juga menyatakan yang berikut (penekanan milikku):

[Dalam versi awal Java, hasilnya salah dihitung sebagai:

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

Ini mungkin tampak setara, jika tidak lebih baik, tetapi faktanya hal itu memperkenalkan ketidakmerataan yang besar karena bias dalam pembulatan bilangan floating-point: tiga kali lebih mungkin bahwa bit orde rendah dari signifikansi akan menjadi 0 selain itu akan menjadi 1 ! Ketidakseragaman ini mungkin tidak terlalu penting dalam praktiknya, tetapi kami berusaha untuk kesempurnaan.]

Catatan ini sudah ada sejak Java 5 setidaknya (dokumen untuk Java <= 1.4 berada di belakang panel masuk, terlalu malas untuk memeriksa). Ini menarik, karena masalahnya ternyata masih ada bahkan di Jawa 8. Mungkin versi "tetap" tidak pernah diuji?

Thomas
sumber
4
Aneh. Saya baru saja mereproduksi ini di Jawa 8.
aioobe
1
Nah, itu menarik, karena saya baru saja berpendapat bahwa bias masih berlaku untuk metode baru. Apakah aku salah?
Harold
3
@ Harvest: Tidak, saya pikir Anda benar dan siapa pun yang mencoba untuk memperbaiki bias ini mungkin telah melakukan kesalahan.
Thomas
6
@harold Saatnya mengirim email ke Java guys.
Daniel
8
"Mungkin versi tetap tidak pernah diuji?" Sebenarnya, saat membaca ulang ini, saya pikir dokter tentang masalah yang berbeda. Perhatikan bahwa itu menyebutkan pembulatan , yang menunjukkan bahwa mereka tidak menganggap "tiga kali lebih mungkin" menjadi masalah, secara langsung, tetapi ini mengarah pada distribusi yang tidak seragam ketika nilai dibulatkan . Perhatikan bahwa dalam jawaban saya, nilai-nilai yang saya daftarkan terdistribusi secara seragam, tetapi bit orde rendah seperti yang diwakili dalam format IEEE tidak seragam. Saya pikir masalah yang mereka perbaiki berkaitan dengan keseragaman keseluruhan, bukan keseragaman bit rendah.
ajb
33

Hasil ini tidak mengejutkan saya mengingat bagaimana angka floating-point direpresentasikan. Misalkan kita memiliki tipe floating-point yang sangat pendek dengan presisi hanya 4 bit. Jika kita menghasilkan angka acak antara 0 dan 1, didistribusikan secara seragam, akan ada 16 nilai yang mungkin:

0.0000
0.0001
0.0010
0.0011
0.0100
...
0.1110
0.1111

Jika itu yang mereka lihat di mesin, Anda bisa menguji bit orde rendah untuk mendapatkan distribusi 50/50. Namun, IEEE float direpresentasikan sebagai kekuatan 2 kali mantissa; satu bidang dalam float adalah kekuatan 2 (ditambah offset tetap). Kekuatan 2 dipilih sehingga bagian "mantissa" selalu berupa angka> = 1.0 dan <2.0. Ini berarti bahwa, pada dasarnya, angka-angka selain 0.0000akan diwakili seperti ini:

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

( 1Sebelum titik biner adalah nilai tersirat; untuk mengapung 32- dan 64-bit, sebenarnya tidak ada bit yang dialokasikan untuk menampung ini 1.)

Tetapi melihat di atas harus menunjukkan mengapa, jika Anda mengubah representasi menjadi bit dan melihat bit rendah, Anda akan mendapatkan nol 75% dari waktu. Ini disebabkan oleh semua nilai kurang dari 0,5 (biner 0.1000), yang merupakan setengah dari nilai yang mungkin, setelah mantisa mereka bergeser, menyebabkan 0 muncul dalam bit rendah. Situasinya pada dasarnya sama ketika mantissa memiliki 52 bit (tidak termasuk 1 tersirat) seperti yang doubledilakukan.

(Sebenarnya, seperti yang disarankan @sneftel dalam komentar, kami dapat menyertakan lebih dari 16 nilai yang mungkin dalam distribusi, dengan menghasilkan:

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

Tapi saya tidak yakin itu jenis distribusi yang kebanyakan programmer harapkan, jadi mungkin tidak bermanfaat. Plus itu tidak banyak membantu Anda ketika nilai digunakan untuk menghasilkan bilangan bulat, seperti nilai floating-point acak sering.)

ajb
sumber
5
Menggunakan floating point untuk mendapatkan bit acak / byte / apa saja membuat saya bergidik. Bahkan untuk distribusi acak antara 0 dan n, kami memiliki alternatif yang lebih baik (lihat arc4random_uniform) daripada acak * n ...
mirabilos