Download - RNG- Simulasi Sistem Diskrit (Final)
Aris Fanani 5111201012 M. Mahaputra Hidayat 5111201037Click to edit Master subtitle style
Random-Number Generation 3/19/12
Outline
3/19/12
Semula dihasilkan secara atau mekanis, misal:
Definition ofrandom numbers
manual
Melempar dadu Mengocok kartu
Pendekatan komputer
modern
menggunakan
Random number yaitu barisan angka yang tidak dapat diprediksi kemunculannya yang dihasilkan dengan algoritma tertentu 3/19/12
Properties of random numbers
Dua sifat statistik yang sangat penting:
Uniform Independen
Random number Ri harus Gambar 1. Pdf untuk random number independen diambil dari distribusi uniform dengan pdf:
3/19/12
Generating of pseudo-random numbers
Tidak ada komputasi yang benar-benar menghasilkan deret random number secara sempurna random number yang dihasilkan dengan rumus-rumus matematika adalah random number semu (pseudo), karena pembangkitan bilangannya dapat diulang kembali. Pembangkit deret random number semacam itu disebut pseudo-random number generator (PRNG)3/19/12
Generating of pseudorandom numbers
Hal-hal yang perlu dipertimbangkan dalam Random number routines:v
Fast Portable untuk komputer yang berbeda Memiliki siklus yang panjang Replicable Uniform dan independen
v
v
v
v
3/19/12
Techniques for generating random numbers
Linear Congruential Method (LCM) Combined Linear Generation(CLGC) Congruential
3/19/12
Linear Congruential Method (LCM) LCM memanfaatkan model linear untukmembangkitkan random didefinisikan dengan : number yang
dimana : Xi : random number ke-i a,c m : modulus
: konstanta LCM
Random number antara 0 dan 1 dapat dihasilkan dengan rumus:
3/19/12
Linear Congruential Method (LCM)
Jika c 0, disebut Mixed congruential method
Jika c = 0, disebut Multiplicative congruential method
3/19/12
Contoh LCM 1Membangkitkan random number sebanyak 8 kali dengan a=2, c=7, m = 10 dan x0=2 x1 = ( 2 (2) + 7 ) mod 10 = 1 (7) + 7 ) mod 10 = 1 x2 = ( 2 (1) + 7 ) mod 10 = 9 (1) + 7 ) mod 10 = 9 x3 = ( 2 (9) + 7 ) mod 10 = 5 (9) + 7 ) mod 10 = 53/19/12 x4 = ( 2 (5) + 7 ) mod 10 = 7
x5 = ( 2 x6 = ( 2 x7 = ( 2 x8 = ( 2
Contoh LCM 2Membangkitkan random sebanyak 16 kali dengan a=4, b=7, m = 15 dan x0=3 X1 = ( 4 (3) + 7 ) mod 15 = 4 ( 4 (7) + 7 ) mod 15 = 13 X2 = ( 4 (4) + 7 ) mod 15 = 8 ( 4 (13) + 7 ) mod 15 = 14 X3 = ( 4 (8) + 7 ) mod 15 = 5 ( 4 (14) + 7 ) mod 15 = 3 X 4= ( 4 (5) + 7 ) mod 15 = 12 3/19/12 X9= X10 = X11 = X12= number
Kesimpulan LCM
Terjadi pengulangan pada periode waktu tertentu atau setelah sekian kali pembangkitan LGC mempunyai periode tidak lebih besar dari m, dan pada kebanyakan kasus periodenya kurang dari itu LGC mempunyai periode penuh (m1) jika memenuhi syarat berikut:1.
c relatif prima terhadap m. a 1 dapat dibagi dengan semua
3/19/12 2.
Combined Linear Congruential Generation(CLGC)
Alasan: Pembangkitan random number dengan periode yang lebih panjang karena meningkatnya kompleksitas dari sistem simulasi Pendekatan: mengkombinasikan dua atau lebih multiplicative congruential generator Misalkan Xi,1 , Xi,2 , , Xi,k , adalah output ke-i dari k multiplicative congruential generator berbeda.
3/19/12
Combined Linear Congruential Generation(CLGC) , Wi,k Theorema : jika Wi,1 , Wi,2 , independent discrete-valued random variable dan Wi,1 berdistribusi uniform [0, m1- 2] kemudian
adalah berdistribusi uniform pada [0, m1- 2]
3/19/12
Mengusulkan bentuk:
Combined Linear Congruential Generation(CLGC)
Periode maksimum yang mungkin adalah:
3/19/12
Contoh CLGC
Untuk 32-bit komputer, LEcuyer[1988] menyarankan menggabungkan k=2 pembangkit, dengan m1 =2,147,483,562, a1=40,014 m2= 2,147,483,399 dan a2=20,692 Algoritma menjadi: Langkah 1: Pilih Seed (umpan)q
1.
X1,0 dalam range [1, 2,147,483,562] untuk generator pertama X2,0 dalam range [1, 2,147,483,398]
3/19/12
q
Tests for Random Number
Pengujian dimaksudkan untuk melihat distribusi dari random number, urutan keacakannya.
3/19/12
Type of tests
Empiris:v
Berdasarkan sampel yang dihasilakan Statistik tes Dilakukan uji parameter pembangkit untuk pembangkitan secara menyeluruh.
v
Teoritis:v
3/19/12
Tests for Random Number
Dua kategori:q
Pengujian untuk uniform H0: R1 ~ U[0,1] H1: R1 U[0,1]
Kegagalan menolak H0 ,berarti bukti dari non uniform belum terdeteksiq
Pengujian untuk independen H0: R1 ~ independen H1: R1 independen
3/19/12
Frequency Test
Test untuk uniform Dua metode yang berbeda:v
Kolmogorov-Smirnov test Chi-square test
v
3/19/12
Kolmogorov-smirnov test
Membandingkan distribusi data (cdf continous, F(X) dari distribusi uniform dengan empiris cdf, SN(x), dari N sample yang diobservasi.
Kita tahu: F(x)= x, 0x1 Jika sample dari RN generation adalah R1 ,R2 , , RN
empiris cdf, SN(x) :
Berdasarkan statistik: D= max|F(x)3/19/12 SN(x)|
Kolmogorov-smirnov test
Prosedur kolmogorov-smirnov test :1.
Langkah 1: rangking data dari terbesar sampai terkecilR1 R2 RN
1.
Hitung :
3/19/12Hitung 1.
:
Contoh Kolmogorov-smirnov test
Misalkan 5 angka yang dihasilkan adalah 0.44, 0.81, 0.14, 0.15, 0.93 Langkah 1:i/N R(i) 0.05 0.14 0.44 0.81 0.93 0.20 0.40 0.60 0.80 1.00 0.15 0.26 0.16 0.07
Langkah 2: Langkah 3:
i/N R(i)
R(i) (i-1)/N0.05 -
= 0.26
0.04 0.21 0.13
Langkah 4: =0.05, D = 0.565 > D(0.26)3/19/12
Karena D < D, maka H0 diterima
Contoh Kolmogorov-smirnov test
Gambar 2. Komparasi F(x) dan SN(x)
3/19/12
Chi-square test
Uji Chi-square menggunakan sample statistik:
Dimana Oi : frekuensi yang diperoleh/observasi dalam i kelas Ei : frekuensi yang diharapkan dalam i kelas3/19/12
n : jumlah kelas
Contoh Chi-square test
Dibangkitkan 100 bilangan acak yang akan dikelompokkan dalam 10 kelompok kelas probabilitas.
3/19/12
Contoh Chi-square test
Pengujian:
Ho : data terdistribusi uniform HI : tidak terdistribusi uniform : 5% (0,05) Chi square hitung 2,4 artinya < tabel (16,919) Kesimpulan Ho diterima
Nilai Chi square tabel = 16,919
3/19/12
Uji autokorelasi
Uji ini akan melihat apakah terdapat korelasi antara setiap m bilangan dari urutan bilangan yang dimulai dari bilangan ke-i. koefisien autokorelasi akan melihat ada tidaknya korelasi di antara bilangan M adalah bilangan bulat terbesar yang memenuhi persamaan , dengan N adalah jumlah bilangan 3/19/12 dalam urutan tersebut.
Uji autokorelasi (Lanjutan)
Persamaan untuk estimator dan standar deviasinya adalah sebagai berikut :
3/19/12
Uji autokorelasi (Lanjutan II)
Sehingga dengan statistik berikut ini,
dapat diambil kesimpulan bahwa hipotesis urutan bilangan random saling bebas akan ditolak bila atau , adalah besarnya tingkat keyakinan.3/19/12
Contoh
[Test untuk Autokorelasi]
3/19/12
Kekurangan
[Test untuk Autokorelasi]
Tes ini tidak terlalu sensitif untuk nilai-nilai M yg kecil, terutama ketika bilangan yang diuji berada di sisi yang rendah.
3/19/12
Kesimpulan
Pada bab 7 ini, telah dibahas :
Pembangkit random number Pengujian untuk keseragaman dan independence
Meskipun generator telah digunakan selama bertahun-tahun, ditemukan beberapa kurang memadai. Juga, meskipun jika bilangan yang dihasilkan lulus tes, beberapa pola dasar mungkin tak terdeteksi. 3/19/12