Bilangan Acak – OpenStat

Menghitung Integral dengan menggunakan Bilangan Acak

13 October 2010 adminku Leave a comment

Misalkan g(x) adalah sebuah fungsi. Kita ingin menghitung $ \theta $ yaitu :

$\dpi{100} \theta = \int_{0}^{1} g(x) dx$

Apa yang menjadi dasar bahwa integral di atas dapat dihitung dengan menggunakan bilangan random $ \theta $

Penjelasan :

Ambil U suatu bilangan acak yang terdistribusi secara uniform dan independent di interval (0,1).

Kemudian misalnya kita nyatakan $ \theta $ sebagai :

$\theta = E[g(U)]$

Jika $U_{1}, … , U_{k}$ adalah variabel random yang independent dan uniform di interval (0,1), maka menjadikan juga $g( u_{i} )$ adalah sebagai variabel random yang independent dan terdistribusi secara identik dengan mean $ \theta $. Karena itu, dengan menggunakan dasar hukum kuat dari bilangan besar (the strong law of large numbers), mengikuti ketentuannya dengan probabilitas 1.

$\large \sum_{i=1}^{k}\frac{g(U_{i})}{k} \to E[g(U)]= \theta \;\;\;\; ketika \; k \to \infty$

Karena itu kita dapat mendekati $ \theta $ dengan cara membangkitkan sebanyak mungkin bilangan random $ u_{i}$ dan mengambilnya sebagai pendekatan kita terhadap nilai rata-rata (average) dari $g( u_{i} ) $. Pendekatan semacam ini sering disebut sebagai pendekatan Monte Carlo.

Berikut ini adalah contoh algoritma dari bahasa BASIC yang dapat digunakan untuk mendekati nilai $ \theta $ :

10 RANDOMIZE 20 INPUT K 30 S = 0 40 FOR I = 1 TO k 50 U = RND 60 S = S + g(U) 70 NEXT 80 PRINT S/K
Nilai yang dihasilkan dari alogoritma ini adalah nilai dari $ \theta = \int_{0}^{1} g(x) dx $.

Kasus 1 :

Jika kita ingin menghitung :

$ \theta = \int_{a}^{b} g(x) dx $

maka kita menggunakan substitusi $ y = (x-a)/(b – a), dy = dx / (b-a) $, sehingga :

$\begin{align*} \theta &= \int_{0}^{1} g(a+[b-a]y)(b-a)) dy\\ &= \int_{0}^{1} h(y) dy \end{align*}$

dimana h(y) = (b – a) g(a + [b – a] y ).

Dengan demikian kita dapat mendekati nilai $ \theta $ dengan membangkitkan bilang random secara kontinyu dan mengambil nilai rata-rata (average) dari h yang dihitung pada bilangan-bilangan random tadi.

Kasus 2 :

Jika kita ingin menghitung :

$\theta &= \int_{0}^{\infty} g(x) dx$

kita bisa menggunakan substitusi $\inline y = 1/(x + 1), dy = - dx/(x + 1)^2 = -y^{2} dx$

Substitusi ini menggambarkan bahwa

ketika $ x \to 0$ maka $ y \to 0$
ketika $ x \to \infty $ maka $ y \to 1$

Catatan : ingat sifat integral tertentu :

$\int_{a}^{b} f(x) dx = - \int_{b}^{a} f(x) dx$

selanjutnya karena : $\inline y = 1/(x + 1)$

$\begin{align*} dy &= d(\frac{1}{x+1}) \\ &= - \frac{dx}{(x+1)^2}\\ &= - (\frac{1}{x+1})^2 dx\\ &= - y^2 dx\\ dx &= - \frac{1}{y^2} dy \end{align*}$

kemudian

$\begin{align*} y &= \frac{1}{x+1}\\ x+1 &= \frac{1}{y}\\ {\color{red} x } &= {\color{red} \frac{1}{y} - 1 }\\ \end{align*}$

sehingga didapatkan identitas :

$\theta &= \int_{0}^{\infty} h(x) dx$

dimana

$h(y)=\frac{g(\frac{1}{y}-1)}{y^{2}}$

Pemodelan & simulasi Bilangan Acak, Integral, Monte Carlo

Pembangkit Bilangan Acak Pesudo

30 September 2010 toosa Leave a comment

Salah satu pendekatan yang sering digunakan dalam membangkitkan bilangan acak pseudo (pseudorandom numbers) adalah memulainya dengan sebuah nilai awal x₀yang sering disebut sebagai bibit/seed, kemudian komputer akan membangkitkan bilangan nilai-nilai berikutnya yaitu x_n, $n\geq 1$ secara rekursif, dengan cara memisalkan :

$x_{n}= a x_{n-1} \; modulo \; m$ … (3.1)

dimana a dan m adalah bilangan bulat positif yang sudah ditentukan, dan dimana hal diatas artinya bahwa $a x_{n-1}$ dibagi dengan m dan sisa baginya diambil sebagai nilai dari $ x_{n}$. Dengan demikian setiap $ x_{n}$ bisa bernilai salah satu diantara $0,1,\cdots,m-1$ dan kuantitas dari $x_{n}/m$ – disebut sebuah bilangan acak pseudo (pseudorandom number)- diambil sebagai nilai pendekatan untuk nilai dari variabel acak uniform (0,1).

Pendekatan yang ditentukan dengan persamaan 3.1 dalam membangkitkan bilangan acak tersebut sering disebut Multiplicative Congruential Method. Karena setiap angka $ x_{n}$ yang akan bernilai salah satu dari $0,1,\cdots,m-1$, pada suatu saat setelah sejumlah pembangkitan tertentu akan terjadi perulangan; dan seketika ini terjadi, keseluruhan deret bilangan akan kembali berulang. Dengan demikian, kita seyogyanya ingin memilih konstanta a dan m sedemikian sehingga, untuk sembarang seed $ x_{0}$, banyaknya variable yang dapat dibangkitkan sebelum terjadi perulangan terjadi cukup besar.

Secara umum konstanta a dan m dapat dipilih untuk memenuhi 3 kriteria :

Untuk sembarang nilai awal seed , deretan hasil memiliki pemunculan deret variable acak yang independent uniform (0,1)
Untuk sembarang nilai awal seed , banyaknya variable yang dapat dibangkitkan sebelum terjadi perulangan cukup besar.
Nilai-nilai ini dapat dihitung secera efisien dengan menggunakan komputer

Untuk memenuhi ketiga kondisi tersebut di atas, sebaiknya m dipilih dari bilangan prima yang cukup besar, biasanya disesuaikan dengan kemampuan komputer yang digunakan dan ukuran word. Untuk mesin 32 bit (dimana bit pertama digunakan sebagai bit penanda / sign bit), pemilihan m = $ 2^{31} – 1$ dan $ a = 7^5 = 16807$ menghasilkan hasil yang diinginkan.

Pembangkit bilangan acak lainnya adalah :

$x_{n}= (a x_{n-1}+c) \; modulo \; m$

pembangkit ini diberi nama mixed congruential generators. Pembangkit ini dianggap lebih baik hasilnya dari pembangkit sebelumnya.

Kebanyakan bahasa pemrograman komputer sudah menyediakan pembangkit bilangan acak nya sendiri. Misalnya dalam bahasa BASIC, bahasa ini menggunakan 2 (dua) buah perintah yaitu :

1 RANDOMIZE

2 U = RND

Contoh program yang menghasilkan 10 (sepuluh) buah bilangan acak :

10 RANDOMIZE

20 FOR I = 1 TO 10

30 U = RND

40 PRINT U

50 NEXT

Pemodelan & simulasi Bilangan Acak