Darts, Dice, and Coins: Algoritma Distribusi Terpisah

Saya pernah bertanya kepada Stack Overflow pertanyaan tentang struktur data untuk selingkuh dadu . Secara khusus, saya tertarik pada jawaban untuk pertanyaan ini: “Jika kita memiliki tulang n-facet, wajah yang memiliki kemungkinan rontok p _i . Apa struktur data yang paling efektif untuk mensimulasikan gulungan tulang seperti itu? "

Struktur data ini dapat digunakan untuk banyak tugas. Misalnya, Anda dapat menggunakannya untuk mensimulasikan gulungan hex jujur, menetapkan probabilitas $$$\ frac {1} {6}$ setiap sisi tulang, atau untuk mensimulasikan koin yang adil dengan meniru tulang bilateral, kemungkinan jatuh dari setiap sisi yang sama dengan $$$\ frac {1} {2}$ . Anda juga dapat menggunakan struktur data ini untuk secara langsung mensimulasikan jumlah dua tulang hex jujur ​​dengan membuat tulang 11-sisi (dengan wajah 2, 3, 4, ..., 12), masing-masing wajah yang memiliki bobot probabilitas yang sesuai dengan gulungan dua tulang jujur. Namun, Anda juga dapat menggunakan struktur data ini untuk mensimulasikan tulang selingkuh. Misalnya, jika Anda bermain dadu dengan tulang, yang, seperti yang Anda tahu, tidak sepenuhnya jujur, maka Anda dapat menggunakan struktur data ini untuk mensimulasikan banyak gulungan tulang dan menganalisis strategi yang optimal. Anda juga dapat mencoba mensimulasikan roda roulette yang juga tidak sempurna.

Jika Anda melampaui game, Anda dapat menerapkan struktur data ini dalam simulasi robot yang sensornya diketahui tingkat kegagalannya. Misalnya, jika sensor rentang memiliki probabilitas 95% untuk mengembalikan nilai yang benar, probabilitas 4% dari nilai yang terlalu kecil, dan probabilitas 1% dari nilai yang terlalu tinggi, maka Anda dapat menggunakan struktur data ini untuk mensimulasikan pembacaan pembacaan sensor dengan menghasilkan hasil acak dan mensimulasikan pembacaan sensor hasil.

Jawaban yang saya terima di Stack Overflow mengesankan saya karena dua alasan. Pertama, dalam solusi saya disarankan untuk menggunakan teknik yang kuat yang disebut metode alias , yang, dengan asumsi masuk akal tertentu tentang model mesin, dapat, setelah tahap persiapan awal yang sederhana, untuk mensimulasikan gulungan tulang dari waktu ke waktu. $$$O (1)$ . Kedua, saya bahkan lebih terkejut bahwa algoritma ini telah dikenal selama beberapa dekade, tetapi saya belum pernah menemukannya! Mengingat berapa banyak waktu komputasi dihabiskan untuk simulasi, orang akan berharap bahwa teknik ini jauh lebih dikenal. Beberapa pertanyaan di Google memberi saya banyak informasi tentang teknik ini, tetapi saya tidak dapat menemukan satu situs di mana pemahaman intuitif dan penjelasan teknik ini datang bersama.

Artikel ini adalah upaya saya untuk memberikan gambaran singkat tentang berbagai pendekatan untuk mensimulasikan tulang kecurangan, dari teknik sederhana dan sangat tidak praktis hingga metode alias yang sangat optimal dan efektif. Saya berharap bahwa saya akan dapat menyampaikan berbagai cara untuk memahami tugas secara intuitif dan bagaimana masing-masing dari mereka menekankan beberapa aspek baru dalam mensimulasikan tulang yang curang. Tujuan saya untuk setiap pendekatan adalah mempelajari ide yang memotivasi, algoritma dasar, bukti kesetiaan, dan analisis runtime (dalam hal waktu, memori, dan keacakan yang diperlukan).

Entri

Sebelum beralih ke detail spesifik dari berbagai teknik, mari kita terlebih dahulu membakukan terminologi dan notasi.

Dalam pengantar artikel, saya menggunakan istilah "tulang selingkuh" untuk menggambarkan skenario umum di mana ada serangkaian hasil yang terbatas, masing-masing memiliki probabilitas. Secara formal, ini disebut distribusi probabilitas diskrit , dan tugas mensimulasikan tulang kecurangan disebut pengambilan sampel dari distribusi diskrit .

Untuk menggambarkan distribusi probabilitas diskrit kami (tulang curang), kami akan menganggap bahwa kami memiliki serangkaian probabilitas $$$p_0, p_1, ..., p_ {n - 1}$ terkait dengan hasilnya $$$0, 1, ..., n - 1$ . Meskipun hasilnya bisa berupa apa saja (elang / ekor, angka pada tulang, warna, dll.), Untuk kesederhanaan saya akan menganggap hasilnya sebagai semacam bilangan real positif yang sesuai dengan indeks yang diberikan.

Bekerja dengan bilangan real pada komputer adalah "area abu-abu" dari komputasi. Ada banyak algoritma cepat, kecepatan yang disediakan semata-mata oleh kemampuan untuk menghitung fungsi lantai bilangan real arbitrer dalam waktu yang konstan, dan ketidakakuratan numerik dalam representasi angka floating point dapat sepenuhnya menghancurkan beberapa algoritma. Oleh karena itu, sebelum memulai setiap diskusi tentang algoritma yang bekerja dengan probabilitas, yaitu memasuki dunia gelap bilangan real, saya harus mengklarifikasi apa yang dapat dan tidak bisa dilakukan oleh komputer.

Selanjutnya, saya akan berasumsi bahwa semua operasi berikut dapat dilakukan dalam waktu yang konstan:

• Selain itu. pengurangan, penggandaan, pembagian dan perbandingan bilangan real arbitrer . Kita perlu melakukan ini untuk memanipulasi probabilitas. Ini mungkin tampak seperti asumsi yang berani, tetapi jika kita berasumsi bahwa keakuratan bilangan real dibatasi oleh beberapa polinomial dari ukuran kata mesin (misalnya, 64-bit ganda pada mesin 32-bit), tetapi saya tidak berpikir itu terlalu tidak masuk akal.
• Generasi bilangan real seragam dalam interval [0, 1). Untuk mensimulasikan keacakan, kita memerlukan beberapa sumber nilai acak. Saya kira kita dapat menghasilkan sejumlah akurasi yang sewenang-wenang dalam waktu yang konstan. Sejauh ini melebihi kemampuan komputer yang sebenarnya, tetapi menurut saya untuk keperluan diskusi ini hal ini dapat diterima. Jika kita sepakat untuk mengorbankan sebagian akurasi dengan mengatakan bahwa IEEE-754 double arbitrary berada dalam interval [0, 1], maka kita sebenarnya akan kehilangan akurasi, tetapi hasilnya cenderung cukup akurat untuk sebagian besar aplikasi.
• Perhitungan bilangan bulat (pembulatan ke bawah) dari bilangan real. Ini dapat diterima jika kita berasumsi bahwa kita bekerja dengan IEEE-754 dobel, tetapi secara umum, persyaratan untuk komputer seperti itu tidak layak.

Layak mengajukan pertanyaan - apakah masuk akal untuk menganggap bahwa kita dapat melakukan semua operasi ini secara efektif. Dalam praktiknya, kami jarang menggunakan probabilitas yang ditunjukkan ke tingkat akurasi di mana kesalahan pembulatan yang melekat pada IEEE-754 ganda dapat menyebabkan masalah serius, sehingga kami dapat memenuhi semua persyaratan di atas hanya dengan bekerja secara eksklusif dengan IEEE ganda. Namun, jika kita berada di lingkungan di mana probabilitas ditunjukkan persis dengan angka rasional dengan akurasi tinggi, maka pembatasan tersebut mungkin tidak masuk akal.

Simulasi tulang yang jujur

Sebelum kita beralih ke kasus yang lebih umum tentang melempar tulang selingkuh yang sewenang-wenang, mari kita mulai dengan algoritma yang lebih sederhana yang akan berfungsi sebagai blok pembangun untuk algoritma berikut: mensimulasikan tulang berwajah n yang jujur. Misalnya, gulungan dadu heksagonal yang jujur ​​saat bermain Monopoli atau Risiko, atau melemparkan koin yang jujur ​​(dadu dua sisi), dll. Dapat berguna bagi kami.

Untuk kasus khusus ini, ada algoritma sederhana, elegan dan efektif untuk mensimulasikan hasilnya. Algoritma ini didasarkan pada ide berikut: misalkan kita dapat menghasilkan bilangan real yang benar-benar acak dan terdistribusi seragam dalam interval $$$[0, 1)$ . Interval ini dapat diilustrasikan sebagai berikut:


Sekarang jika kita ingin berhenti $$$n$ tulang faceted, maka salah satu caranya adalah dengan membagi interval $$$[0, 1)$ pada $$$n$ area dengan ukuran yang sama, masing-masing memiliki panjang $$$\ frac {1} {n}$ . Ini terlihat seperti ini:


Selanjutnya, kami menghasilkan bilangan real yang dipilih secara acak dalam interval $$$[0, 1)$ yang pasti jatuh ke salah satu area kecil ini. Dari ini, kita dapat menghitung hasil gulungan tulang dengan melihat area tempat nomor itu jatuh. Misalnya, jika nilai kami yang dipilih secara acak jatuh ke tempat ini:


maka kita dapat mengatakan bahwa 2 jatuh pada tulang (jika kita mengasumsikan bahwa tepi tulang diindeks dari awal).

Secara grafis mudah untuk melihat wilayah mana yang memiliki nilai acak, tetapi bagaimana kita menyandikan ini dalam suatu algoritma? Dan di sini kita mengambil keuntungan dari kenyataan bahwa ini adalah tulang yang jujur. Karena semua interval memiliki ukuran yang sama, yaitu $$$\ frac {1} {n}$ , maka kita bisa melihat apa nilai terbesarnya $$$i$ adalah seperti itu $$$\ frac {i} {n}$ tidak lebih dari nilai yang dihasilkan secara acak (sebut saja nilai ini x). Anda mungkin memperhatikan bahwa jika kami ingin menemukan nilai maksimum, seperti itu $$$\ frac {i} {n} \ le x$ , maka ini mirip dengan mencari nilai maksimum $$$n$ sedemikian rupa $$$i \ le xn$ . Tapi ini menurut definisi berarti itu $$$i = \ lfloor xn \ rfloor$ , bilangan bulat positif terbesar tidak lebih besar dari xn. Oleh karena itu, ini membawa kita ke algoritma simulasi tulang n-faceted jujur ​​(sangat sederhana) ini:

Algoritma: Simulasi tulang yang jujur

1. Hasilkan nilai acak yang terdistribusi secara seragam $$$x$ dalam jangkauan $$$[0, 1)$ .
2. Kembali $$$\ lfloor xn \ rfloor$ .

Dengan asumsi kami di atas tentang perhitungan, algoritma ini berjalan tepat waktu $$$O (1)$ .

Dua kesimpulan dapat ditarik dari bagian ini. Pertama, kita dapat membagi intervalnya $$$[0, 1)$ sebagian sehingga bilangan real acak terdistribusi seragam dalam interval ini secara alami berkurang menjadi salah satu dari banyak opsi diskrit yang tersedia untuk kita. Di sisa artikel ini, kami akan secara aktif mengeksploitasi teknik ini. Kedua, mungkin sulit untuk menentukan interval tertentu yang dimiliki oleh nilai acak, tetapi jika kita mengetahui sesuatu tentang bagian-bagian tersebut (dalam hal ini, bahwa mereka semua memiliki ukuran yang sama), maka kita secara matematis dapat dengan mudah menentukan bagian mana yang spesifik merujuk pada titik.

Simulasi kecurangan tulang dengan tulang jujur

Dengan algoritma simulasi tulang yang jujur, dapatkah kita mengadaptasinya untuk mensimulasikan tulang yang curang? Menariknya, jawabannya adalah ya, tetapi solusi akan membutuhkan lebih banyak ruang.

Dari bagian sebelumnya, secara intuitif jelas bahwa untuk mensimulasikan lemparan tulang selingkuh, itu cukup untuk membagi interval $$$[0, 1)$ berkeping-keping, dan kemudian menentukan bagian mana yang kita tekan. Namun, dalam kasus umum, ini bisa menjadi jauh lebih rumit daripada yang terlihat. Katakanlah kita memiliki tetrahedron dengan probabilitas wajah $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ dan $$$\ frac {1} {12}$ (kita dapat memastikan bahwa ini adalah distribusi probabilitas yang benar, karena $$$\ frac {1} {2} + \ frac {1} {3} + \ frac {1} {12} + \ frac {1} {12} = \ frac {6} {12} + \ frac {4 } {12} + \ frac {1} {12} + \ frac {1} {12} = \ frac {12} {12}$ ) Jika kita membagi intervalnya $$$[0, 1)$ menjadi empat bagian dari ukuran ini, maka kita mendapatkan yang berikut:


Sayangnya, pada langkah ini kita mandek. Bahkan jika kita tahu angka acak dalam interval $$$[0, 1)$ , maka tidak ada trik matematika sederhana untuk secara otomatis menentukan bagian mana dari nomor ini. Saya tidak ingin mengatakan bahwa ini tidak mungkin - seperti yang akan Anda lihat, kami dapat menggunakan banyak trik luar biasa - tetapi tidak ada yang memiliki kesederhanaan matematis dari algoritma melempar tulang yang jujur.

Namun, kita dapat mengadaptasi teknik yang digunakan untuk tulang yang jujur ​​untuk bekerja dalam kasus ini juga. Mari kita ambil tulang yang dibahas di atas sebagai contoh. Peluang jatuh tepi adalah $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ dan $$$\ frac {1} {12}$ . Jika kami menulis ulang ini sehingga semua anggota memiliki pembagi yang sama, kami mendapatkan nilainya $$$\ frac {6} {12}$ , $$$\ frac {4} {12}$ , $$$\ frac {1} {12}$ dan $$$\ frac {1} {12}$ . Oleh karena itu, kita dapat memahami tugas ini sebagai berikut: alih-alih melempar tulang tetrahedral dengan probabilitas tertimbang, mengapa tidak melempar tulang jujur ​​12 sisi, di tepian yang memiliki nilai duplikat? Karena kita tahu bagaimana mensimulasikan tulang yang jujur, ini akan analog dengan pemisahan interval $$$[0, 1)$ berkeping-keping dengan cara ini:


Kemudian kami menugaskan mereka ke berbagai hasil sebagai berikut:


Sekarang akan sangat sederhana untuk mensimulasikan lemparan tulang - kita hanya melempar tulang jujur ​​baru ini, dan kemudian kita melihat wajah yang telah jatuh dan membaca nilainya. Langkah pertama ini dapat dilakukan oleh algoritma yang disajikan di atas, yang akan memberi kita bilangan bulat angka dalam interval $$$0, 1, ..., 11$ . Untuk mengikat bilangan bulat ini ke salah satu wajah dari tulang penipu asli, kami akan menyimpan array tambahan dari dua belas elemen yang menghubungkan masing-masing angka ini dengan hasil asli. Ini dapat digambarkan secara grafis sebagai berikut:


Untuk memformalkan ini dalam bentuk algoritma, kami menggambarkan tahap inisialisasi (memperoleh tabel) dan tahap generasi (mensimulasikan lemparan tulang acak). Kedua langkah ini penting untuk dipertimbangkan dalam algoritma ini dan selanjutnya, karena waktu persiapan harus sangat baik.

Pada tahap inisialisasi, kita mulai dengan mencari kelipatan paling umum dari semua probabilitas yang diberikan untuk tepi tulang (dalam contoh kami, LCL adalah 12). NOC berguna di sini karena sesuai dengan pembagi umum terkecil yang dapat kita gunakan untuk semua fraksi, dan karenanya jumlah wajah dari tulang jujur ​​baru yang akan kita gulung. Setelah menerima NOC ini (kami menyatakan dengan L), kita harus menentukan berapa banyak wajah dari tulang baru akan didistribusikan pada masing-masing wajah dari tulang penipu asli. Dalam contoh kita, wajah dengan probabilitas $$$\ frac {1} {2}$ mendapat enam sisi tulang baru sejak itu $$$\ frac {1} {2} \ kali 12 = 6$ . Begitu pula dengan pesta dengan probabilitas $$$\ frac {1} {3}$ mendapat 4 wajah sejak $$$\ frac {1} {3} \ kali 12 = 4$ . Dalam bentuk yang lebih umum, jika L adalah LCL dari probabilitas, dan $$$p_i$ adalah probabilitas sebuah wajah $$$i$ tulang, lalu kita sorot wajah $$$i$ tulang sharpie asli $$$L \ cdot p_i$ segi tulang yang jujur.

Berikut adalah pseudocode dari algoritma di atas:

Algoritma: mensimulasikan tulang selingkuh dengan tulang jujur

• Inisialisasi :
  
  1. Temukan NOC dari penyebut probabilitas $$$p_0, p_1, ..., p_ {n-1}$ ; nyatakan itu $$$L$
  2. Pilih sebuah array $$$A$ ukurannya $$$L$ untuk membandingkan hasil gulungan tulang yang jujur ​​dengan gulungan tulang asli.
  3. Untuk setiap wajah $$$i$ dari tulang awal, kami melakukan hal berikut dalam urutan apa pun:
     
     1. Kami menetapkan sebagai berikut $$$L \ cdot p_i$ elemen $$$A$ nilai $$$i$ .
• Generasi :
  
  1. Kami menghasilkan lemparan tulang yang jujur $$$L$ - Tulang wajah; panggil wajah $$$S$ .
  2. Kembali $$$A [S]$ .

Algoritma ini mungkin sederhana, tetapi seberapa efisien itu? Generasi gulungan tulang cukup cepat - setiap gulungan tulang membutuhkan $$$O (1)$ runtime untuk menghasilkan gulungan dadu acak menggunakan algoritma sebelumnya, ditambah lagi $$$O (1)$ jam kerja untuk mencari tabel. Ini memberi kami waktu kerja total. $$$O (1)$ .

Namun, langkah inisialisasi bisa sangat mahal. Agar algoritma ini berfungsi, kita perlu mengalokasikan ruang untuk array ukuran NLC penyebut semua fraksi input. Dalam contoh kita ( $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ ), itu adalah 12, untuk nilai input lainnya nilainya bisa buruk secara patologis. Sebagai contoh, mari kita lihat pecahan $$$\ frac {999999} {1.000.000}$ dan $$$\ frac {1} {1000000}$ . NOC penyebut sama dengan satu juta, jadi harus ada satu juta elemen di tabel kami!

Sayangnya, keadaan bisa lebih buruk. Pada contoh sebelumnya, kita setidaknya dapat "berharap" bahwa algoritma ini menghabiskan banyak memori, karena kedua penyebut fraksi sama dengan satu juta. Namun, kami mungkin memiliki banyak probabilitas yang NOC secara signifikan lebih besar daripada masing-masing penyebut individu. Sebagai contoh, mari kita lihat probabilitasnya $$$\ frac {1} {15}$ , $$$\ frac {1} {10}$ , $$$\ frac {5} {6}$ . Di sini NOC penyebutnya adalah 30, yang lebih dari penyebutnya. Desainnya bekerja di sini karena $$$15 = 3 \ kali 5$ , $$$10 = 2 \ kali 5$ , dan $$$6 = 2 \ kali 3$ ; dengan kata lain, setiap penyebut adalah produk dari dua bilangan prima yang dipilih dari kumpulan tiga nilai. Oleh karena itu, NOC mereka adalah produk dari semua bilangan prima ini, karena setiap penyebut harus menjadi pembagi NOC. Jika kami menyamaratakan konstruksi ini dan mempertimbangkan set $$$k$ bilangan prima dan ambil satu fraksi untuk setiap produk berpasangan dari bilangan prima ini, maka NOC akan jauh lebih banyak daripada masing-masing penyebut individu. Bahkan, salah satu batas atas terbaik yang bisa kita dapatkan untuk NOC adalah $$$O (\ prod_ {i = 0} ^ n {d_i})$ dimana $$$d_i$ Apakah penyebutnya $$$i$ probabilitas itu. Ini tidak memungkinkan penggunaan algoritma seperti itu dalam kondisi nyata, ketika probabilitasnya tidak diketahui sebelumnya, karena memori yang diperlukan untuk menyimpan tabel ukuran $$$O (\ prod_ {i = 0} ^ n {d_i})$ , Dapat dengan mudah berubah menjadi lebih dari volume yang dapat ditampung dalam RAM.

Dengan kata lain, dalam banyak kasus, algoritma ini berperilaku baik. Jika semua probabilitas sama, maka semua probabilitas yang diperoleh pada input sama $$$\ frac {1} {n}$ untuk beberapa orang $$$n$ . Kemudian penyebut NOC sama $$$n$ , sebagai akibatnya, tulang yang jujur ​​akan terlempar $$$n$ wajah, dan setiap segi dari tulang asli akan sesuai dengan satu segi dari tulang jujur. Oleh karena itu, waktu inisialisasi adalah $$$O (n)$ . Ini dapat digambarkan secara grafis sebagai berikut:


Ini memberi kami informasi berikut tentang algoritme:

Algoritma	Waktu inisialisasi		Waktu generasi		Memori yang ditempati
	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk
Tulang tulang lebih jujur	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$

Detail penting lainnya tentang algoritme ini: mengasumsikan bahwa kami akan menerima probabilitas yang mudah dalam bentuk pecahan dengan penyebut yang baik. Jika probabilitas ditetapkan sebagai ganda IEEE-754, maka pendekatan ini cenderung menjadi bencana karena kesalahan pembulatan kecil; Bayangkan kita memiliki probabilitas 0,25 dan 0,250000000001! Oleh karena itu, pendekatan ini mungkin lebih baik untuk tidak digunakan, kecuali dalam kasus khusus ketika probabilitas berperilaku baik dan ditentukan dalam format yang sesuai dengan operasi dengan angka rasional.

Simulasi koin asimetris

Penjelasan kami tentang primitif acak sederhana (tulang jujur) menyebabkan algoritma simulasi kecurangan tulang sederhana tapi berpotensi sangat tidak efektif. Mungkin studi tentang primitif acak sederhana lainnya akan menjelaskan pendekatan lain untuk memecahkan masalah ini.

Tugas sederhana namun mengejutkan bermanfaat adalah untuk mensimulasikan koin asimetris menggunakan generator angka acak. Jika kita memiliki koin dengan probabilitas seekor elang $$$p_ {head}$ , lalu bagaimana kita bisa mensimulasikan lemparan koin asimetris seperti itu?

Sebelumnya, kami mengembangkan satu pendekatan intuitif: partisi interval $$$[0, 1)$ pada urutan daerah tersebut sehingga ketika memilih nilai acak dalam interval, itu muncul di beberapa daerah dengan probabilitas yang sama dengan ukuran wilayah. Untuk mensimulasikan koin asimetris menggunakan nilai acak yang terdistribusi seragam dalam interval $$$[0, 1)$ kita harus istirahat intervalnya $$$[0, 1)$ sebagai berikut:


Dan kemudian menghasilkan nilai acak terdistribusi seragam dalam interval $$$[0, 1)$ untuk melihat area apa itu. Untungnya, kami hanya memiliki satu titik perpecahan, sehingga sangat mudah untuk menentukan di area mana titik tersebut berada; jika nilainya kurang $$$p_ {head}$ , maka elang jatuh pada koin, jika tidak - ekor. Kodesemu:

Algoritma: mensimulasikan koin asimetris

1. Hasilkan nilai acak terdistribusi seragam dalam interval $$$[0, 1)$ .
2. Jika $$$x <p_ {heads}$ , kembalikan "elang".
3. Jika $$$x \ ge p_ {head}$ , kembalikan ekor.

Karena kita dapat menghasilkan nilai acak yang terdistribusi secara seragam dalam interval $$$[0, 1)$ tepat waktu $$$O (1)$ , dan kami juga dapat membandingkan bilangan real untuk $$$O (1)$ , maka algoritma ini berjalan dalam waktu $$$O (1)$ .

Mensimulasikan tulang yang jujur ​​menggunakan koin asimetris

Dari diskusi sebelumnya, kita tahu bahwa kita dapat mensimulasikan tulang selingkuh menggunakan tulang jujur, jika kita menganggap bahwa kita siap untuk menghabiskan ruang memori tambahan. Karena kita dapat menganggap koin asimetris sebagai tulang bilateral yang curang, ini berarti bahwa kita dapat mensimulasikan koin asimetris dengan bantuan tulang yang jujur. Sangat menarik bahwa kebalikannya juga dapat dilakukan - untuk mensimulasikan tulang yang jujur ​​menggunakan koin asimetris.Desainnya sederhana, elegan dan dapat dengan mudah digeneralisasikan untuk mensimulasikan tulang selingkuh menggunakan berbagai koin asimetris.

Desain untuk mensimulasikan koin asimetris membagi intervalnya$$[ 0 , 1 ) menjadi dua area - area "elang" dan area "ekor" berdasarkan probabilitas elang jatuh ke tulang. Kita telah melihat trik serupa yang digunakan untuk mensimulasikan kejujuran$[0, 1)$$$n tulang -face: Interval$n$$$[ 0 , 1 ) dibagi menjadi$[0, 1)$$$∎ daerah yang sama. Misalnya, ketika melempar tulang tetrahedral, kami mendapat pemisahan berikut:$n$


Sekarang anggaplah kita tertarik untuk mensimulasikan gulungan dari tulang yang jujur ​​ini menggunakan satu set koin asimetris. Salah satu solusinya adalah sebagai berikut: bayangkan kita mengitari area ini dari kiri ke kanan, setiap kali bertanya apakah kita ingin berhenti di area saat ini, atau jika kita akan pindah. Sebagai contoh, katakanlah kita ingin memilih secara acak salah satu area ini. Mulai dari area paling kiri, kita akan membalik koin asimetris, yang memberi tahu kita apakah kita harus berhenti di area ini, atau terus bergerak. Karena kita perlu memilih dari semua bidang ini secara seragam dengan probabilitas$$14 , maka kita bisa melakukan ini dengan melemparkan koin asimetris, elang yang jatuh dengan probabilitas$\frac{1}{4}$$$$\frac{1}{4}$ .Jika elang jatuh, maka kita berhenti di daerah saat ini. Kalau tidak, kami pindah ke area berikutnya.

Jika koin jatuh ke atas, maka kita menemukan diri kita di daerah kedua dan lagi bertanya apakah kita harus memilih daerah ini lagi atau terus bergerak. Anda mungkin berpikir bahwa untuk ini kita harus melempar koin lain dengan probabilitas seekor elang$$14 , tetapi sebenarnya ini tidak benar! Untuk melihat kekurangan dalam alasan ini, kita harus sampai pada situasi yang ekstrem - jika di setiap wilayah kita melempar koin tempat elang jatuh dengan probabilitas$\frac{1}{4}$$$14 , yaitu, ada kemungkinan kecil bahwa di setiap area koin akan jatuh ekor, yaitu, kita harus meninggalkan semua area. Saat bergerak melalui daerah, kita harus terus meningkatkan kemungkinan elang jatuh pada koin. Dalam situasi yang ekstrem, jika kita menemukan diri kita di area terakhir, maka koin harus memiliki seekor elang dengan probabilitas$\frac{1}{4}$$$1 , karena jika kita menolak semua area sebelumnya, maka keputusan yang tepat adalah berhenti di area terakhir. Untuk menentukan probabilitas di mana koin asimetris kita harus melempar rajawali setelah melewati area pertama, kita perlu memperhatikan bahwa setelah melewati area pertama hanya ada tiga yang tersisa. Ketika kita menggulung tulang yang jujur, kita perlu masing-masing dari ketiga bidang ini untuk dipilih dengan probabilitas$1$

$$$\frac{1}{3}$ . Oleh karena itu, secara naluriah nampaknya kita harus memiliki tulang kedua tempat elang jatuh dengan probabilitas $$$\frac{1}{3}$ . Dengan menggunakan alasan yang sama, dapat dipahami bahwa ketika sebuah ekor muncul di wilayah kedua kisi di wilayah ketiga, koin harus dijatuhkan oleh elang dengan probabilitas. $$12 , dan di area terakhir - dengan probabilitas$\frac{1}{2}$$$$1$ .

Pemahaman intuitif ini membawa kita ke algoritma berikut. Perhatikan bahwa kami tidak membahas kebenaran atau kekeliruan algoritma ini; segera kita akan melakukannya.

Algoritma: mensimulasikan tulang yang jujur ​​menggunakan koin asimetris

1. Untuk $$i = 0 hingga$i = 0$$$$n - 1$ :
   
   1. Lempar koin asimetris dengan probabilitas elang $$$\frac{1}{n - i}$ .
   2. Jika elang jatuh, maka kembalilah $$$i$ .

Algoritma ini sederhana dan, dalam kasus terburuk, berjalan dalam waktu. $$$O (n)$ .Tetapi bagaimana kita memeriksa apakah itu benar? Untuk mengetahuinya, kita membutuhkan teorema berikut:

Teorema: algoritma di atas mengembalikan sisi$$saya dengan probabilitas$i$$$1n untuk semua yang dipilih$\frac{1}{n}$$$$i$ .

Bukti: pertimbangkan konstanta apa saja$$$n \ge 0$ . Menggunakan induksi yang kuat, kami membuktikan bahwa masing-masing $$n menghadapi probabilitas seleksi$n$$$$\frac{1}{n}$ .

Sebagai contoh kita, kita menunjukkan wajah itu $$0 dadu memiliki kemungkinan pilihan$0$$$$\frac{1}{n}$ . Tapi ini secara langsung mengikuti dari algoritma itu sendiri - kita memilih wajah 0 jika pada koin asimetris dengan probabilitas elang $$$\frac{1}{n}$ , $$$\frac{1}{n}$ .

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{1}{n - k}$ . $$$k$ $$$\frac{1}{n}$ , , $$k diberikan sebagai$k$$$$\frac{k}{n}$ . Ini berarti bahwa kemungkinan algoritma tidak memilih yang pertama $$wajah k sama dengan$k$$$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ . Artinya, kemungkinan memilih wajah $$k diberikan sebagai$k$$$n - kn 1n - k =1n , yang akan ditampilkan. Dengan demikian, setiap wajah tulang dipilih secara merata dan acak.$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$

Tentu saja, algoritma ini sangat tidak efisien - menggunakan teknik pertama, kita dapat mensimulasikan gulungan dadu yang jujur ​​dalam waktu $$$O(1)$ ! Tetapi algoritma ini dapat digunakan sebagai batu loncatan ke algoritma yang cukup efektif untuk mensimulasikan tulang yang curang menggunakan koin asimetris.

Simulasi tulang shuler menggunakan koin asimetris

Algoritma yang disajikan di atas menarik karena memberikan kita kerangka kerja sederhana untuk mensimulasikan tulang menggunakan set koin. Kita mulai dengan melempar koin untuk menentukan apakah akan memilih segi pertama dari tulang atau pindah ke yang lain. Dalam proses ini, kita perlu secara hati-hati menangani skala probabilitas yang tersisa.

Mari kita lihat bagaimana Anda dapat menggunakan teknik ini untuk mensimulasikan lemparan tulang yang curang. Kami menggunakan contoh kami dengan probabilitas$$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . Dia, jika Anda tidak ingat, membagi intervalnya $$[ 0 , 1 ) sebagai berikut:$[0, 1)$


Sekarang mari kita berpikir tentang bagaimana mensimulasikan tulang selingkuh menggunakan koin asimetris. Kita bisa mulai dengan melempar koin dengan probabilitas seekor elang$$12 untuk menentukan apakah kita harus mengembalikan wajah 0. Jika elang jatuh di koin ini, maka baiklah! Kita sudah selesai. Kalau tidak, kita perlu melempar koin lain untuk memutuskan apakah akan memilih sisi berikutnya. Seperti sebelumnya, terlepas dari kenyataan bahwa segi selanjutnya memiliki kemungkinan pilihan$\frac{1}{2}$$$13 , kita tidak ingin melempar koin di mana rajawali turun dengan probabilitas$\frac{1}{3}$$$13 , karena setengah dari "massa" probabilitas dibuang ketika kami tidak memilih jalur$\frac{1}{3}$$$$\frac{1}{2}$ . Faktanya, karena setengah dari massa probabilitas telah menghilang, maka jika kita menormalkan kembali probabilitas yang tersisa, kita akan mendapatkan probabilitas yang diperbarui: $$$\frac{2}{3}$ , $$$\frac{1}{6}$ , $$$\frac{1}{6}$ . Karena itu, koin kedua harus dilemparkan dengan probabilitas $$$\frac{2}{3}$ . Jika koin ini juga berekor, maka kita harus memilih antara dua sisi $$$\frac{1}{12}$ . Karena pada tahap ini kita akan disingkirkan $$56 massa probabilitas, maka kita bisa menormalkan kembali probabilitas partai$\frac{5}{6}$$$112 sehingga setiap orang memiliki kesempatan$\frac{1}{12}$$$12 tetes elang, yaitu, koin ketiga akan memiliki probabilitas$\frac{1}{2}$$$$\frac{1}{2}$ . Koin terakhir, jika pernah sampai padanya, harus melempar rajawali dengan probabilitas $$1 karena ini adalah area terbaru. Untuk meringkas, probabilitas koin adalah sebagai berikut:$1$

1. Gulungan pertama: $$$\frac{1}{2}$
2. Gulungan kedua: $$$\frac{2}{3}$
3. Gulungan ketiga: $$$\frac{1}{2}$
4. Gulungan keempat: $$$1$

Mungkin intuitif dari mana angka-angka ini berasal, tetapi untuk mengubah seleksi menjadi suatu algoritma, kita harus membuat konstruksi formal dari pilihan probabilitas. Idenya akan menjadi sebagai berikut - pada setiap tahap kita mengingat sisa massa probabilitas. Pada awalnya, sebelum koin pertama dilemparkan, itu sama dengan$$$1$ . Setelah melempar koin pertama $$$1 - p_0$ . Setelah melempar koin kedua $$$1 - p_0 - p_1$ . Lebih umum setelah lemparan $$k sisa dari probabilitas adalah$k$$$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . Setiap kali kami melempar koin untuk menentukan apakah akan memilih suatu area atau tidak $$k , akibatnya kita melempar koin, probabilitas elang jatuh yang sama dengan fraksi dari probabilitas yang tersisa ditempati oleh probabilitas$k$$$p k , yang didefinisikan sebagai$p_k$$$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ . Ini memberi kami algoritma berikut untuk menyontek simulasi tulang dengan satu set koin asimetris (kami akan membuktikan kebenaran dan runtime tepat di bawah):

Algoritma: Tulang Schuler dari koin asimetris

• Inisialisasi :
  
  1. Kami menjaga probabilitas $$p i untuk digunakan di masa depan.$p_i$
• Generasi :
  Set$$m a s s = 1 For$mass = 1$
  $$i = 0 hingga$i = 0$$$$n - 1$ :
  
  1. Lempar koin asimetris dengan probabilitas elang $$$\frac{p_i}{mass}$ .
  2. Jika elang jatuh, maka kembalilah $$$i$ .
  3. Kalau tidak, kita atur $$$mass = mass - p_i$

Dari sudut pandang intuitif, ini logis, tetapi apakah secara matematis benar? Untungnya, jawabannya adalah ya berkat generalisasi dari bukti di atas:

Teorema: algoritma yang ditunjukkan di atas mengembalikan wajah$$saya dengan probabilitas$i$$$p i untuk setiap yang dipilih$p_i$$$$i$ .

Bukti: pertimbangkan konstanta apa saja$$$n \ge 0$ . , $$$n$ $$$p_i$ .

, $$$0$ $$$p_0$ . $$$0$ , , $$$\frac{p_0}{mass}$ . $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ . Ini berarti kemungkinan keseluruhan memilih wajah $$k diberikan sebagai$k$$$( 1 - ∑ k - 1 i = 0 p i ) p k1 - ∑ k - 1 i = 0 p i =pk, sesuai kebutuhan.$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$

Sekarang mari kita evaluasi kompleksitas waktu dari algoritma ini. Kita tahu bahwa waktu inisialisasi mungkin$$Θ ( 1 ) jika kita menyimpan salinan permukaan array probabilitas input, tetapi mungkin ada$\Theta(1)$$$Θ ( n ) sehingga kita dapat menyimpan versi array kita sendiri (kalau-kalau fungsi panggilan ingin mengubahnya nanti). Generasi dari hasil lemparan tulang mungkin diperlukan dalam kasus terburuk$\Theta(n)$$$Θ ( n ) melempar, dan hanya satu lemparan terbaik.Namun, setelah refleksi, menjadi jelas bahwa jumlah lemparan koin yang diperlukan sangat dipengaruhi oleh distribusi yang masuk. Dalam kasus terbaik, kita akan memiliki distribusi probabilitas di mana seluruh massa probabilitas terkonsentrasi di tepi pertama tulang, dan semua probabilitas lainnya adalah nol. Dalam hal ini, satu lemparan koin sudah cukup untuk kita. Dalam kasus terburuk, seluruh massa probabilitas terkonsentrasi di bagian paling akhir dari tulang, dan pada semua wajah lainnya sama dengan nol. Dalam hal ini, kita harus melempar$\Theta(n)$

$$n koin Kami dapat dengan jelas dan matematis menggambarkan jumlah lemparan koin yang diharapkan dalam algoritma ini. Mari kita bayangkan sebuah variabel acak$n$

$$X , menunjukkan jumlah lemparan koin untuk setiap eksekusi algoritma ini untuk distribusi tertentu. Yaitu$X$$$P [ X = 1 ] adalah probabilitas untuk menyelesaikan algoritma itu cukup untuk melempar satu koin,$\mathbb{P}[X = 1]$$$P [ X = 2 ] - probabilitas bahwa algoritma akan melempar dua koin, dll. Dalam hal ini, jumlah lemparan koin yang diharapkan untuk algoritme kami ditentukan olehekspektasi matematis$\mathbb{P}[X = 2]$ $$X dilambangkan dengan$X$$$$\mathbb{E}[X]$ . ,

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

$$$\mathbb{P}[X = i]$ ? - . $$$0$ , . $$$1$ , — , $$$0$ , , $$$1$ . , $$$i$ , $$$i + 1$ : $$$i$ , , $$$i - 1$ , , , $$$i$ . , $$$i$ $$$p_i$ , ,

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]} = \sum_{i = 1}^n{i \cdot p_{i - 1}} = \sum_{i = 1}^n{((i - 1) p_{i - 1} + p_{i - 1})} = \sum_{i = 1}^n{((i - 1) p_{i - 1})} + \sum_{i = 1}^n{p_{i - 1}}$$

Perhatikan bahwa dalam penyederhanaan terakhir, istilah pertama adalah setara $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ yang setara $$$\ mathbb {E} [p]$ , hasil yang diharapkan dari lemparan dadu! Apalagi istilah kedua sama dengan $$$1$ karena ini adalah jumlah dari semua probabilitas. Ini artinya $$$\ mathbb {E} [X] = \ mathbb {E} [p] + 1$ . Artinya, jumlah yang diharapkan dari gulungan koin sama dengan satu ditambah harapan matematika dari gulungan mati!

Algoritma	Waktu inisialisasi		Waktu generasi		Memori yang sibuk
	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk
Tulang tulang lebih jujur	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Tulang Schuler dari koin asimetris	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$

Generalisasi koin asimetris: mensimulasikan tulang selingkuh

Dalam contoh yang ditunjukkan di atas, kami dapat secara efektif mensimulasikan koin asimetris, karena kami hanya perlu memperhitungkan satu titik perpecahan. Bagaimana kita bisa menggeneralisasikan ide ini secara efektif ke tulang yang curang di mana jumlah wajah bisa berubah-ubah?

Seperti yang Anda lihat, koin asimetris adalah tulang yang curang, dengan hanya dua wajah. Oleh karena itu, kita dapat melihat koin asimetris hanya sebagai kasus khusus dari masalah yang lebih umum yang ingin kita pecahkan. Saat memecahkan masalah koin asimetris, kami membagi intervalnya $$$[0, 1)$ menjadi dua area - satu untuk elang, yang kedua untuk ekor - dan kemudian untuk menemukan area kita menggunakan fakta bahwa hanya ada satu titik perpecahan. Jika kita memiliki tulang bermuka n, maka akan ada lebih banyak daerah, dan oleh karena itu beberapa titik pemisah. Anggaplah, misalnya, bahwa kita memiliki tulang tujuh sisi dengan probabilitas $$$\ frac {1} {4}$ , $$$\ frac {1} {5}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {8}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ , $$$\ frac {1} {10}$ . Jika kita ingin membagi interval $$$[0, 1)$ menjadi tujuh bagian, maka kita melakukannya sebagai berikut:


Perhatikan di mana area ini berada. Area pertama dimulai dengan $$$0$ dan berakhir $$$\ frac {1} {4}$ . Area kedua dimulai dengan $$$\ frac {1} {4}$ dan berakhir di $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ . Lebih umum, jika probabilitasnya sama $$$p_0, p_1, ..., p_ {n - 1}$ , maka area akan menjadi interval $$$[0, p_0)$ , $$$[p_0, p_0 + p_1)$ , $$$[p_0 + p_1, p_0 + p_1 + p_2)$ dll. Itulah area $$$i$ dibatasi oleh interval

$$

$$[\ sum_ {j = 0} ^ {i - 1} {p_j}, \ sum_ {j = 0} ^ {i} {p_j})$$

Perhatikan bahwa perbedaan antara kedua nilai ini adalah $$$p_i$ , yaitu, total wilayah wilayah itu $$$p_i$ sesuai kebutuhan.

Sekarang kita tahu di mana lokasinya. Jika kita ingin memilih nilai acak yang terdistribusi secara seragam $$$x$ dalam jangkauan $$$[0, 1)$ , lalu bagaimana kita menentukan dalam interval berapa jatuh? Jika kita menggunakan algoritme koin asimetris sebagai titik awal, idenya adalah sebagai berikut: mulai dari titik akhir wilayah pertama, terus bergerak ke atas melalui semua area hingga kami menemukan titik akhir yang nilainya lebih besar dari nilai $$$x$ . Jika kita melakukan ini, kita akan menemukan wilayah pertama yang mengandung titik $$$x$ , dan karena itu nilai kami. Misalnya, jika kita memilih nilai acak $$$x = \ frac {27} {40}$ , lalu lakukan pencarian berikut:


Dari mana kita dapat menyimpulkan bahwa facet 3 jatuh pada dadu dengan pengindeksan dari awal.

Algoritma pemindaian linier seperti itu akan memberi kita algoritma waktu $$$O (n)$ untuk menemukan tepi tulang yang dibuang. Namun, kami dapat secara signifikan meningkatkan waktu pelaksanaannya dengan menggunakan pengamatan berikut: serangkaian titik akhir daerah membentuk urutan yang meningkat (karena kami selalu menambah lebih banyak probabilitas, tidak ada yang bisa kurang dari nol). Oleh karena itu, kami ingin menjawab pertanyaan berikut: memiliki urutan peningkatan nilai dan beberapa pos pemeriksaan, kami perlu menemukan nilai pertama dalam interval yang benar-benar lebih besar daripada pos pemeriksaan. Ini adalah waktu yang tepat untuk menggunakan pencarian biner ! Sebagai contoh, inilah pencarian biner pada larik di atas untuk menemukan area tempat ia berada $$$x = \ frac {39} {40}$ :


Ini memberi kita suatu algoritma dari waktu ke waktu. $$$\ Theta (\ log n)$ untuk mengikat nilai acak terdistribusi seragam dalam interval $$$[0, 1)$ ke tepi tulang yang ditinggalkan. Selain itu, waktu pra-pemrosesan cukup untuk membangun tabel titik akhir $$$\ Theta (n)$ ; kami hanya menghitung jumlah sebagian probabilitas saat kami naik.

Algoritma ini kadang-kadang disebut algoritma pemilihan roda roulette karena memilih area acak menggunakan teknik yang mirip dengan roda roulette - melempar bola ke dalam interval dan mengamati di mana ia berhenti. Dalam pseudo-code, algoritmenya terlihat seperti ini:

Algoritma: pemilihan roda roulette

• Inisialisasi :
  
  1. Pilih sebuah array $$$A$ ukurannya $$$n$
  2. Kami mengatur $$$A [0] = p_0$ .
  3. Untuk setiap probabilitas $$$i$ dari $$$1$ sebelumnya $$$n - 1$ :
     
     1. Kami mengatur $$$A [i] = A [i - 1] + p_i$
  
  
• Generasi :
  
  1. Hasilkan nilai acak yang didistribusikan secara seragam $$$x$ dalam jangkauan $$$[0, 1)$
  2. Menggunakan pencarian biner, kami menemukan indeks $$$i$ elemen terkecil $$$A$ yang kurang $$$x$ .
  3. Kembali $$$i$ .

Perbandingan antara algoritma ini dan yang diberikan sebelumnya terlihat cukup mengesankan:

Algoritma	Waktu inisialisasi		Waktu generasi		Memori yang sibuk
	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk
Tulang tulang lebih jujur	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Tulang Schuler dari koin asimetris	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Pemilihan Roda Roulette	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$

Jelas, kami sekarang memiliki algoritma yang jauh lebih baik daripada yang asli. Kebijaksanaan probabilitas hanya pada awalnya tampak menjanjikan, tetapi pendekatan baru ini, berdasarkan nilai terus menerus dan pencarian biner, terlihat jauh lebih baik. Namun, masih dimungkinkan untuk meningkatkan indikator ini dengan penggunaan cerdas serangkaian teknik hibrida, yang akan kita bahas di bawah ini.

Detail yang menarik dari algoritma ini adalah meskipun penggunaan pencarian biner menjamin waktu terburuk untuk menghasilkan angka acak $$$O (\ log n)$ , itu juga tidak memungkinkan pencarian lebih cepat; yaitu, waktu pembuatan juga akan sama $$$\ Omega (\ log n)$ . Bisakah ini diperbaiki? Ternyata kamu bisa.

Misalkan kita beralih dari pencarian biner pada daftar probabilitas kumulatif untuk menggunakan pohon pencarian biner . Sebagai contoh, dengan memiliki set probabilitas yang diberikan di atas, kita dapat membangun pohon pencarian biner berikut untuk distribusi kumulatifnya:


Sekarang, jika kita ingin mensimulasikan gulungan tulang, kita dapat menghasilkan angka yang terdistribusi secara merata dalam interval $$$[0, 1)$ dan kemudian lihat interval apa yang ada di pohon pencarian biner (BST) ini. Karena ini adalah pohon pencarian biner seimbang, waktu pencarian terbaik adalah $$$O (1)$ dan yang terburuk $$$O (\ log n)$ .

Namun, dengan asumsi bahwa kita tahu lebih banyak tentang distribusi probabilitas, kita dapat melakukan jauh lebih baik. Sebagai contoh, misalkan probabilitas kita sama $$$\ frac {99} {100}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ , $$$\ frac {1} {600}$ . Yaitu, distribusi probabilitas sangat miring, dan hampir seluruh massa probabilitas terkonsentrasi pada satu wajah. Kami dapat membangun BST seimbang untuk probabilitas ini:


Meskipun pohon pencarian biner ini seimbang sempurna, itu tidak sangat cocok untuk tugas kita. Karena kita tahu bahwa dalam 99 dari 100 kasus, nilai acak akan berada dalam kisaran $$$[0, \ frac {99} {100})$ , maka tidak ada gunanya menyimpan node untuk interval ini di mana ia berada sekarang. Bahkan, ini berarti bahwa hampir setiap saat kita akan membuat dua perbandingan yang tidak perlu dengan area biru dan kuning. Karena dengan probabilitas yang sangat tinggi kita harus menjadi yang pertama untuk memeriksa interval terbesar, akan logis untuk tidak seimbang pohon sehingga membuat kasus rata-rata jauh lebih baik karena yang tersisa. Ini ditunjukkan di sini:


Sekarang kami kemungkinan besar akan menyelesaikan pencarian dengan segera menemukan area yang diinginkan setelah upaya pertama. Dalam hal yang sangat tidak mungkin bahwa area yang diinginkan ada di sisanya $$$(\ frac {99} {100}, 1]$ kita dengan tenang turun ke ujung pohon, yang sebenarnya seimbang.

Dalam bentuk umum, kami ingin menyelesaikan masalah berikut:

Dengan serangkaian probabilitas tertentu, temukan pohon pencarian biner untuk probabilitas ini yang meminimalkan waktu pencarian yang diharapkan.

Untungnya, masalah ini dipelajari dengan sangat baik dan disebut masalah pohon pencarian biner optimal . Ada banyak algoritma untuk menyelesaikan masalah ini; diketahui bahwa solusi pasti dapat ditemukan tepat waktu $$$O (n ^ 2)$ menggunakan pemrograman dinamis , dan ada algoritma waktu linear yang baik yang dapat menemukan solusi perkiraan. Selain itu, untuk mendapatkan faktor konstan dari solusi optimal, Anda dapat menggunakan struktur data splay tree (memperluas tree) (pohon pencarian biner penyeimbang sendiri).

Sangat menarik bahwa kasus terbaik untuk perilaku pohon pencarian biner yang dioptimalkan seperti itu terjadi ketika distribusi probabilitas sangat miring, karena kita dapat dengan mudah memindahkan node yang berisi sebagian besar massa probabilitas ke akar pohon, dan kasus terburuk adalah ketika distribusi seimbang, karena dengan demikian pohon harus lebar dan dangkal. Ini adalah kebalikan dari perilaku algoritma sebelumnya, di mana yang jujur ​​digunakan untuk mensimulasikan tulang yang curang!

Dalam kasus terbaik, kami memiliki tulang curang di mana satu wajah selalu rontok (yaitu, ia memiliki probabilitas 1, dan semua wajah lainnya memiliki probabilitas 0). Ini berlebihan berlebihan dari contoh kami sebelumnya, tetapi dalam kasus ini, pencarian akan selalu berakhir setelah upaya pertama. Dalam kasus terburuk, semua probabilitas sama, dan kami mendapatkan pencarian BST standar. Kami datang sebagai berikut:

Algoritma	Waktu inisialisasi		Waktu generasi		Memori yang sibuk
	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk	Yang terbaik	Yang terburuk
Tulang tulang lebih jujur	$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ Theta (n)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
Tulang Schuler dari koin asimetris	$$$\ Theta (n)$		$$$\ Theta (1)$	$$$\ Theta (n)$	$$$\ Theta (n)$
Pemilihan Roda Roulette	$$$\ Theta (n)$		$$$\ Theta (\ log n)$		$$$\ Theta (n)$
Pilihan roda roulette optimal	$$$O (n ^ 2)$		$$$\ Theta (1)$	$$$O (\ log n)$	$$$\ Theta (n)$

Lempar dart

Sejauh ini kami telah mempertimbangkan dua primitif yang membantu kami membangun algoritma untuk mensimulasikan tulang yang curang: tulang jujur ​​dan koin asimetris. Hanya menggunakan tulang yang jujur, kami sampai pada algoritma (sayangnya, tidak praktis) untuk menipu tulang, dan mulai dengan koin asimetris, kami dapat menemukan algoritma cepat untuk menyontek tulang. Bisakah kedua pendekatan ini digabungkan untuk membuat algoritma berdasarkan pada tulang yang jujur ​​dan koin asimetris? Ternyata ya, dan ternyata algoritma yang dihasilkan lebih baik dari kedua pendekatan ini.

Sampai saat ini, kami memvisualisasikan intervalnya $$$[0, 1)$ dan probabilitas wajah tulang sebagai interval satu dimensi. Kedua algoritma ini memilih beberapa titik dalam interval $$$[0, 1)$ dan meletakkannya di segmen garis lurus, yang panjangnya sesuai dengan beberapa jenis probabilitas. Semakin lama segmen yang kita buat, semakin besar kemungkinan memilih segmen ini. Tetapi bagaimana jika Anda mencoba berpikir tidak dalam satu tetapi dalam dua dimensi? Bagaimana jika kita mengambil probabilitas $$$p_i$ bukan panjang segmen garis lurus, tetapi area persegi panjang?

Mari kita mulai dengan kembali ke contoh sebelumnya dengan probabilitas $$$\ frac {1} {2}$ , $$$\ frac {1} {3}$ , $$$\ frac {1} {12}$ , $$$\ frac {1} {12}$ . Kami mewakili probabilitas ini dalam bentuk persegi panjang dengan lebar $$$w$ (dengan beberapa sewenang-wenang $$$w> 0$ ) dan tinggi $$$p_i$ (Dengan demikian, luas persegi panjang akan sama dengan $$$w \ cdot p_i$ ):


Perhatikan bahwa total luas persegi panjang ini adalah $$$w$ sejak area

$$

$$\ sum_ {i = 0} ^ {n - 1} {w p_i} = w \ sum_ {i = 0} ^ {n - 1} {p_i} = w$$

Sekarang anggaplah kita menggambar persegi panjang terikat di sekitar persegi panjang yang lebarnya $$$4w$ (Karena ada empat segi empat), dan tingginya $$$\ frac {1} {2}$ (Karena persegi panjang tertinggi memiliki ketinggian $$$\ frac {1} {2}$ ):


Kita dapat membayangkan bahwa persegi panjang ini dibagi menjadi lima area - empat area sesuai dengan probabilitas yang berbeda, dan satu area menunjukkan ruang yang tidak digunakan. Mengambil istirahat ini, kita bisa memikirkan algoritma simulasi lemparan dadu acak sebagai permainan anak panah. Misalkan kita melempar panah (terdistribusi sempurna) pada target ini. Jika jatuh ke ruang yang tidak digunakan, maka kita mengeluarkan panah dan melemparkannya lagi, mengulangi prosesnya sampai kita masuk ke salah satu persegi panjang. Karena semakin besar probabilitas, semakin besar persegi panjangnya, semakin besar kemungkinan melempar tepi tulang, semakin tinggi kemungkinan jatuh ke dalam persegi panjangnya. Bahkan, jika kita menetapkan kondisi bahwa kita telah jatuh ke dalam semacam persegi panjang, maka kita mendapatkan yang berikut:

$$

$$\ mathbb {P} [\ mbox {tekan segi empat untuk sisi i} | \ mbox {tekan beberapa persegi panjang}] = \ frac {\ mbox {area persegi panjang untuk i}} {\ mbox {total area persegi panjang}} = \ frac {w p_i} {w} = p_i$$

Dengan kata lain, ketika kita akhirnya jatuh ke dalam semacam persegi panjang dengan panah yang didistribusikan secara merata, kita memilih persegi panjang wajah $$$i$ tulang curang dengan probabilitas $$$p_i$ , yaitu, dengan probabilitas yang kita butuhkan! Artinya, jika kita dapat menemukan beberapa cara yang efektif untuk mensimulasikan melempar anak panah acak pada persegi panjang ini, maka kita akan memiliki cara yang efektif untuk mensimulasikan melempar dadu acak.

Salah satu cara untuk mensimulasikan lemparan panah di persegi panjang ini adalah untuk memilih dua nilai yang didistribusikan secara merata dalam interval $$$[0, 1)$ menskalakannya dengan lebar dan tinggi yang sesuai, diikuti dengan memeriksa area di bawah panah. Namun, ini menyebabkan masalah yang sama yang kami miliki ketika kami mencoba menentukan wilayah satu dimensi di mana nilai acak berada. Namun, ada serangkaian pengamatan yang benar-benar luar biasa, berkat penentuan tempat dampak dapat menjadi tugas yang sederhana, jika tidak sepele.

Pengamatan pertama: kami menunjukkan bahwa lebar persegi panjang ini dapat dipilih secara sewenang-wenang, karena semuanya memiliki lebar yang sama. Ketinggian, tentu saja, tergantung pada probabilitas wajah tulang. Namun, jika kita secara merata skala semua ketinggian dengan beberapa bilangan real positif $$$h$ , maka area relatif dari semua persegi panjang akan sama. Bahkan, untuk setiap bilangan real positif $$$h$ luas total semua persegi panjang setelah menskalakan ketinggiannya $$$h$ dihitung sebagai

$$

$$\ sum_ {i = 0} ^ {n - 1} {w h p_i} = w h \ sum_ {i = 0} ^ {n - 1} {p_i} = w h$$

Sekarang kita akan mempertimbangkan kemungkinan memilih persegi panjang individu, membatasi diri kita pada kondisi bahwa kita pasti mencapai semacam persegi panjang. Dengan menggunakan perhitungan yang sama, kita mendapatkan yang berikut:

$$

$$\ mathbb {P} [\ mbox {tekan segi empat untuk sisi i} | \ mbox {tekan beberapa persegi panjang}] = \ frac {\ mbox {area persegi panjang untuk i}} {\ mbox {total area persegi panjang}} = \ frac {w h p_i} {w h} = p_i$$

Faktanya, probabilitas untuk memilih persegi panjang tunggal tidak berubah jika kita menskalakannya secara linear dan merata.

Karena kita dapat memilih faktor penskalaan yang cocok, mengapa kita tidak menskala persegi panjang ini sehingga ketinggian kotak pembatas selalu 1? Karena ketinggian kotak pembatas ditentukan oleh nilai maksimum $$$p_i$ input probabilitas, maka kita bisa mulai dengan menskalakan masing-masing persegi dengan faktor $$$\ frac {1} {p_ {max}}$ dimana $$$p_ {maks}$ Apakah probabilitas maksimum dari semua probabilitas input. Berkat ini, kita mendapatkan tinggi persegi panjang 1. Demikian pula, karena kita dapat memilih lebar sembarang untuk persegi panjang, mari kita ambil lebar 1. Ini berarti bahwa untuk $$$n$ probabilitas lebar total kotak pembatas adalah $$$n$ , dan tinggi totalnya adalah 1. Ini ditunjukkan pada gambar:


Sekarang kita siap untuk berpikir tentang bagaimana kita bisa melempar panah acak ke dalam persegi panjang dan menentukan apa yang jatuh ke dalamnya. Yang paling penting adalah kita bisa membagi persegi panjang sehingga tidak terdiri dari beberapa persegi panjang yang lebih kecil dan ruang kosong dengan bentuk yang aneh. Sebaliknya, area tersebut dipotong menjadi satu set $$$2n$ persegi panjang, dua di masing-masing $$$n$ probabilitas input. Ini ditunjukkan di sini:


Perhatikan bagaimana bentuk persegi panjang ini. Untuk setiap permukaan tulang penipu, kami memiliki satu kolom dengan lebar 1 dan tinggi 1, dibagi menjadi dua ruang - setengah ruang "ya" yang sesuai dengan persegi panjang ukuran ini, dan setengah ruang "tidak" sesuai dengan bagian kolom yang tersisa.

Sekarang mari kita pikirkan bagaimana kita bisa melempar panah. Anak panah yang seragam sempurna dilemparkan ke dalam persegi panjang ini akan memiliki komponen $$$x$ dan $$$y$ . Di sini komponen $$$x$ yang harus dalam interval $$$[0, 1)$ , sesuai dengan kolom yang dart hits. Komponen $$$y$ yang harus dalam interval $$$[0, 1)$ , sesuai dengan seberapa tinggi kita di kolom. Pemilihan komponen $$$x$ mempengaruhi bagian mana dari tulang penipu yang sedang kita pertimbangkan, dan pemilihan komponen $$$y$ sesuai dengan apakah kita telah memilih aspek ini atau tidak. Tapi tunggu - kita sudah tahu dua ide ini! Seleksi koordinat $$$x$ sesuai dengan kolom, mirip dengan melempar tulang yang jujur ​​untuk memutuskan pilihan kolom. Seleksi koordinat $$$y$ sesuai dengan lemparan koin asimetris untuk menentukan apakah akan memilih wajah atau melemparkan lagi! Pengamatan ini sangat penting sehingga kami membuatnya benar-benar dapat dimengerti:

Pilihan titik acak dalam interval ini mirip dengan melempar tulang yang jujur ​​dan melempar koin asimetris.

Bahkan, hasil ini dapat dianggap sebagai peluang yang jauh lebih kuat. Untuk mensimulasikan tulang selingkuh, kami membuat satu set koin asimetris, satu untuk setiap sisi tulang, dan kemudian menggulung tulang yang jujur ​​untuk menentukan koin yang akan dilempar. Berdasarkan pada gulungan tulang, jika seekor rajawali jatuh pada koin yang sesuai, maka kita memilih wajah yang sesuai, dan jika ekornya jatuh, maka lemparkan tulang itu lagi dan ulangi prosesnya.

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ . , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ .
  2. $$$Coins$ $$$n$ , «» .
  3. $$$i$ dari $$$0$ sebelumnya $$$n - 1$ :
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$i$ $$$[0, n)$ .
     2. , $$$Coins[i]$ .
     3. , $$$i$ .

. $$$O (n)$ , $$$O (n)$ $$$Coins$ , $$$O (n)$ . , $$$O(1)$ . ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$i$ $$$\frac{p_i}{p_{max}}$ , -

$$

$$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ . ? $$$p_{max}$ . $$$p_{max}$ $$$1$ ( ). $$$n$ , $$$n$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . Jika $$$p_{max} = \frac{1}{n}$ , 1. . Jika $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$n$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ . , «» $$$\frac{1}{n \cdot p_{max}}$ . , , «», $$$p_{max}$ . , , .

:

Algoritma
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . , $$$\frac{1}{4}$ . , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ? , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ . , :


, , $$$\frac{1}{2}$ dan $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ? , - , :


, , . , $$$\frac{1}{2}$ dan $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ . $$$n$ . , alias , ( ). , . - - $$$i$ . $$$Prob[i]$ . , , $$$i$ , , $$$Alias[i]$ . alias :

Alias

, $$$Alias$ dan $$$Prob$ . , , :

• $$$(n \cdot p_i) \times 1$ $$$p_i$ ,
• $$$n$
  
  • , $$$1$ ,
  • , $$$i$ , $$$i$ .

, , . , $$$\frac{1}{2}$ , $$$\frac{1}{3}$ , $$$\frac{1}{12}$ , $$$\frac{1}{12}$ . ( $$$k = n = 4$ ), $$$1 = \frac{4}{4}$ . , alias, , . , 4, :


, , ( $$$\frac{1}{3}$ , $$$\frac{1}{3}$ ) 1. , - . ( ) :


- . , , , 1 ( $$$2$ dan $$$\frac{4}{3}$ ) ; $$$\frac{4}{3}$ . $$$\frac{4}{3}$ , ; $$$\frac{2}{3}$ dari $$$\frac{4}{3}$ , :


, . , $$$3$ , , , . , . , , $$$1$ , (, $$$\frac{2}{3}$ ) :


, - , 1, . ( $$$2$ ), $$$\frac{1}{3}$ dari $$$2$ :


, . , - , 1 ( $$$\frac{1}{3}$ ), :


- $$$1$ , . — $$$\frac{5}{3}$ :


, 1. , :


! .

, :

• - , 1, , $$$Prob$ .
• - , 1, , $$$Alias$ , .

, ? «», ? , . : , 1 ( $$$\frac{1}{n}$ , $$$n$ ) , , , , 1 ( ) 1 ( ). , . , ? , . , , . , .

:

: $$$k$ $$$h_0$ , $$$h_1$ , ..., $$$h_{k-1}$ , , $$$\sum_{i=0}^{k-1}{h_i} = k$ , $$$k$ , 1, , , $$$i$ - $$$i$ - .

: . , $$$k = 1$ , 1. $$$0$ - . , 1, , $$$0$ - $$$0$ - .

, - $$$k$ $$$k + 1$ $$$1$ $$$h_0$ , $$$h_1$ , ..., $$$h_{k}$ , , $$$\sum_{i = 0}^{k}{h_i} = k + 1$ . , $$$h_l$ , , $$$h_l \le 1$ , - $$$h_g$ (, $$$l \ne g$ ), , $$$h_g \ge 1$ . , , $$$h_l$ dengan $$$h_l \le 1$ ; , $$$h_i > 1$ $$$i$ $$$0 \le i \le k$ . , $$$k + 1 = \sum_{i = 0}^k{h_i} > \sum_{i=0}^k{1} = k + 1$ , . , - $$$l$ , , $$$h_l \le 1$ . , $$$h_g$ ( $$$l \ne g$ ), , $$$h_g \ge 1$ . , $$$h_g < 1$ , ( ) $$$\sum_{i=0}^{k}{h_i} < k + 1$ . , $$$h_l \le 1$ dan $$$h_g \ge 1$ .

. $$$h_l$ $$$l$ $$$1 - h_l$ masuk $$$l$ - $$$h_g$ ( , $$$0 \le 1 - h_l \le 1$ dan $$$h_g \ge 1$ ) . $$$k$ , $$$k$ , $$$1$ , $$$k + 1$ . , $$$l$ , . , , $$$k$ masuk $$$k$ , . , $$$l$ , , , . .

, , alias, , . alias.

Alias

, alias-. 1 1, :

: Alias-

• :
  
  1. $$$p_i$ pada $$$n$ .
  2. $$$Alias$ dan $$$Prob$ , $$$n$ .
  3. For $$$j = 1 \mbox{ to } n - 1$ :
     
     1. $$$p_l$ , $$$p_l \le 1$ .
     2. $$$p_g$ ( $$$l \ne g$ ), $$$p_g \ge 1$
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_l$ .
     6. $$$p_g := p_g - (1 - p_l)$ .
     
     
  4. Biarkan $$$i$ , 1.
  5. $$$Prob[i] = 1$ .
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

, , $$$\Theta(1)$ . . -, $$$\Theta(n)$ $$$n$ , $$$O (n)$ . $$$\Theta(n)$ , $$$O (n)$ , . $$$O(n^2)$ . , :

Algoritma
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$

alias- , . - (, $$$O (n)$ ), .

. , $$$O (n)$ . . $$$p_g$ dan $$$p_l$ $$$O(\log n)$ , . $$$p_l$ $$$O(\log n)$ , $$$p_g$ $$$O(\log n)$ . :

: Alias-

• :
  
  1. $$$Alias$ dan $$$Prob$ , $$$n$ .
  2. $$$T$ .
  3. $$$n \cdot p_i$ masuk $$$T$ $$$i$ .
  4. For $$$j = 1 \mbox{ to } n - 1$ :
     
     1. $$$T$ ; $$$p_l$ .
     2. $$$T$ ; $$$p_g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := p_g - (1 - p_l)$ .
     6. $$$p_g$ $$$T$ .
     
     
  5. Biarkan $$$i$ , 1.
  6. $$$Prob[i] = 1$ .
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

. $$$Alias$ dan $$$Prob$ - $$$O (n)$ , BST $$$T$ $$$\Theta(n \log n)$ . $$$\Theta(n)$ , $$$O(\log n)$ . $$$O(n \log n)$ :

Algoritma
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$

, . , , , alias-. «A Linear Algorithm For Generating Random Numbers With a Given Distribution» , alias-.

: 1, 1. . «» , «» «». :

• «» 1.
• «» 1.
• .

, , , . , :

: () Alias-

: . .

• :
  
  1. $$$Alias$ dan $$$Prob$ , $$$n$ .
  2. , $$$Small$ dan $$$Large$ .
  3. $$$n$ .
  4. $$$p_i$ :
     
     1. Jika $$$p_i < 1$ , $$$i$ $$$Small$ .
     2. ( $$$p_i \ge 1$ ) $$$i$ $$$Large$ .
     
     
  5. $$$Small$ :
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Large$ ; $$$g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := p_g - (1 - p_l)$ .
     6. Jika $$$p_g < 1$ , $$$g$ masuk $$$Small$ .
     7. ($p_g \ge 1$) $$$g$ masuk $$$Large$ .
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$g$ .
     2. $$$Prob[g] = 1$ .
     
     
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

(, ) : - $$$Small$ $$$Large$ , . . $$$Small$ $$$Large$ ( $$$Small$ , , ). $$$Large$ 1, $$$k$ $$$Large$ $$$k$ , $$$Large$ 1, . 1, , , 1.

. , , , . .

, . $$$\frac{1}{4}$ , $$$\frac{1}{5}$ , $$$\frac{1}{8}$ , $$$\frac{1}{8}$ , $$$\frac{1}{10}$ , $$$\frac{1}{10}$ , $$$\frac{1}{10}$ . , , $$$\frac{1}{8}$ , $$$\frac{1}{5}$ , $$$\frac{1}{10}$ , $$$\frac{1}{4}$ , $$$\frac{1}{10}$ , $$$\frac{1}{10}$ , $$$\frac{1}{8}$ . :


$$$Small$ , :


$$$Large$ ( ) . $$$\frac{7}{4} - \frac{1}{8} = \frac{13}{8} \ge 1$ , $$$Large$ :


. $$$Small$ , $$$Large$ :


:


, , , . , :


$$$Small$ , :


$$$Small$ , , :


, $$$Small$ , .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$ $$$Large$ , . , , $$$n$ , , $$$\frac{1}{n}$ , $$$1$ ( $$$Small$ , $$$Large$ )
2. , , . , , $$$Large$ , $$$Small$ .

, $$$Small$ $$$Large$ . , , $$$Small$ , $$$Large$ .

, . , , , $$$Large$ . -, , $$$1$ , , $$$1$ . , . :

: Alias-

• :
  
  1. $$$Alias$ dan $$$Prob$ , $$$n$ .
  2. , $$$Small$ dan $$$Large$ .
  3. $$$n$ .
  4. $$$p_i$ :
     
     1. Jika $$$p_i < 1$ , $$$i$ masuk $$$Small$ .
     2. ( $$$p_i \ge 1$ ) $$$i$ masuk $$$Large$ .
     
     
  5. $$$Small$ dan $$$Large$ : ( $$$Large$ )
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Large$ ; $$$g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := (p_g + p_l) - 1$ . ( . )
     6. Jika $$$p_g < 1$ , $$$g$ masuk $$$Small$ .
     7. ( $$$p_g \ge 1$ ) $$$g$ masuk $$$Large$ .
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$g$ .
     2. $$$Prob[g] = 1$ .
     
     
  7. $$$Small$ : - .
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Prob[l] = 1$ .
     
     
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

, — . $$$\Theta(n)$ , . $$$\Theta(1)$ , , . $$$O (n)$ , () , . $$$O (n)$ , $$$Large$ dan $$$Small$ $$$O (n)$ . $$$\Theta(n)$ , ( ) :

Algoritma
	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !