7_Pembangkit_Bilangan_Random

Menggenerate Bilangan Random

Masalah: menggenerate sample dari variabel random $X$ dengan densitas $f$ tertentu (sample ini disebut random variate). Maksudnya: mengembangkan algoritma sehingga jika dipakai berulang (dan independen) menghasilkan urutan sample $X_1,X_2,...,X_n$, maka untuk $n$ besar, proporsi sample yang jatuh di interval $[a,b]$ mendekati $P(X\in [a,b])$.

Solusi 2 langkah:

1. Generate random variate uniform di $[0,1]$ (disebut juga random number).
2. Gunakan transformasi yang sesuai untuk mengubah bilangan random tersebut menjadi random variate dari distribusi yang diinginkan.

Pendekatan ini bagus karena kita cukup fokus pada cara menggenerate sample dari satu distribusi saja (uniform), lalu mentransformasinya ke distribusi lain.

Pseudo-Random Numbers

Beberapa metode menggenerate bilangan random uniform $[0,1]$:

1. Metode fisik — roda roulette, bola undian lotere, sirkuit elektrik, dsb.
2. Metode numerik/aritmetik — metode sekuensial, tiap bilangan baru adalah fungsi deterministik dari bilangan-bilangan sebelumnya.

Untuk simulasi, metode numerik paling praktis — meskipun bilangan yang dihasilkan sebenarnya tidak benar-benar random (karena deterministik), cukup jika bilangan tersebut “tampak” uniform, tidak berkorelasi satu sama lain, dan lolos uji statistik (sehingga central limit theorem tetap bisa berlaku).

Properti yang harus dimiliki pembangkit bilangan pseudo-random:

1. Cepat dan tidak membebani memori.
2. Bisa mereproduksi aliran (stream) bilangan random yang sama — berguna untuk debugging/verifikasi program, atau untuk membandingkan sistem yang berbeda dengan bilangan random yang identik.
3. Menyediakan beberapa stream independen berbeda.

Linear Congruential Generators (LCG)

$Z_i=(a{Z}_{i-1}+c)(\mathrm{mod}m),i\ge 1,U_i=\frac{Z_i}{m}$

dimana modulus $m$ (pembagi yang menentukan rentang nilai $Z_i$, yaitu $0$ sampai $m-1$), multiplier $a$ (pengali $Z_{i-1}$ tiap langkah), increment $c$ (konstanta yang ditambahkan tiap langkah), dan seed $Z_0$ (nilai awal yang menjadi titik mulai urutan — mengganti seed menghasilkan urutan bilangan yang berbeda, meski rumusnya sama) semuanya non-negatif, dengan $a<m$ dan $c,Z_0<m$.

Contoh: $Z_i=(5Z_{i-1}+3)(\mathrm{mod}16)$ dengan $Z_0=7$ menghasilkan urutan $7,6,1,8,11,10,15,12,15,14,9,0,3,2,13,4,7,6,1,8,...$ (berulang dengan periode tertentu — banyaknya bilangan berbeda yang muncul sebelum urutan $Z_i$ kembali ke nilai awal dan mengulang polanya; periode yang lebih panjang berarti generator tampak acak lebih lama sebelum pengulangan terlihat). Mengganti increment $c$ (mis. $c=6$) menghasilkan urutan berbeda.

Ada juga generator yang lebih umum: $Z_i=g(Z_{i-1},Z_{i-2},...)(\mathrm{mod}m)$ — contoh populer: Tautsworth generator, $Z_i=(c_1{Z}_{i-1}+c_2{Z}_{i-2}+...+c_q{Z}_{i-q})(\mathrm{mod}2)$.

Dalam praktik, sebagian besar simulator dan bahasa pemrograman sudah menyediakan pembangkit bilangan random yang baik — fokus pembahasan berikutnya adalah bagaimana mentransformasi bilangan random menjadi random variate dari distribusi tertentu, dibahas di Metoda Pembangkit Random Variate.

Sumber

• Materi kuliah IF4021 Model dan Simulasi, minggu 8, “Inverse Transform Method” (bagian 1: generating random numbers & pseudo-random numbers).

Flashcard

flashcards Apa dua langkah solusi umum untuk menggenerate random variate dari distribusi tertentu? :: (1) Generate random variate uniform di [0,1] (random number), (2) gunakan transformasi yang sesuai untuk mengubah bilangan random tersebut menjadi random variate dari distribusi yang diinginkan. Mengapa pendekatan dua-langkah (generate uniform lalu transformasi) dianggap baik? :: Karena kita cukup fokus mengembangkan cara menggenerate sample dari SATU distribusi saja (uniform [0,1]), lalu memakai transformasi berbeda-beda untuk mendapatkan distribusi lain — tidak perlu algoritma terpisah untuk tiap distribusi dari awal. Mengapa bilangan yang dihasilkan metode numerik/aritmetik disebut “pseudo-random”, bukan benar-benar random? :: Karena tiap bilangan baru adalah fungsi deterministik dari bilangan-bilangan sebelumnya (metode sekuensial) — bukan hasil proses fisik yang benar-benar acak; cukup jika bilangan tersebut tampak uniform dan lolos uji statistik. Sebutkan tiga properti yang harus dimiliki pembangkit bilangan pseudo-random yang baik :: (1) Cepat dan tidak membebani memori, (2) mampu mereproduksi stream bilangan random yang sama (untuk debugging/perbandingan sistem), (3) menyediakan beberapa stream independen berbeda. Apa rumus umum Linear Congruential Generator (LCG), dan apa syarat pada parameter-parameternya? :: Z_i = (aZ_{i-1}+c) mod m dengan U_i = Z_i/m; parameter modulus m, multiplier a, increment c, dan seed Z_0 semuanya non-negatif, dengan a<m dan c,Z_0<m. Apa itu Tautsworth generator, dan bagaimana ia berbeda dari LCG dasar? :: Generator yang lebih umum, Z_i = (c_1 Z_{i-1} + c_2 Z_{i-2} + … + c_q Z_{i-q}) mod 2 — memakai kombinasi beberapa nilai sebelumnya (bukan hanya satu nilai sebelumnya seperti LCG dasar) untuk membangkitkan bilangan berikutnya.