8_Metoda_Pembangkit_Random_Variate

Empat metode umum untuk mentransformasi bilangan random (uniform $[0,1]$) menjadi random variate dari distribusi tertentu: Inverse Transform, Komposisi, Konvolusi, dan Penerimaan-Penolakan (acceptance-rejection).

Metode Inverse Transform

Variabel Random Kontinu

Untuk menggenerate $X\sim F$ (dengan asumsi $F^{-1}$ ada):

1. Generate bilangan random uniform $U$.
2. Set $X=F^{-1}(U)$.

Bukti: $P(X\le x)=P(F^{-1}(U)\le x)=P(U\le F(x))=F(x)$ — karena $F$ monoton naik, dan CDF uniform $F_U(y)=y$ untuk $y\in [0,1]$.

Algoritma umum: diberikan CDF $F(x)$ atau densitas $f(x)$ (integralkan dulu bila diberi densitas — kesalahan tersering: salah batas integrasi); set $F(X)=U$ dan selesaikan $X$ dalam bentuk $U$, pastikan solusi berada di rentang yang benar.

Contoh — eksponensial $(\lambda )$: $f(x)=\lambda e^{-\lambda x}$, $F(x)=1-e^{-\lambda x}$. Dari $F(X)=U$: $X=-\frac{1}{\lambda }\ln (1-U)$. Karena $1-U$ juga uniform $[0,1]$ bila $U$ uniform, cukup dipakai $X=-\frac{1}{\lambda }\ln (U)$.

Variabel Random Diskrit

Untuk pmf $P(X=x_i)=p_i,i=1,...,m$: generate $U$, lalu set $X=x_j$ jika ${\sum }_{i=1}^{j-1}{p}_i\le U<{\sum }_{i=1}^j{p}_i$.

Efisiensi: waktu eksekusi proporsional terhadap jumlah interval yang harus diperiksa — sehingga lebih efisien mengurutkan nilai $x_j$ berdasarkan $p_i$ menurun (nilai dengan probabilitas terbesar dicek lebih dulu).

Contoh geometrik: $P(X=i)=p{q}^{i-1}$, $q=1-p$. CDF $F(i)=1-q^i$. Diperoleh bentuk tertutup:

$X=\lceil \frac{\log (1-U)}{\log (1-p)}\rceil$

Contoh binomial: tidak ada bentuk tertutup, dipakai algoritma iteratif memakai relasi rekursif $p_i=\left(\frac{n-i}{i+1}\right)\left(\frac{p}{1-p}\right)p_{i-1}$ — cari $j$ terkecil sehingga kumulatif $F$ melebihi $U$.

Kelebihan & Kekurangan

• Kekurangan: butuh bentuk tertutup untuk $F(x)$; seringkali lambat karena banyak perbandingan.
• Kelebihan: mempertahankan monotonicity ($U$ yang lebih besar selalu menghasilkan $X=F^{-1}(U)$ yang lebih besar pula, karena $F^{-1}$ monoton naik) dan korelasi — berguna untuk teknik reduksi variansi (mis. memakai $U$ yang sama di beberapa skenario agar hasilnya bisa dibandingkan secara berpasangan), membangkitkan truncated distribution (distribusi yang “dipotong” hanya pada sub-interval tertentu — cukup dibatasi dengan membatasi rentang $U$ sesuai interval tersebut), dan order statistics (sampel yang sudah terurut $X_{(1)}\le X_{(2)}\le ...\le X_{(n)}$, bisa langsung diperoleh dengan mentransformasi $U_{(1)}\le U_{(2)}\le ...$ yang sudah terurut lebih dulu).

Metode Konvolusi

Jika $X$ adalah jumlah dari variabel random independen $Z_1,...,Z_m$ (masing-masing $\sim F_i$):

$X=Z_1+Z_2+...+Z_m$

Algoritma: generate $m$ bilangan random $U_1,...,U_m$; hitung $Z_i=F_i^{-1}(U_i)$ (inverse transform); set $X=\sum Z_i$.

Disebut metode konvolusi karena densitas $X$ adalah hasil konvolusi densitas-densitas komponennya: $f_X=f_1\ast f_2\ast ...\ast f_m$.

Contoh — Erlang$(\lambda ,m)$: jika $Z_i\sim \exp (\lambda )$ independen, maka $X=\sum Z_i\sim \text{Erlang}(\lambda ,m)$. Algoritma: generate $U_1,...,U_m$; $Z_i=-\frac{1}{\lambda }\ln U_i$; $X=\sum Z_i$. Kekurangan: butuh $m$ bilangan random untuk 1 sample — tidak efisien untuk $m$ besar.

Metode Komposisi

Dipakai bila fungsi distribusi $F$ yang ingin digenerate dapat dituliskan sebagai kombinasi konveks dari fungsi distribusi lain $F_1,F_2,...$:

$F(x)={\sum }_{j=1}^{\infty }{p}_j{F}_j(x),p_j\ge 0,\sum p_j=1$

(meski dituliskan tak hingga, biasanya cukup $k$ komponen dengan $p_j=0$ untuk $j>k$). Ide dasarnya: kita berharap men-generate sample dari $F_j$ lebih mudah dibanding dari $F$ langsung.

Contoh — distribusi eksponensial-ganda (Laplace): $f(x)=0.5e^{-|x|}$ untuk semua $x$ real. Fungsi ini adalah komposisi $f_1(x)=e^x{I}_{(-\infty ,0)}(x)$ dan $f_2(x)=e^{-x}{I}_{(0,\infty )}(x)$ dengan $p_1=p_2=0.5$. Algoritma: generate $U_1,U_2\sim U(0,1)$; jika $U_1\le 0.5$ maka $X=\ln U_2$, sebaliknya $X=-\ln U_2$.

Metode Penerimaan-Penolakan (Acceptance-Rejection)

Memerlukan fungsi $t(x)$ yang melingkupi densitas target: $t(x)\ge f(x)\forall x$. Karena $t$ bukan densitas ($c=\int t(x)dx\ge 1$), didefinisikan densitas $r(x)=t(x)/c$.

Algoritma:

1. Generate $Y$ dengan densitas $r$.
2. Generate $U\sim U(0,1)$, independen terhadap $Y$.
3. Jika $U\le f(Y)/t(Y)$, maka $X=Y$; jika tidak, ulangi dari langkah 1.

Contoh — beta(4,3): $f(x)=60x^3(1-x{)}^2$ untuk $0\le x\le 1$. Karena $F(x)$ berderajat polinomial 6 (sulit dicari baliknya), dipakai penerimaan-penolakan. Nilai maksimum $f(x)$ terjadi di $x=0.6$, $f(0.6)=2.0736$, sehingga $t(x)=2.0736$ (konstan) untuk $0\le x\le 1$; $c=2.0736$, dan $r(x)$ menjadi densitas $U(0,1)$. Algoritma: generate $Y,U\sim U(0,1)$; cek $U\le \frac{60Y^3(1-Y{)}^2}{2.0736}$ — jika ya $X=Y$, jika tidak ulangi.

Membangkitkan Variabel Random Kontinu Tertentu

Uniform $U(a,b)$

$X=F^{-1}(u)=a+(b-a)u$. Algoritma: generate $U\sim U(0,1)$; $X=a+(b-a)U$.

Eksponensial

Algoritma: generate $U\sim U(0,1)$; $X=-\beta \ln U$ (mean $\beta$).

m-Erlang

Jika $X$ punya mean $\beta$, $X=Y_1+...+Y_m$ dimana $Y_i$ eksponensial dengan mean $\beta /m$. Dengan metode konvolusi:

$X={\sum }_{i=1}^m\left(-\frac{\beta }{m}\ln U_i\right)=-\frac{\beta }{m}\ln \left({\prod }_{i=1}^m{U}_i\right)$

Algoritma: generate $U_1,...,U_m$ IID $U(0,1)$; $X=-\frac{\beta }{m}\ln (\prod U_i)$.

Gamma$(\alpha ,1)$, $0<\alpha <1$

Variabel random Gamma umum kompleks; kasus $\text{gamma}(\alpha ,\beta )$ diperoleh dari $X^{\prime }=\beta X$ dengan $X\sim \text{gamma}(\alpha ,1)$. (Catatan: gamma(1,1) = eksponensial mean 1). Untuk $0<\alpha <1$ dipakai penerimaan-penolakan, dengan fungsi pendominasi $t(x)$ berbeda untuk $0<x\le 1$ dan $x>1$, serta $b=(e+\alpha )/e$. Fungsi densitas rasio $f(Y)/t(Y)=e^{-Y}$ untuk $0\le Y\le 1$, dan $=Y^{\alpha -1}$ untuk $Y>1$.

Weibull

$F^{-1}(u)=\beta [-\ln (1-u){]}^{1/\alpha }$. Algoritma: generate $U\sim U(0,1)$; $X=\beta (-\ln U{)}^{1/\alpha }$.

Normal (Metode Polar)

Cukup membangkitkan $N(0,1)$ (variabel $N(\mu ,{\sigma }^2)$ diperoleh dari transformasi linier). Metode polar membangkitkan sepasang $N(0,1)$ sekaligus:

Algoritma:

1. Generate $U_1,U_2$ IID $U(0,1)$; hitung $V_i=2U_i-1$ untuk $i=1,2$; hitung $W=V_1^2+V_2^2$.
2. Jika $W>1$, kembali ke langkah 1. Jika tidak: hitung $Y=\sqrt{(-2\ln W)/W}$; $X_1=V_{1}Y$; $X_2=V_{2}Y$. Maka $X_1,X_2$ adalah IID $N(0,1)$.

Sumber

• Materi kuliah IF4021 Model dan Simulasi, minggu 9, “Inverse Transform Method” (bagian 2: continuous & discrete random variables, convolution) dan “Men-generate bilangan Random Variate” (komposisi, penerimaan-penolakan, distribusi kontinu tertentu).

Flashcard

flashcards Bagaimana bukti bahwa algoritma inverse transform (X = F⁻¹(U)) menghasilkan sample dengan CDF tepat F(x)? :: P(X≤x) = P(F⁻¹(U)≤x) = P(U≤F(x)) [karena F monoton naik] = F(x) [karena CDF uniform F_U(y)=y untuk y∈[0,1]]. Mengapa untuk variabel random diskrit, lebih efisien mengurutkan nilai x_j berdasarkan p_i menurun sebelum menerapkan inverse transform? :: Karena waktu eksekusi algoritma proporsional terhadap jumlah interval yang harus diperiksa sebelum menemukan interval yang tepat; dengan mengurutkan probabilitas terbesar dicek lebih dulu, rata-rata jumlah perbandingan yang dibutuhkan menjadi lebih kecil. Apa dua kekurangan utama metode inverse transform, dan apa kelebihan utamanya? :: Kekurangan: (1) butuh bentuk tertutup untuk F(x), (2) seringkali lambat karena banyak perbandingan. Kelebihan: mempertahankan monotonicity dan korelasi, berguna untuk variance reduction, truncated distribution, dan order statistics. Bagaimana metode konvolusi membangkitkan random variate Erlang(λ,m), dan mengapa metode ini disebut “konvolusi”? :: Membangkitkan m variate eksponensial independen Z_i = -(1/λ)ln(U_i) lalu menjumlahkannya X=ΣZ_i; disebut konvolusi karena densitas fX adalah hasil operasi konvolusi f1f2…*fm dari densitas komponennya. Kapan metode komposisi digunakan untuk membangkitkan random variate, dan apa syarat pj serta Fj di dalamnya? :: Digunakan bila F(x) dapat dituliskan sebagai kombinasi konveks Σp_j F_j(x) dari distribusi lain yang lebih mudah digenerate; syaratnya p_j≥0, Σp_j=1, dan F_j adalah fungsi distribusi yang sah. Jelaskan tiga langkah algoritma penerimaan-penolakan (acceptance-rejection), dan apa syarat fungsi t(x)? :: (1) Generate Y dengan densitas r=t/c, (2) generate UU(0,1) independen dari Y, (3) jika U≤f(Y)/t(Y) maka X=Y, jika tidak ulangi dari langkah 1. Syarat t(x): t(x)≥f(x) untuk semua x (melingkupi densitas target). Mengapa distribusi beta(4,3) pada contoh materi dibangkitkan dengan penerimaan-penolakan, bukan inverse transform? :: Karena F(x) distribusi beta(4,3) berbentuk polinomial derajat 6, sehingga sulit dicari fungsi baliknya (inverse) secara analitik — penerimaan-penolakan menghindari kebutuhan tersebut dengan memakai fungsi pendominasi konstan t(x)=2.0736 (nilai maksimum f di x=0.6). Bagaimana metode polar membangkitkan sepasang variate N(0,1) sekaligus? :: Generate U1,U2U(0,1), hitung V_i=2U_i-1 dan W=V1²+V2²; jika W>1 ulangi; jika tidak, hitung Y=√((-2 ln W)/W), lalu X1=V1·Y dan X2=V2·Y — keduanya IID N(0,1).