Metode Penolakan (Rejection Method) pada Variabel Acak Diskrit
Misalkan kita telah memiliki sebuah metode yang efisien untuk mensimulasikan variabel acak. Model tersebut memiliki fungsi probabilitas massa (Probability Mass Function) \{ q_{j},j\geq 0 \} . Kita bisa menggunakan metode ini sebagai basis simulasi dari distribusi yang memiliki fungsi massa dengan cara mensimulasikan terlebih dahulu sebuah variabel acak Y yang memiliki fungsi massa
dan kemudian menerima nilai simulasi ini dengan probabilitas proporsional p_{y}/q_{y}
Secara lebih rincinya, misalkan c sebuah konstanta yang sedemikian sehingga :
\frac{p_{j}}{q_{j}}\leq c \; \; , untuk semua j sedemikian sehingga p_{j}> 0
Sekarang kita memiliki teknik yang disebut Metode Penolakan atau Metode penerimaan-penolakan, untuk mensimulasikan sebuah variabel acak X yang memiliki fungsi massa p_j = P \{ X = j\}
Langkah-langkah Metode Penolakan (Rejectoin Method) adalah sebagai berikut :
- Simulasikan nilai Y, yaitu nilai yang memiliki fungsi massa probabilitas q_j
- Bangkitkan sebuah bilangan acak U
- Jika U <\frac{p_y}{c q_y}, tetapkan X = Y, lainnya kembali ke langkah nomor 1
Secara gambar, metode penolakan ini dapat dilihat sebagai berikut :
Teorema
Algoritma penerimaan-penolakan membangkitkan sebuah variabel acak X sedemikian sehingga
P \{ X = j\} = p_j , j = 0, …
Tambahan : banyaknya iterasi algoritma ini yang dibutuhkan untuk menghasilkan X adalah variabel random geometric dengan mean c.
Bukti :
Untuk memulai pembuktian, mari kita tentukan probabilitas yaitu sebuah iterasi tunggal menghasilkan penerimaan sebuah nilai j.