BAB II PERTIDAKSAMAAN CHERNOFF

BAB II PERTIDAKSAMAAN CHERNOFF

BAB II PERTIDAKSAMAAN CHERNOFF 2.1

Pendahuluan

Di lapangan, yang menjadi perhatian umumnya adalah besar peluang dari peubah acak X pada beberapa nilai atau suatu selang, misalkan P(a<Xb) ataupun P (X≤a). Jika fungsi peluang dari X diketahui dengan pasti, hal ini tidak menjadi masalah. Bahkan untuk beberapa distribusi, seperti binomial, poisson, normal, t dan χ2 sudah ditabelkan. Tetapi dalam praktek, yang sering terjadi fungsi peluang X tidak diketahui dan informasi yang ada mengenai distribusi ini sangat terbatas. Misalkan yang dapat diketahui hanya parameter rataan µ atau variansi σ2. Untuk mengatasi ini, sering dipakai pertidaksamaan Chebyshev, yaitu P(( X − E[ X ]) 2 ≥ a 2 ) ≤

Var ( X ) σ2 2 2 − µ ≥ ≤ atau P (( X ) a ) a2 a2

(2.1)

Persamaan ini memberikan hampiran pada batas atas untuk peluang dari (X-µ)2 tidak kurang dari a2, dengan a sembarang. Jika µ dan σ2 juga tidak diketahui, pertidaksamaan ini masih bisa dipakai, dengan mensubstitusi µ dan σ2 masing-masing oleh rataam sampel X dan variansi sampel S n2−1 . Meskipun demikian, perlu dipelajari lebih dalam mengenai hampiran ini, baik terhadap hasil eksak ataupun terhadap pertidaksamaan lainnya. Hal ini akan dipelajari di bawah ini, tetapi sebelumnya akan dibahas pertidaksamaan Markov, yang sering dianggap sebagai dasar dari pertidaksamaan Chebyshev.

2.2

Pertidaksamaan Markov

Tidak diketahui siapa yang pertama kali mengemukakan pertidaksamaan Markov ini. Akan tetapi, di beberapa literatur disebutkan bahwa nama pertidaksamaan ini diambil dari nama salah seorang matematikawan Rusia bernama Andrey Markov. Dalam Ross, Introduction to Probability Models, hal 73, dituliskan

5


Definisi pertidaksamaan Markov Untuk setiap X ≥ 0 P( X ≥ a) ≤

E[ X ] a

(2.2)

dengan a > 0 Mengingat untuk membuktikan pertidaksamaan (2.2) harus dilakukan pada peubah acak diskrit dan kontinu, maka bukti pertidaksamaan ini dapat dipelajari pada Lampiran A.1. Mengingat pula definisi fungsi kehidupan (survival function) S(x), yaitu S(x) = 1- P( X≤x ), Dapat dikatakan bahwa ternyata pertidaksamaan (2.2) di atas bisa membantu perhitungan fungsi kehidupan. Fungsi S(x) ini sangat bermanfaat jika peubah acak X adalah usia dari makhluk hidup atau masa hidup barang elektronik. Dalam Tugas Akhir ini, fungsi kehidupan tidak dibahas terlalu dalam. Selanjutnya sebagai contoh aplikasi pertidaksamaan Markov, andaikan diketahui bahwa banyaknya barang yang diproduksi sebuah pabrik dalam 1 minggu mempunyai rataan 50. Maka peluang bahwa pada minggu ini produksi pabrik tersebut lebih dari 75 adalah sebagai berikut P ( X > 75) ≤

E[ X ] µ 50 2 = = = 75 75 75 3

Seperti telah dituliskan di Bab I, di bawah ini akan dijelaskan penggunaan pertidaksamaan Markov dari suatu distribusi yang diketahui fungsi peluangnya untuk membandingkan hampiran batas atas pertidaksamaan Markov dengan nilai sebenarnya. Hasil ini akan menjadi masukan untuk mempelajari kelebihan dan kekurangan pertidaksamaan Markov.

Contoh 2.1 Misalkan ada 10 ibu hamil tua dengan kondisi yang hampir sama. Andaikan pula mereka belum tahu jenis kelamin dari masing-masing janinnya. Jika peubah acak X menyatakan banyaknya anak perempuan yang akan lahir, maka X ~ binomial (10,

1 ). Di bawah ini telah 2

dihitung nilai P( X ≥ a) untuk beberapa nilai a dan hasilnya sebagai berikut:

6


PX ( ≥a)

PX ( ≥a) sebenarnya dari

( ≥a) Hasil akhir PX

eksak

Pertidaksamaan

dari Pertidaksamaan

Markov

Markov

P ( X ≥ 1)

0.99

5

1

P ( X ≥ 2)

0.98

2.5

1

P ( X ≥ 3)

0.95

1.67

1

P ( X ≥ 4)

0.83

1.25

1

P ( X ≥ 5)

0.62

1

1

P ( X ≥ 6)

0.377

0.83

0.83

P ( X ≥ 7)

0.172

0.71

0.71

P ( X ≥ 8)

0.055

0.625

0.625

P ( X ≥ 9)

0.011

0.556

0.556 Tabel 1

Tabel perbandingan PX ( ≥a) eksak dan hampiran dari pertidaksamaan Markov untuk distribusi binomial (10,1/2)

Tanpa mengingat bahwa besar total peluang tidak lebih dari 1, maka pertidaksamaan Markov memberikan nilai yang cukup memuaskan hanya untuk a = 4, 5. Untuk yang lainnya, hasil perhitungan jauh lebih besar, umumnya 1,5 kali nilai sebenarnya. Tetapi, jika nilai batas atasnya lebih dari 1 dan diganti oleh 1, maka nilai batas yang cukup memuaskan adalah untuk a = 1, ..., 5.

Contoh 2.2 Sebagai pendamping, di bawah ini dihitung hampiran Markov untuk peubah acak kontinu. Misalkan suatu perusahaan membuat bola lampu yang umurnya mengikuti distribusi normal

µ = 5 (dalam puluhan jam) dan σ2=10 (dalam ratusan jam).

PX ( ≥a)



eksak

Pertidaksamaan

dari Pertidaksamaan

Markov

Markov

P ( X ≥ 1)

0.896

5

1

P ( X ≥ 2)

0.829

2.5

1

P ( X ≥ 3)

0.736

1.67

1

7


PX ( ≥a)



eksak

Pertidaksamaan

dari Pertidaksamaan

Markov

Markov

P ( X ≥ 4)

0.622

1.25

1

P ( X ≥ 5)

0.5

1

1

P ( X ≥ 6)

0.375

0.83

0.83

P ( X ≥ 7)

0.264

0.71

0.71

P ( X ≥ 8)

0.171

0.625

0.625

P ( X ≥ 9)

0.1

0.556

0.556 Tabel 2

Tabel perbandingan PX ( ≥a) eksak dan hampiran dari pertidaksamaan Markov untuk distribusi normal (5,10)

Untuk distribusi kontinu normal pun, tidak jauh berbeda dengan hasil di atas. Dari Tabel 1 dan Tabel 2 dapat disimpulkan bahwa pertidaksamaan Markov memberikan batas atas yang cukup jauh dari nilai sebenarnya. Dalam pertidaksamaan (2.2) parameter yang terlibat hanyalah ukuran pemusatan µ. Sehingga jika ada dua peubah acak, masing-masing mempunyai distribusi yang berbeda, misalkan variansi berbeda jauh, tetapi rataan µ sama, maka hampiran pertidaksamaan Markovnya akan sama. Hal ini tentu akan sangat menyesatkan jika diterapkan di lapangan, khususnya dalam menganalisa data. Untuk itu pertidaksamaan (2.2), perlu dimodifikasi dengan melibatkan parameter lain yang lebih representatif dari distribusi X. Dari studi singkat di atas dapat disimpulkan bahwa pertidaksamaan Markov cukup mudah untuk digunakan, tetapi 1. Hanya berlaku terbatas untuk peubah acak non-negatif 2. Pada beberapa nilai a, hampiran yang diberikan sangat jauh dari nilai sebenarnya. 3. Batas atas dari pertidaksamaan Markov bisa bernilai lebih dari 1, dengan kata lain hampiran yang diberikan over-estimate. 4. Dua peubah acak dimana masing-masing distribusi peluangnya berlainan akan mempunyai batas atas yang sama.

8


Sebagai tambahan, jika di lapangan ingin dipakai pertidaksamaan ini, tetapi E[ X ] = µ tidak diketahui, maka µ dapat ditaksir oleh rataan sampel (rataan aritmatika) yaitu X .

2.3

Pertidaksamaan Chebyshev

Pada 1850 Pafnuty Chebyshev mengusulkan Pertidaksamaan Chebyshev sebagai berikut (lihat Sheldon Ross, 1997, A First Course in Probability, halaman 396) Untuk setiap X P (( X − E[ X ]) 2 ≥ a 2 ) ≤

Var ( X ) a2

(2.3)

1 k2

(2.4)

dengan a 2 > 0 atau P ( µ − kσ < X < µ + kσ ) ≥ 1 −

Pembuktian pertidaksamaan ini dapat dilhat di Lampiran A.2 Pertidaksamaan Chebyshev ini ternyata dibentuk dari pertidaksamaan Markov dengan mengambil peubah acaknya adalah ( X − µ ) 2 , kemudian a ditulis sebagai k , sehingga bentuk kuadratnya adalah k 2 , dan mengingat bahwa E[(X-µ)2] = Var (X) = σ2. Terlihat bahwa pertidaksamaan ini memperbaiki pertidaksamaan Markov yang hanya berlaku untuk peubah acak non-negatif. Jadi Pafnuty Chebyshev menemukan bahwa bagian luas antara dua nilai yang setangkup terhadap nilai rataan µ berkaitan dengan simpangan baku σ . Karena luas di bawah kurva distribusi peluang atau dalam histogram peluang berjumlah 1, maka luas antara dua bilangan sembarang menyatakan peluang peubah acak yang bersangkutan mendapat nilai antara kedua bilangan tersebut. Pertidaksamaan ini memberikan taksiran tentang peluang bahwa suatu peubah acak mendapat nilai dalam jarak k simpangan baku dari harga rataannya untuk setiap bilangan k real [1]. Dari definisi di atas dapat pula kita bentuk pertidaksamaan Chebyshev untuk satu sisi. (Lihat Sheldon Ross, 1997, A First Course in Probability , halaman 412). P( X − µ ≥ a) ≤

σ2 σ 2 + a2

dengan a > 0

(2.5)

9


Dengan menggunakan pertidaksamaan ini akan lebih mudah untuk membandingkan penggunaan dari pertidaksamaan Markov dan Chebyshev. Terlihat pula di atas, dibandingkan dengan pertidaksamaan Markov, jika ada dua peubah acak yang rataannya sama, tetapi variansinya berbeda maka batas atasnya pun akan berbeda. Pertidaksamaan Chebyshev dapat digunakan untuk sebarang peubah acak. Hal ini terlihat dari bentuknya yang dikuadratkan. Ini merupakan salah satu keunggulannya. Selain itu, dalam banyak kasus akan memberikan batas yang lebih baik dibandingkan pertidaksamaan Markov karena dalam perhitungannya menggunakan variansi dari peubah acak X yang memberikan informasi mengenai penyebaran atau keragaman data. Sebagai bahan perbandingan pula akan diberikan tabel perbandingan nilai P ( X − µ ≥ a ) secara eksak dengan nilai P ( X − µ ≥ a) yang diperoleh dengan menggunakan pertidaksamaan Markov dan Chebyshev dengan kasus yang sama seperti Contoh 2.1 P ( X − µ ≥ a)

Hasil P ( X − µ ≥ a)

Hasil P ( X − µ ≥ a )

eksak

dari P. Markov

dari P.Chebyshev

P ( X − 5 ≥ 1)

0.377

0.83

0.82

P ( X − 5 ≥ 2)

0.172

0.71

0.61

P ( X − 5 ≥ 3)

0.055

0.625

0.41

P ( X − 5 ≥ 4)

0.011

0.556

0.28

Tabel 3 Tabel perbandingan PX ( ≥a) eksak dan hampiran dari pertidaksamaan Chebyshev untuk distribusi binomial (10, 1/2)

Terlihat dari Tabel 3, pada kasus ini, batas atas dari pertidaksamaan Markov dan pertidaksamaan Chebyshev hampir sama, meskipun jauh dari nilai eksaknya. Keduanya menghasilkan hasil yang selalu over estimated.

Akan tetapi, hasil dari pertidaksamaan

Chebyshev lebih kecil dari pertidaksamaan Markov. Tetapi perlu diperhatikan, bahwa studi banding antara Markov dan Chebyshev di atas, hanya dilakukan pada beberapa nilai X, mengingat syarat besar a pada pertidaksamaan (2.5) harus positif. Nilai taksiran Markov untuk a = 1, 2, ..., 5 tidak bisa dibandingkan dengan hampiran Chebyshev. Hal ini disebabkan sifat setangkup dari pertidaksamaan Chebyshev. 10


Untuk kasus kontinu, seperti pada Contoh 2.2 , di bawah ini diberikan pula hasil perhitungan dari pertidaksamaan Chebyshev kemudian dibandingkan dengan pertidaksamaan Markov P ( X − µ ≥ a)



Eksak

Dari P. Markov

dari P.Chebyshev

P ( X − 5 ≥ 1)

0.375

0.83

0.9

P ( X − 5 ≥ 2)

0.264

0.71

0.7

P ( X − 5 ≥ 3)

0.171

0.625

0.52

P ( X − 5 ≥ 4)

0.1

0.556

0.38

Tabel 4 Tabel perbandingan P(( X − E[ X ]) ≥ a ) eksak dan hampiran dari pertidaksamaan Chebyshev untuk distribusi 2

2

normal (5,10)

Terlihat dari Tabel 4, pada kasus ini, batas atas dari pertidaksamaan Markov dan Chebyshev hampir sama, meskipun jauh dari nilai eksaknya. Keduanya menghasilkan hasil yang selalu over-estimated. Akan tetapi, hasil dari pertidaksamaan Chebyshev lebih kecil dari pertidaksamaan Markov kecuali untuk P ( X − 5 ≥ 1) .

Sama halnya dengan pertidaksamaan Markov, pertidaksamaan Chebyshev juga terbatas di 1 karena menghampiri nilai peluang. Oleh karena itu, hasil sebenarnya dari pertidaksamaan Chebyshev yang lebih dari 1 dapat diganti menjadi bernilai 1. Dari tabel 3 dan 4 dapat disimpulkan bahwa pertidaksamaan Chebyshev dapat menghampiri nilai P ( X − µ ≥ a ) dengan cukup dekat dengan nilai sebenarnya. Dapat diperhatikan juga karena nilai variansi cukup besar, hasil batas dari pertidaksamaan Chebyshev untuk a yang kecil kurang begitu dekat dengan nilai sebenarnya. Dapat dikatakan bahwa pertidaksamaan Chebyshev lebih baik dibandingkan pertidaksamaan Markov. Akan tetapi, hal ini belum menjadikan pertidaksamaan ini selalu menghasilkan nilai yang paling baik karena rataan dan variansi belum menggambarkan distribusi secara keseluruhan. .

11


Dari studi singkat di atas dapat diambil beberapa kesimpulan mengenai pertidaksamaan Chebyshev, yaitu 1. Pertidaksamaan ini adalah perbaikan dari pertidaksamaan Markov, khususnya untuk sembarang distribusi 2. Pada beberapa nilai a, hampiran yang diberikan masih cukup jauh dari nilai sebenarnya, batas atas bisa lebih dari 1. 3. Meskipun telah memasukkan faktor variansi, tetapi jika ada dua peubah acak dimana masing-masing distribusi peluangnya berlainan, tetapi rataan dan variansinya sama, maka batas atas dari pertidaksamaan Chebyshev pada masing-masing peubah acak tersebut akan bernilai sama Sebagai tambahan, jika di lapangan ingin dipakai pertidaksamaan ini, tetapi E[ X ] = µ dan variansi tidak diketahui, maka µ dan σ2 masing dapat ditaksir oleh rataan sampel (rataan aritmatika) X dan variansi sampel S n2−1 .

Lalu bagaimana jika diinginkan pertidaksamaan yang dapat menghasilkan nilai hampiran yang lebih dekat dengan nilai sebenarnya?

Di dalam dunia informatika mulai dikenal

pertidaksamaan Chernoff.

2.4

Pertidaksamaan Chernoff

Pertidaksamaan Chernoff ini dikemukakan oleh Herman Chernoff, seorang matematikawan Amerika, pada tahun 1952 [8]. Pertidaksamaan ini menggunakan fungsi pembangkit momen dalam perhitungannya, karena itu banyak pendapat bahwa pertidaksamaan ini menghasilkan nilai yang lebih akurat, dekat dengan nilai sebenarnya karena fungsi pembangkit momen cukup mewakili informasi distribusi secara keseluruhan. Hal ini disebabkan sifat fungsi pembangkit momen yang satu-satu pada dengan distribusinya. Misal M (t ) = E ⎡⎣etX ⎤⎦

adalah fungsi pembangkit momen untuk variabel acak X. Maka untuk t ≥ 0 dan a > 0 , dengan menggunakan pertidaksamaan Markov dapat diperoleh P( X ≥ a ) = P{etX ≥ eta } ≤ E ⎡⎣etX ⎤⎦ e − ta 12


Sedangkan untuk t < 0 dan a > 0 diperoleh P( X ≤ a ) = P{etX ≥ eta } ≤ E ⎡⎣etX ⎤⎦ e − ta Pertidaksamaan ini dikenal dengan sebutan Chernoff bounds. P ( X ≥ a ) ≤ e − ta ⋅ M ( t ) , untuk setiap t > 0 P ( X ≤ a ) ≤ e − ta ⋅ M ( t ) , untuk setiap t < 0

(2.6)

(lihat Ross, 1997, A First Course in Probability, hal 415) Karena Chernoff bounds memenuhi semua nilai t baik positif atau negatif, dapat dicari nilai batas dari P ( X ≥ a ) dengan menggunakan t yang dapat meminimumkan e − ta ⋅ M (t ) . Bentuk pertidaksamaan (2.6) di atas merupakan bentuk umum dari pertidaksamaan Chernoff.

2.5

Pertidaksamaan Chernoff untuk Beberapa Distribusi

Telah disebutkan sebelumnya bahwa pertidaksamaan Chernoff menggunakan fungsi pembangkit momen yang berfungsi satu-satu dengan fungsi distribusi. Oleh karena itu, bentuk pertidaksamaan Chernoff akan berbeda untuk setiap distribusi. Di sini akan dibahas pembentukan pertidaksamaan Chernoff untuk beberapa distribusi.

A.

Distribusi Geometrik (G(p))

Berikut ini akan diberikan pembentukan pertidaksamaan Chernoff untuk distribusi Geometrik,G(p).

Fungsi pembangkit momen untuk distribusi ini mengandung fungsi

eksponensial dan juga bentuk pecahan sehingga perhitungan matematisnya akan cukup sulit. Fungsi pembangkit momen untuk distribusi geometrik dapat diberikan sebagai berikut,

[ ]

M (t ) = E e tX ∞

M (t ) = ∑ etX p(1 − p) x =1

∞

= pet ∑ (et (1 − p)) x −1 x =1 ∞

= pe ∑ (et (1 − p))n t

n =0

=

p e − (1 − p) −t

(2.7)

13


P ( X ≥ a ) ≤ e − ta ⋅ E ⎡⎣ e tX ⎤⎦

(2.8)

Bentuk pertidaksamaan (2.8) di atas mengandung

e−ta di

sebelah kanannya. Hal ini akan

menyulitkan perhitungan, untuk itu ln-kan pertidaksamaan tersebut, mengingat ln adalah suatu transformasi yang bersifat mengawetkan kemonotonan. Jadi pertidaksamaan ini dapat diubah menjadi ln P ( X ≥ a ) ≤ − ta + ln E ⎡⎣ e tX ⎤⎦ ≤ − ta + ln

e

−t

p − (1 − p )

(2.9)

Selanjutnya harus dicari t yang paling optimal agar batas atas P( X ≥ a) dapat dihampiri dengan baik. Titik t ini dicari dengan meminimumkan ruas kanan dari pertidaksamaan (2.9). Dengan menurunkan fungsi di ruas kanan tersebut terhadap t dan menyamadengankannya dengan 0, bisa didapatkan t yang paling sederhana yaitu ⎛ ⎞ p ∂ ⎜ −ta + ln − t e − (1 − p ) ⎟⎠ ⎝ =0 ∂t ∂ (−ta + ln p − ln(e − t − (1 − p))) =0 ∂t e−t −a + −t =0 e − (1 − p) (a − 1)e − t = a(1 − p ) a(1 − p) (a − 1) a(1 − p) t = − ln (a − 1)

e−t =

t = − ln

a (1 − p ) . Selanjutnya t ini akan menghasilkan a −1 ⎛

⎜ ln p = e⎝ P( X ≥ a) ≤ e . − t e − (1 − p ) − ta

a (1− p ) ⎞ ⎟ a. a −1 ⎠

p e

⎛ a (1− p ) ⎞ ⎜ ln ⎟ a −1 ⎠ ⎝

− (1 − p )

a

⎡ a(1 − p) ⎤ ⎡ p(a − 1) ⎤ Jadi P(X ≥ a) ≤ ⎢ ⎥ ⎥ .⎢ ⎣ a −1 ⎦ ⎣ 1− p ⎦

(2.10)

14


Jadi bentuk pertidaksamaan (2.10) merupakan bentuk pertidaksamaan Chernoff untuk distribusi geometrik (G(p))

B.

Distribusi Binomial (B(n,p))

Fungsi pembangkit momen untuk distribusi binomial (B(n.p)) dapat diberikan sebagai berikut M (t ) = [(1 − p ) + pet ]n Fungsi pembangkit momen tersebut dapat disubstitusikan ke dalam bentuk pertidaksamaan (2.8) sehingga diperoleh P( X ≥ a ) ≤ e − ta ⋅ [(1 − p) + pet ]n

(2.11)


e−ta di


menyulitkan perhitungan, untuk itu ln-kan pertidaksamaan tersebut, mengingat ln adalah suatu transformasi yang bersifat mengawetkan kemonotonan. Jadi pertidaksamaan ini dapat diubah menjadi ln P( X ≥ a ) ≤ −ta + n. ln((1 − p ) + pet ) kemudian akan dicari t yang optimal dengan menurunkan fungsi yang ada di sebelah kanan pertidaksamaan terhadap t ∂ ( − ta + n. ln((1 − p ) + pe t )) =0 ∂t n. pe t −a+ =0 (1 − p ) + pe t a (1 − p ) et = p (n − a ) a (1 − p ) Sehingga didapat t yang optimal adalah t = ln p (n − a)

Nilai t yang telah diperoleh disubstitusikan ke dalam bentuk pertidaksamaan (2.11) P ( X ≥ a ) ≤ e − ta ⋅ [(1 − p ) + pet ] a

⎡ p (n − a ) ⎤ ⎡ n(1 − p ) ⎤ ≤⎢ ⎥ ⎢ ⎥ ⎣ a (1 − p ) ⎦ ⎣ n − a ⎦

n

(2.12)

Jadi bentuk pertidaksamaan (2.12) merupakan bentuk Pertidaksamaan Chernoff untuk distribusi binomial (B(n,p))

15


C.

Distribusi Poisson (P(λ))

Fungsi pembangkit momen untuk distribusi Poisson (P(λ)) dapat diberikan sebagai berikut t

M(t) = eλ(e −1) Fungsi pembangkit momen tersebut dapat disubstitusikan ke dalam bentuk pertidaksamaan (2.8) sehingga diperoleh

P ( X ≥ a ) ≤ e − ta e λ ( e

t

− 1)

(2.13)


e−ta di


menyulitkan perhitungan, untuk itu ln-kan pertidaksamaan tersebut, mengingat ln adalah suatu transformasi yang bersifat mengawetkan kemonotonan. Jadi pertidaksamaan ini dapat diubah menjadi ln P( X ≥ a ) ≤ −ta + λ (et − 1) kemudian akan dicari t yang optimal dengan menurunkan fungsi yang ada di sebelah kanan pertidaksamaan terhadap t

∂ (−ta + λ (et − 1)) =0 ∂t t − a + λe = 0 a et =

λ

Sehingga didapat t optimal adalah t = ln

a

λ

Nilai t yang telah diperoleh disubstitusikan ke dalam bentuk pertidaksamaan (2.13)

P( X ≥ a) ≤ e

a⎤ ⎡ ⎢ − ln λ ⎥ a ⎣ ⎦

a

⎡ a ⎤ + λ ⎢ ( ) − 1⎥ ⎣ λ ⎦

⎛λ⎞ ≤ ⎜ ⎟ e( a −λ ) ⎝a⎠

(2.14)

Jadi bentuk pertidaksamaan (2.14) merupakan bentuk pertidaksamaan Chernoff untuk distribusi Poisson (P(λ))

16


D.

Distribusi Normal (N(µ,σ2))

Fungsi pembangkit momen untuk distribusi normal (N(µ,σ2)) dapat diberikan sebagai berikut µt +σ 2 t 2

M (t ) = e

2

Fungsi pembangkit momen tersebut dapat disubstitusikan ke dalam bentuk pertidaksamaan (2.8) sehingga diperoleh µt +σ 2 t 2 − ta

P( X ≥ a) ≤ e .e

(2.15)

2


e−ta di


menyulitkan perhitungan, untuk itu ln-kan pertidaksamaan tersebut, mengingat ln adalah suatu transformasi yang bersifat mengawetkan kemonotonan. Jadi pertidaksamaan ini dapat diubah menjadi ln P( X ≥ a) ≤ −ta +

µ t + σ 2t 2 2

kemudian akan dicari t yang optimal dengan menurunkan fungsi yang ada di sebelah kanan pertidaksamaan terhadap t ∂ (−ta +

µ t + σ 2t 2 ∂t

−a +

2

µ 2

)

=0

+ σ 2t = 0 t=

2a − µ 2σ 2

Nilai t yang telah diperoleh disubstitusikan ke dalam bentuk pertidaksamaan (2.15) − ta

P ( X ≥ a) ≤ e .e

µ t +σ 2t 2 2

4 a ( µ −a )− µ 2

≤e

=e

− ta +

µt +σ 2t 2 2

(2.16)

8σ 2

Jadi bentuk pertidaksamaan (2.16) merupakan bentuk pertidaksamaan Chernoff untuk distribusi normal (N(µ,σ2)).

17


E.

Distribusi Gamma (G(α,β))

Fungsi pembangkit momen untuk distribusi gamma (G(α,β)) dapat diberikan sebagai berikut M (t ) = (1 − β t ) −α dengan t <

1

β

Fungsi pembangkit momen tersebut dapat disubstitusikan ke dalam bentuk pertidaksamaan (2.8) sehingga diperoleh P( X ≥ a) ≤ e − ta .(1 − β t ) −α

(2.17)


e−ta di


menyulitkan perhitungan, untuk itu ln-kan pertidaksamaan tersebut, mengingat ln adalah suatu transformasi yang bersifat mengawetkan kemonotonan. Jadi pertidaksamaan ini dapat diubah menjadi ln P ( X ≥ a ) ≤ −ta + ln(1 − β t ) −α kemudian akan dicari t yang optimal dengan menurunkan fungsi yang ada di sebelah kanan pertidaksamaan terhadap t ∂ (e − ta (1 − β t ) −α ) =0 ∂t −a +

αβ =0 1− βt

, dengan t <

a − αβ aβ 1 α t= − β a t=

1

β

Nilai t yang telah diperoleh disubstitusikan ke dalam bentuk pertidaksamaan (2.17) P( X ≥ a) ≤ e

⎡1 α⎤ −⎢ − ⎥a ⎣β a ⎦

⎛ ⎡ 1 α ⎤⎞ . ⎜1 − β ⎢ − ⎥ ⎟ ⎣β a ⎦⎠ ⎝

αβ − a β

−α

−α

dengan t <

1

β

, α > 0, a > 0

-(2.18)

⎛ αβ ⎞ ⋅⎜ ⎟ ⎝ a ⎠ Jadi bentuk pertidaksamaan (2.18) merupakan bentuk Pertidaksamaan Chernoff untuk ≤e

distribusi gamma (G(α,β))

18


Dari uraian Sub-Bab 2.5 ini dapat disajikan dalam bentuk tabel bentuk-bentuk pertidaksamaan Chernoff untuk beberapa distribusi Distribusi

Pertidaksamaan Chernoff

Binomial (n,p)

⎡ p (n − a) ⎤ ⎡ n(1 − p ) ⎤ P( X ≥ a) ≤ ⎢ ⎥ ⎢ ⎥ ⎣ a(1 − p) ⎦ ⎣ n − a ⎦

Poisson (λ)

⎛λ⎞ P( X ≥ a) ≤ ⎜ ⎟ e(a−λ ) ⎝a⎠

a

n

a

Gamma (α,β)

P( X ≥ a) ≤ e

t< Normal (µ,σ2)

1

β

αβ − a β

−α

⎛ αβ ⎞ .⎜ ⎟ dengan ⎝ a ⎠

, α > 0, a > 0 4a(µ −a)− µ 2

P( X ≥ a) ≤ e

8σ 2

Tabel 5 Tabel Pertidaksamaan Chernoff untuk Beberapa Disribusi

Pertidaksamaan Chernoff dikatakan memberikan nilai peluang dari peubah acak dalam suatu selang yang cukup dekat dengan nilai sebenarnya karena menggunakan fungsi pembangkit momen dari distribusi peubah acak tersebut, yang mana fungsi pembangkit momen itu berfungsi satu-satu dengan fungsi distribusi. Pembentukan pertidaksamaan Chernoff dengan tahapan di atas hanya berlaku untuk suatu populasi yang telah diketahui distribusi datanya. Sebaliknya jika distribusi dari X tidak diketahui distribusinya, pertidaksamaan Chernoff ini masih bisa diterapkan, dengan 2 cara: 1. Mencari distribusi X dengan melalui metode pencocokan (fitting distribution, kemudian memakai distribusi pilihan ini sebagai informasi untuk menentukan fungsi pembangkit momennya.

Melalui cara ini, bisa memungkinkan lebih dari satu

distribusi yang bisa terpilih. Untuk itu dibutuhkan uji kecocokan anatara data dan distribusi yang dipilih. 2. Menentukan fpm taksiran, dengan menganggap data sebagai peubah acak diskrit. Cara ini sangat sulit, karena sangat tergantung dari data dan juga pengelompokkan yang dipilih. 19


2.6

Penggunaan Pertidaksamaan Chernoff

Untuk membandingkan penggunaan ketiga pertidaksamaan, dapat dilakukan perhitungan untuk distribusi binomial dan normal seperti Contoh 2.1 dan 2.2. Penggunaan ketiga pertidaksamaan untuk Contoh 2.1 dapat diberikan dalam tabel perbandingan nilai P ( X − µ ≥ a) secara eksak dengan nilai P ( X − µ ≥ a) yang diperoleh dengan menggunakan

Pertidaksamaan Markov, Chebyshev, dan Chernoff untuk suatu distribusi binomial (10, 1/2). P ( X − µ ≥ a)




eksak

dari P. Markov

dari P.Chebyshev

dari P.Chernoff

P ( X − 5 ≥ 1)

0.377

0.83

0.82

0.81

P ( X − 5 ≥ 2)

0.172

0.71

0.61

0.43

P ( X − 5 ≥ 3)

0.055

0.625

0.41

0.14

P ( X − 5 ≥ 4)

0.011

0.556

0.28

0.025

Tabel 6 Tabel perbandingan P ( X − µ ≥ a) eksak dan hampiran dari pertidaksamaan Chernoff untuk distribusi binomial (10, 0.5)

Selain itu, akan dibandingkan pula penggunaan pertidaksamaan Markov, Chebyshev, dan Chernoff untuk Contoh 2.2 sebagai berikut P ( X − µ ≥ a)




Eksak

dari P. Markov

dari P.Chebyshev

dari P.Chernoff

P ( X − 5 ≥ 1)

0.375

0.83

0.9

0.541

P ( X − 5 ≥ 2)

0.264

0.71

0.7

0.36

P ( X − 5 ≥ 3)

0.171

0.625

0.52

0.22

P ( X − 5 ≥ 4)

0.1

0.556

0.38

0.12

Tabel 7 Tabel perbandingan P ( X − µ ≥ a) eksak dan hampiran dari pertidaksamaan Chernoff untuk distribusi normal (5,10)

Selain bentuk umum Pertidaksamaan Chernoff yang disebutkan pada pertidaksamaan (2.4) dan bentuk-bentuk pertidaksamaan untuk beberapa distribusi yang disajikan dalam Tabel 5,

20


ada satu teorema yang menyangkut bentuk pertidaksamaan Chernoff untuk peubah acak binomial, yaitu sebagai berikut : Teorema 1

Jika X merupakan peubah acak binomial dengan ekspektasi E[ X ] ,

P[ X > (1 + δ ) E[ X ]] < e P[ X < (1 − δ ) E[ X ]] < e

−

−

δ2 3

δ2 2

E[ X ]

E[ X ]

dengan 0 < δ ≤ 1 Pembuktian teorema ini terdapat pada Lampiran A.3 Bentuk pertidaksamaan ini cukup banyak diaplikasikan dalam perhitungan, terutama dalam dunia komputasi karena berlaku untuk peubah acak diskrit. Selain itu bentuknya pun mudah untuk digunakan. Berikut ini merupakan contoh penggunaannya Contoh 2.3:

Dalam suatu permainan antara dua orang, peluang orang pertama menang adalah 2/3. Permainan tersebut dilakukan sebanyak 30 kali. Berapakah peluang terjadinya orang pertama menang tidak lebih dari setengah permainan? Dalam menyelesaikan permasalahan ini dapat digunakan bentuk Pertidaksamaan Chernoff dalam teorema 1 Misalkan X adalah peubah acak binomial yang menyatakan banyaknya kemenangan dalam permainan. 2 E[ X ] = n. p = 30. = 20 3 P ( X < 15) = P ( X > (1 − δ )20) maka δ =

P ( X < 15) < e

−

1 selanjutnya dapat dilakukan perhitungan 4

(1/ 4) 2 .20 3

P ( X > 15) < 0.5352

dengan menggunakan pertidaksamaan Chebyshev didapatkan P ( X < 15) < 0.266

Pada contoh 2.3 ini dapat dilihat bahwa pertidaksamaan Chebyshev malah memberikan batas yang lebih baik. Dapat diperkirakan bahwa yang berperan dalam permasalahan ini adalah 21


parameter δ . Untuk itu akan diberikan contoh lainnya yang memberikan nilai parameter δ yang dekat dengan 1.

Contoh 2.4:

Dengan permainan yang serupa seperti contoh 1, berapa peluang terjadinya orang pertama menang tidak lebih dari 1/6 permainan? Pertidaksamaan Chernoff pada teorema 1 akan menghasilkan δ =

P( X < 5) < e

−10

9 16

3 sehingga 4

= 0.0036

dengan menggunakan Pertidaksamaan Chebyshev dapat diperoleh P ( X < 5) < 0.029

Dapat disimpulkan bahwa untuk δ yang mendekati 1 Pertidaksamaan Chernoff menghasilkan batas yang lebih baik dibandingkan Pertidaksamaan Chebyshev. Selain itu, contoh kasus lain yang menunjukkan keakuratan pertidaksamaan Chernoff adalah pada kasus sebagai berikut

Contoh 2.5:

Dengan permainan yang serupa seperti contoh 1, tetapi permainan dilakukan sebanyak 300 kali. Berapa peluang terjadinya orang pertama menang tidak lebih dari setengah permainan? Pertidaksamaan Chernoff pada teorema 1 akan menghasilkan P ( X < 150) < 0.0266 , sedangkan Pertidaksamaan Chebyshev menghasilkan P ( X < 150) < 0.0019 Dapat disimpulkan pula bahwa untuk n yang besar, Pertidaksamaan Chernoff akan menghasilkan batas yang lebih baik.

2.7

Skema Penggunaan Pertidaksamaan

Teori statistika inferensi terdiri atas metode untuk menarik inferensi atau rampatan mengenai populasi [1]. Dalam melakukan statistika inferensi ini di lapangan ada beberapa kemungkinan yang terjadi. Kemungkinan pertama, distribusi dari populasi diketahui secara penuh atau menyeluruh. Hal ini akan memudahkan karena perhitungan peluang dapat langsung dilakukan dengan menggunakan fungsi distribusinya. Akan tetapi, bagaimana halnya dengan populasi yang hanya diketahui sebagian informasinya? Misalnya hanya diketahui rataannya saja atau 22


variansinya saja. Dalam hal ini pertidaksamaan dapat berperan. Skema penggunaan pertidaksamaan dapat dilihat di bawah ini, POPULASI f (x )

Diketahui secara menyeluruh

Hanya diketahui sebagian informasi Mis: rataan dan variansi

Peluang suatu selang ((P(X=c) atau P(a<X
fitting distribution

Markov Chebyshev Chernoff

P ( X ≥ a ) dapat dihitung secara eksak dengan menggunakan f (x )

23

BAB III SIMULASI PENGGUNAAN PERTIDAKSAMAAN PADA DISTRIBUSI

BAB III SIMULASI PENGGUNAAN PERTIDAKSAMAAN PADA DISTRIBUSI 3.1 Pendahuluan

Pada bab sebelumnya telah dibahas mengenai pertidaksamaan Chernoff dengan terlebih dahulu diberi pemaparan mengenai dua pertidaksamaan yang sudah cukup sering dipergunakan yaitu pertidaksamaan Markov dan pertidaksamaan Chebyshev. Telah disebutkan bahwa pertidaksamaan Chernoff memberikan batas yang paling dekat dengan nilai sebenarnya.

Untuk membandingkan batas yang dihasilkan oleh ketiga pertidaksamaan tersebut pada suatu populasi dapat dilakukan sebuah simulasi. Simulasi dilakukan dengan mengenerate data untuk sebuah distribusi kemudian menghitung nilai peluang suatu selang tertentu dengan menggunakan frekuensi relatif yang dihitung dari data tersebut (tanpa melihat distribusinya). Hasil perhitungan secara eksak akan dibandingkan dengan hasil perhitungan dengan menggunakan ketiga bentuk pertidaksamaan. Berikut ini hasil simulasi untuk distribusi binomial dan distribusi normal:

3.2 Simulasi untuk Distribusi Binomial

Pada simulasi pertama untuk suatu data berdistribusi binomial (10, 0.30) di-generate sebanyak 300 data, sebagai berikut

X 0 1 2 3 4

Frekuensi

frekuensi relatif

9 29 64 73 70

0.03 0.097 0.213 0.243 0.233

Frekuensi relatif komulatif 0.03 0.127 0.34 0.583 0.817

hampiran peluang binomial (10, 0.3) (sumber: Walpole) 0.0282 0.1493 0.3828 0.6496 0.8497

24


X 5 6 7 8

frekuensi relatif 0.11 0.06 0.01 0.003

Frekuensi 33 18 3 1

Frekuensi relatif komulatif 0.927 0.987 0.997 1 Tabel 8

hampiran peluang binomial (10, 0.3) (sumber: Walpole) 0.9527 0.9894 0.9984 0.9999

Data Simulasi 1

Distribusi penyebaran data simulasi 1 tersebut dapat digambarkan dalam histogram berikut:

Histogram Data Simulasi 1 80 70

frekuensi

60 50 40 30 20 10 0 1

2

3

4

5

6

7

8

9

x

Gambar 1 Histogram Data Simulasi 1

selain itu statistik dari data tersebut dapat disajikan sebagai berikut : Univariate Statistics Variable 1 Count Sum Average Median Mode Minimum Maximum Range Standard Deviation

300 958 3.19 3 3 0 8 8 1.516

25


2.297 0.191

Variance Skewness

-0.185

Kurtosis Tabel 9

Tabel Informasi Statistik untuk Data Simulasi 1

Dari informasi di atas dapat dilihat bahwa range data cukup besar. Hal ini juga menyebabkan data tersebar cukup luas. Titik puncak dari data berada di sekitar rataan, sehingga kemiringan dari grafik data pun cukup kecil.

Dalam melakukan simulasi penggunaan pertidaksamaan pada distribusi data ini diambil nilai peluang salah satu selang yaitu P( X ≥ 4) . Nilai peluang secara eksak dapat dihitung dengan menggunakan frekuensi relatifnya

P ( X ≥ 4) = 1 − P( X < 4) = 1 − [ P ( X = 3) + P( X = 2) + P( X = 1) + P( X = 0)] = 0.417

(3.2)

Kemudian dengan menggunakan pertidaksamaan dapat diperoleh hasil sebagai berikut Pertidaksamaan Markov: P ( X ≥ 4) ≤

E[ X ] 3.19 = = 0.7975 4 4

(3.3)

Pertidaksamaan Chebyshev: P ( X − 3.19 ≥ 0.81) ≤ P ( X − 3.19 ≥ 0.81) ≤

σ2 σ 2 + (0.81) 2 2.297 2,297 + 0.6561

(3.4)

P ( X ≥ 4) ≤ 0.77 Dalam menghitung batas atas pertidaksamaan Chernoff P ( X ≥ 4) terdapat sedikit kesulitan dalam mencari bentuk fungsi pembangkit momen hampirannya. Perlu bantuan komputer dalam mencari fungsi tersebut. Fungsi pembangkit momen hampirannya tersebut

dihitung

dengan

menggunakan

komputasi

sehingga

didapatkan

hasil

pertidaksamaan Chernoff sebagai berikut:

P ( X ≥ 4) ≤ 0.724

(3.5)

26


Dari simulasi data yang terdistribusi binomial (10, 0.30) ini dapat ditunjukkan bahwa pertidaksamaan Chernoff menghasilkan batas yang paling baik, mendekati nilai sebenarnya. Hal ini bisa diakibatkan karena jumlah datanya yang cukup banyak atau karena penyebaran datanya yang cukup besar. Simulasi lain dilakukan untuk beberapa nilai p, misalnya untuk p=0.5 dengan data sebagai berikut :

Frekuensi

X

frekuensi relative

1 2 3 4 5 6 7 8 9

3 22 64 109 135 96 47 17 6

0.006 0.044 0.128 0.218 0.27 0.192 0.094 0.034 0.012

10

1

0.002

Tabel 10 Tabel Data Simulasi Binomial (10, 0.5)

Pertidaksamaan Chernoff juga memberikan batas yang paling akurat pada simulasi ini. Simulasi lain juga dilakukan untuk distribusi dari peubah acak kontinu, yaitu distribusi normal. Hasil simulasi tersebut dapat dilihat sebagai berikut

3.3 Hasil Simulasi untuk Distribusi Normal

Pada simulasi pertama untuk distribusi normal di-generate data sebanyak 200 dengan mean ( µ ) = 7 dan standar deviasi (σ ) =2

nilai tengah

Frekuensi

2.00-3.00 3.00-4.00 4.00-5.00 5.00-6.00 6.00-7.00

2.5 3.5 4.5 5.5 6.5

6 7 21 33 43

0.03 0.035 0.105 0.165 0.215

0.03 0.065 0.17 0.335 0.55

7.00-8.00

7.5

37

0.185

0.735

Selang

Frekuensi relative

frekuensi relative komulatif

27


nilai tengah

Frekuensi

8.00-9.00

8.5

20

0.1

0.835

9.00-10.00

9.5

19

0.095

0.93

10.00-11.00

10.5

10

0.05

0.98

11.00-12.00

11.5

4

0.02

1

Selang

Frekuensi relative

frekuensi relative komulatif

Tabel 11 Data Simulasi 2

Data mentah untuk simulasi ini dapat dilihat pada lampiran C. Distribusi penyebaran data simulasi 2 tersebut dapat digambarkan dalam histogram berikut:

12.482112

11.714424

10.946736

10.179047

9.411359

8.643671

7.875982

7.108294

6.340606

5.572917

4.805229

4.037541

3.269852

2.502164

50.0 40.0 30.0 20.0 10.0 0.0 1.734476

frekuensi

Histogram Data Simulasi 2

x

Gambar 2 Histogram Data Simulasi 2

Dengan statistik yang diperoleh dari data tersebut sebagai berikut :

Univariate Statistics Variable 1 Count Sum Average

200 1,382.3916 6.911958

Median

6.8740

Minimum

2.1020

Maximum

11.7450

28


9.6430

Range Standard Deviation

1.9513442

Variance

3.8077442 0.103

Skewness

-0.150

Kurtosis Tabel 12

Tabel Informasi Statistik Data Simulasi 2

Dari informasi di atas dapat diketahui bahwa range data cukup besar. Hal ini juga menyebabkan data tersebar cukup luas. Titik puncak dari data berada di sekitar rataan, sehingga kemiringan dari grafik data pun cukup kecil.

Dalam melakukan simulasi penggunaan pertidaksamaan pada distribusi data kontinu ini diambil nilai peluang salah satu selang yaitu P( X ≥ 7) . Nilai peluang secara eksak dapat

dihitung dengan menggunakan frekuensi relatifnya P ( X ≥ 7) = 1 − P ( X < 7) = 0.45

(3.6)

atau jika kita menggunakan tabel distribusi normal [1] bisa didapatkan P ( X ≥ 7) = 1 − P ( X < 7) = 0.5

Kemudian dengan menggunakan pertidaksamaan dapat diperoleh hasil sebagai berikut Pertidaksamaan Markov : E[ X ] 7 6.911958 P ( X ≥ 7) ≤ = 0.9874 7 P ( X ≥ 7) ≤

(3.7)

Pertidaksamaan Chebyshev: P ( X − 6.911958 ≥ 0.088042) ≤ P ( X ≥ 7) ≤

σ2 σ + (0.088042)

3.8077442 = 0.975 3.8077442 + 0.0077513934

(3.8)

Dalam menghitung batas atas pertidaksamaan Chernoff P ( X ≥ 7) terdapat sedikit kesulitan dalam mencari bentuk fungsi pembangkit momen hampirannya. Perlu bantuan

29


komputer dalam mencari fungsi tersebut. Fungsi pembangkit momen hampirannya tersebut dihitung dengan menggunakan komputasi dan akan didapatkan hasil pertidaksamaan Chernoff sebagai berikut: P ( X ≥ 7) ≤ 0.864

(3.9)

Simulasi lain dilakukan untuk beberapa distribusi normal lainnya dan menghasilkan hal yang serupa. Pertidaksamaan Chernoff menghasilkan batas yang paling akurat mendekati nilai sebenarnya.

Dari simulasi ini dapat ditunjukkan bahwa untuk beberapa kasus pada distribusi binomial dan normal, pertidaksamaan Chernoff selalu menghasilkan batas atas dari nilai peluang

P(X ≥ a) yang lebih akurat dibandingkan pertidaksamaan Markov dan Chebyshev. Meskipun dalam perhitungannya lebih sulit dikerjakan dibandingkan dengan kedua pertidaksamaan lainnya.

30

BAB II PERTIDAKSAMAAN CHERNOFF

Recommend Documents