Menghasilkan angka acak yang terdistribusi secara seragam menggunakan koin

Anda punya satu koin. Anda dapat membaliknya sebanyak yang Anda inginkan.

Anda ingin menghasilkan bilangan acak $r$ sehingga $a \leq r < b$ mana .$r,a,b\in \mathbb{Z}^+$

Distribusi angka harus seragam.

Mudah jika :$b -a = 2^n$

r = a + binary2dec(flip n times write 0 for heads and 1 for tails) 

Bagaimana jika ?$b-a \neq 2^n$

Apa yang Anda cari didasarkan pada sampel Penolakan atau metode accept-reject (perhatikan bahwa halaman Wiki sedikit teknis).

Metode ini berguna dalam situasi semacam ini: Anda ingin memilih beberapa objek acak dari suatu himpunan (bilangan bulat acak dalam himpunan dalam kasus Anda), tetapi Anda tidak tahu bagaimana melakukan itu, tetapi Anda dapat memilih beberapa objek acak dari set yang lebih besar berisi set pertama (dalam kasus Anda, [ a , 2 k + a ] untuk beberapa k sedemikian sehingga 2 k + a ≥ b ; ini sesuai dengan k coin flips).$[a,b]$$[a, 2^k + a]$$k$$2^k + a \ge b$$k$

Dalam skenario seperti itu, Anda tetap memilih elemen dari set yang lebih besar sampai Anda secara acak memilih elemen dalam set yang lebih kecil. Jika himpunan Anda yang lebih kecil cukup besar dibandingkan dengan himpunan Anda yang lebih besar (dalam kasus Anda, mengandung paling banyak dua kali lebih banyak bilangan bulat dari [ a , b ] , yang cukup baik), ini efisien.$[a, 2^k + a]$$[a,b]$

Contoh alternatif: misalkan Anda ingin memilih titik acak di dalam lingkaran dengan jari-jari 1. Sekarang, tidak mudah untuk membuat metode langsung untuk ini. Kita beralih ke metode accept-reject: kita sampel poin dalam kotak 1x1 yang mencakup lingkaran, dan menguji apakah angka yang kita gambar terletak di dalam lingkaran.

(teknis: jawabannya cocok dengan pemilihan angka )$a \le x < b$

Karena Anda diperbolehkan untuk membalik koin Anda sebanyak yang Anda inginkan, Anda bisa mendapatkan probabilitas Anda sedekat mungkin dengan seragam dengan memilih pecahan (menggunakan biner radix: Anda membalikkan koin untuk setiap digit setelah titik) dan kalikan r dengan b - a untuk mendapatkan angka antara 0 dan [ba-1] (pembulatan ke bilangan bulat). Menambahkan nomor ini untuk sebuah dan Anda sudah selesai.$r\in [0,1]$$r$$b-a$$a$

Contoh : katakanlah . 1/3 dalam biner adalah 0,0101010101 .... Lalu, jika flip Anda antara 0 dan 0,010101 ... pick Anda adalah b . jika beween 0.010101 .. dan 0.10101010 ... memilih Anda akan menjadi + 1 , dan jika tidak maka akan menjadi + 2 .$b-a=3$$b$$a+1$$a+2$

Jika Anda membalik koin Anda kali maka setiap angka antara a dan b akan dipilih dengan probabilitas $t$$a$$b$.$\frac{1}{b-a}\pm 2^{-(t+1)}$

Pilih angka dengan kekuatan 2 rentang yang lebih besar berikutnya, dan buang jawaban yang lebih besar dari .$b-a$

n = b-a;
N = round_to_next_larger_power_of_2(n)
while (1) {
  x = random(0 included to N excluded);
  if (x < n) break;
}
r = a + x;

Tidak ada yang menyebutkan ini, jadi izinkan saya membuktikan secara formal bahwa jika adalah domain yang ukurannya bukan kekuatan dua, maka banyak lemparan koin yang adil tidak cukup untuk menghasilkan anggota acak D yang seragam . Misalkan Anda menggunakan k koin untuk menghasilkan anggota dari D . Untuk setiap d ∈ D , kemungkinan bahwa algoritma Anda dihasilkan d adalah dari bentuk A / 2 k untuk beberapa bilangan bulat A . Teorema dasar aritmatika menunjukkan bahwa A / 2 k ≠ 1 / | D | .$D$$D$$k$$D$$d \in D$$d$$A/2^k$$A$$A/2^k \neq 1/{|D|}$

Jika Anda ingin menghasilkan sampel seragam D yang independen , maka jumlah lemparan koin yang Anda butuhkan (di bawah algoritma optimal) yang diharapkan adalah kira-kira n log 2 | D | . Lebih umum, jika Anda ingin menghasilkan dari distribusi entropi H , Anda perlu kira-kira n H bit acak dalam harapan. Algoritma yang mencapai hal ini adalah decoding aritmatika, yang diterapkan pada urutan acak bit yang tak terhingga.$n$$D$$n \log_2 |D|$$H$$nH$

Jika ba bukan kekuatan 2 maka Anda mungkin harus membalik banyak koin untuk mendapatkan hasil. Anda bahkan mungkin tidak pernah mendapatkan hasil, tetapi itu tidak mungkin di ekstrem.

Metode

Metode paling sederhana adalah menghasilkan angka dalam [a, a + 2 ^ n), di mana 2 ^ n> = ba, sampai seseorang mendarat di [a, b). Anda membuang banyak entropi dengan metode ini.

Metode yang lebih mahal memungkinkan Anda untuk menyimpan semua entropi, tetapi menjadi sangat mahal secara komputasi karena jumlah koin membalik / gulungan dadu meningkat. Secara intuitif itu seperti memperlakukan koin membalik sebagai digit angka biner di sebelah kanan titik desimal, mengonversi angka itu dari basis 2 ke basis ab setelahnya, dan mengembalikan digit angka itu ketika menjadi 'macet'.

Contoh

Kode berikut mengubah gulungan dari die-sided die yang adil menjadi roll dari sided die-sided (dalam kasus Anda n = 2, m = ab), dengan meningkatnya biaya marjinal karena jumlah roll meningkat. Perhatikan perlunya jenis nomor Rasional dengan presisi sewenang-wenang. Salah satu properti yang bagus adalah mengubah dari sisi ke sisi ke sisi dan kembali ke sisi sisi akan mengembalikan aliran asli, meskipun mungkin tertunda oleh beberapa gulungan karena angka harus menjadi macet.

public static IEnumerable<BigInteger> DigitConversion(this IEnumerable<BigInteger> inputStream, BigInteger modIn, BigInteger modOut) {
    //note: values are implicitly scaled so the first unfixed digit of the output ranges from 0 to 1
    Rational b = 0; //offset of the chosen range
    Rational d = 1; //size of the chosen range
    foreach (var r in inputStream) {
        //narrow the chosen range towards the real value represented by the input
        d /= modIn;
        b += d * r;
        //check for output digits that have become fixed
        while (true) {
            var i1 = (b * modOut).Floor();
            var i2 = ((b + d) * modOut).Floor(); //note: ideally b+d-epsilon, but another iteration makes that correction unnecessary
            if (i1 != i2) break; //digit became fixed?
            //fix the next output digit (rescale the range to make next digit range from 0 to 1)
            d *= modOut;
            b *= modOut;
            b -= i1;
            yield return i1;
        }
    }
}

Hasilkan desimal biner. Alih-alih menyimpannya secara eksplisit, tetap melacak nilai min dan maks yang mungkin. Setelah nilai-nilai itu berada di dalam integer yang sama, kembalikan integer itu. Sketsa kode di bawah ini.

(Edit) Penjelasan lebih lengkap: Katakan Anda ingin membuat bilangan bulat acak dari 1 hingga 3 inklusif dengan 1/3 probabilitas masing-masing. Kami melakukan ini dengan menghasilkan desimal biner acak nyata, x dalam kisaran (0, 1). Jika x <1/3, kembalikan 1, kalau tidak x <2/3 kembalikan 2, kembalikan 3. Alih-alih menghasilkan digit untuk x secara eksplisit, kami hanya melacak nilai minimum dan maksimum yang mungkin dari x. Awalnya, nilai min dari x adalah 0 dan maks adalah 1. Jika Anda membalik kepala lebih dulu maka digit pertama x di belakang titik desimal (dalam biner) adalah 1. Nilai minimum yang mungkin dari x (dalam biner) kemudian menjadi 0,100000 = 1/2 dan maksnya adalah 0,111111111 = 1. Sekarang jika flip Anda berikutnya adalah ekor x dimulai dengan 0,10. Nilai minimum yang mungkin adalah 0,1000000 = 1/2 dan maksnya adalah 0,1011111 = 3/4. Nilai minimum yang mungkin dari x adalah 1/2 sehingga Anda tahu di sana ' tidak ada peluang untuk mengembalikan 1 karena itu memerlukan x <1/3. Anda masih dapat mengembalikan 2 jika x akhirnya menjadi 1/2 <x <2/3 atau 3 jika 2/3 <x <3/4. Sekarang anggaplah flip ketiga adalah ekor. Kemudian x harus mulai dengan 0,100. Min = 0,10000000 = 1/2 dan maks = 0,100111111 = 5/8. Sekarang sejak 1/3 <1/2 <5/8 <2/3 kita tahu bahwa x harus termasuk dalam interval (1/3, 2/3), sehingga kita dapat berhenti menghasilkan angka x dan hanya mengembalikan 2.

Pada dasarnya kode melakukan ini kecuali alih-alih menghasilkan x antara 0 dan 1, ia menghasilkan x antara a dan b, tetapi prinsipnya sama.

def gen(a, b):
  min_possible = a
  max_possible = b

  while True:
    floor_min_possible = floor(min_possible)
    floor_max_possible = floor(max_possible)
    if max_possible.is_integer():
      floor_max_possible -= 1

    if floor_max_possible == floor_min_possible:
      return floor_max_possible

    mid = (min_possible + max_possible)/2
    if coin_flip():
      min_possible = mid
    else:
      max_possible = mid

Catatan: Saya menguji kode ini terhadap metode accept / reject dan keduanya menghasilkan distribusi yang seragam. Kode ini membutuhkan lebih sedikit koin membalik daripada menerima menolak kecuali ketika b - a dekat dengan kekuatan berikutnya dari 2. Ex jika Anda ingin menghasilkan a = 0, b = 62 maka menerima / menolak tidak lebih baik. Saya dapat membuktikan bahwa kode ini dapat digunakan rata-rata tidak lebih dari 2 membalik koin daripada menerima / menolak. Dari bacaan saya, sepertinya Knuth dan Yao (1976) memberikan metode untuk menyelesaikan masalah ini dan membuktikan bahwa metode mereka optimal dalam jumlah flips koin yang diharapkan. Mereka lebih lanjut membuktikan bahwa jumlah flips yang diharapkan harus lebih besar daripada entropi Shannon dari distribusi. Saya tidak dapat menemukan salinan teks dari makalah ini dan ingin tahu apa metode mereka. (Pembaruan: baru saja menemukan eksposisi Knuth Yao 1976 di sini:http://www.nrbook.com/devroye/Devroye_files/chapter_fifteen_1.pdf tapi saya belum membacanya). Seseorang juga menyebut Han Hoshi di utas ini yang tampaknya lebih umum dan menyelesaikannya menggunakan koin bias. Lihat juga http://paper.ijcsns.org/07_book/200909/20090930.pdf oleh Pae (2009) untuk diskusi literatur yang baik.

Jawaban sederhana?

$b-a$$r$

$r$$b - a = 2^n + 1$$n$

Ini adalah solusi yang diusulkan untuk kasus ketika b - a tidak sama dengan 2 ^ k. Seharusnya bekerja dalam jumlah langkah tetap (tidak perlu membuang kandidat yang berada di luar kisaran yang Anda harapkan).

Namun, saya tidak yakin ini benar. Harap kritik dan bantu uraikan ketidakseragaman yang tepat dalam penghasil angka acak ini (jika ada), dan bagaimana mengukur / mengukurnya.

Konversi pertama ke masalah ekuivalen menghasilkan angka acak yang terdistribusi secara merata dalam rentang [0, z-1] di mana z = b - a.

Juga, misalkan m = 2 ^ k menjadi kekuatan terkecil dari 2> = z.

Sesuai solusi di atas, kami sudah memiliki generator nomor acak R yang didistribusikan secara seragam dalam kisaran [0, m-1] (dapat dilakukan dengan melemparkan koin k, satu untuk setiap bit).

    Keep a random seed s and initialize with s = R(m).   

    function random [0, z-1] :
        x = R(m) + s 
        while x >= z:
            x -= z
        s = x
        return x

Loop sementara berjalan paling banyak 3 kali, memberikan angka acak berikutnya dalam jumlah langkah tetap (kasus terbaik = kasus terburuk).

Lihat program pengujian untuk angka [0,2] di sini: http://pastebin.com/zuDD2V6H

Algoritma optimal secara teoritis

Ini adalah peningkatan dari jawaban lain yang saya posting. Jawaban lainnya memiliki keuntungan bahwa lebih mudah untuk memperluas ke kasus yang lebih umum menghasilkan satu distribusi diskrit dari yang lain. Sebenarnya, jawaban lain adalah kasus khusus dari algoritma karena Han dan Hoshi.

Algoritma yang akan saya jelaskan di sini didasarkan pada Knuth dan Yao (1976). Dalam makalah mereka, mereka juga membuktikan bahwa algoritma ini mencapai jumlah minimum yang diharapkan dari jumlah koin yang terbalik.

Untuk menggambarkannya, pertimbangkan metode pengambilan sampel Penolakan yang dijelaskan oleh jawaban lain. Sebagai contoh, misalkan Anda ingin menghasilkan satu dari 5 angka secara seragam [0, 4]. Kekuatan 2 berikutnya adalah 8 sehingga Anda membalik koin 3 kali dan menghasilkan angka acak hingga 8. Jika jumlahnya 0 hingga 4 maka Anda mengembalikannya. Kalau tidak, Anda membuangnya dan menghasilkan nomor lain hingga 8 dan coba lagi sampai Anda berhasil. Tetapi ketika Anda membuang nomornya, Anda hanya membuang beberapa entropi. Sebagai gantinya, Anda dapat mengkondisikan jumlah yang Anda buang untuk mengurangi jumlah flips koin di masa depan yang Anda butuhkan dengan harapan. Konkretnya, begitu Anda menghasilkan angka [0, 7], jika itu [0, 4], kembalilah. Kalau tidak, ini 5, 6, atau 7, dan Anda melakukan sesuatu yang berbeda dalam setiap kasus. Jika 5, balik koin lagi dan kembalikan 0 atau 1 berdasarkan flip. Jika 6, balik koin dan kembalikan 2 atau 3. Jika 7, balik koin; jika kepala, kembalilah 4, jika ekornya mulai dari awal.

Entropi sisa dari upaya awal kami yang gagal memberi kami 3 kasus (5, 6, atau 7). Jika kita membuang ini, kita membuang log2 (3) koin membalik. Kami malah menyimpannya, dan menggabungkannya dengan hasil flip lain untuk menghasilkan 6 kemungkinan kasus (5H, 5T, 6H, 6T, 7H, 7T) yang mari kita segera mencoba lagi untuk menghasilkan jawaban akhir dengan probabilitas keberhasilan 5/6 .

Ini kodenya:

# returns an int from [0, b)
def __gen(b):
  rand_num = 0
  num_choices = 1

  while True:
    num_choices *= 2
    rand_num *= 2
    if coin.flip():
      rand_num += 1

    if num_choices >= b:
      if rand_num < b:
        return rand_num
      num_choices -= b
      rand_num -= b

# returns an int from [a, b)
def gen(a, b):
  return a + __gen(b - a)