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 :

1. Simulasikan nilai Y, yaitu nilai yang memiliki fungsi massa probabilitas \( q_j \)
2. Bangkitkan sebuah bilangan acak U
3. 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.