Probabilitas dan Proses Stokastika PDF

Probabilitas dan Proses Stokastika Reza Pulungan Departemen Ilmu Komputer dan Elektronika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Gadjah Mada Yogyakarta September 18, 2024 Ekspektasi Deﬁnisi Ekspektasi atau nilai harapan adalah sebuah bilangan yang mengungkapkan banyak hal tentang perilaku variabel random. Deﬁnition Jika R adalah sebuah variabel random yang dideﬁnisikan pada sebuah sample space S, maka expectation (ekspektasi) atau expected value (nilai harapan) dari R adalah: X E (R) ::= R(ω) · Pr(ω). ω∈S Andaikan S adalah himpunan semua mahasiswa di kelas ini, dan kita pilih seorang mahasiswa secara random dan uniform. Andaikan R adalah nilai ujian mahasiswa yang dipilih. Maka ekspektasi (E (R)) adalah nilai rata-rata kelas itu. Reza Pulungan Probabilitas dan Proses Stokastika 3 Ekspektasi v.r. Uniform Andaikan R adalah variabel random representasi dari nilai hasil pelemparan dadu yang tidak bias. Ekspektasi dari R adalah: 1 1 1 1 1 1 7 E (R) = 1 · + 2 · + 3 · + 4 · + 5 · + 6 · =. 6 6 6 6 6 6 2 Istilah “nilai harapan” sebetulnya tidak tepat. Kita tidak mengharapkan bahwa nilai dari dadu sama dengan 3 12. Ekspektasi berbeda dengan median atau nilai tengah dari distribusi: Deﬁnition Median dari variabel random R adalah nilai x ∈ range(R) s.s.: 1 1 Pr(R ≤ x ) ≤ dan Pr(R > x ) <. 2 2 Reza Pulungan Probabilitas dan Proses Stokastika 4 Ekspektasi v.r. Uniform Secara umum, jika Rn adalah variabel random dengan distribusi uniform dengan sample space S = {1, 2, · · · , n}, maka: n X 1 n(n + 1) n+1 E (Rn ) = i· = =. n 2n 2 i =1 Reza Pulungan Probabilitas dan Proses Stokastika 5 Ekspektasi v.r. Indikator Ekspektasi dari variabel random indikator untuk suatu event sama saja dengan probabilitas event tersebut: Lemma Jika IA adalah variabel random indikator untuk event A, maka: E (IA ) = Pr(A). Reza Pulungan Probabilitas dan Proses Stokastika 6 Deﬁnisi Alternatif Theorem Jika R adalah sebuah variabel random yang dideﬁnisikan pada sebuah sample space S, maka: X X E (R) = x · Pr(R = x ) = x · PDFR (x ). x ∈range(R) x ∈range(R) Corollary Jika range dari sebuah variabel random R adalah N, maka: ∞ X ∞ X E (R) = i · Pr(R = i ) = Pr(x > i ). i =1 i =0 Reza Pulungan Probabilitas dan Proses Stokastika 7 Mean-Time-to-Failure Mean-Time-to-Failure (MTTF) adalah parameter penting dalam desain semua sistem. Andaikan sebuah program komputer crash di akhir setiap jam dengan probabilitas p. Berapakah ekspektasi dari waktu yang dilalui sampai program tersebut crash? Nilai ekspektasi ini disebut dengan MTTF. Jawaban: asumsikan C adalah v.r. untuk jumlah jam sampai crash, maka yang kita cari adalah E (C). C adalah v.r. dengan range N, maka berdasarkan corollary sebelumnya: ∞ X E (C) = Pr(C > i ). i =0 Reza Pulungan Probabilitas dan Proses Stokastika 8 Mean-Time-to-Failure C adalah v.r. dengan range N, maka berdasarkan corollary sebelumnya: ∞ X E (C) = Pr(C > i ). i =0 Pr(C > i ) mudah ditentukan: crash terjadi setelah jam yang ke i (C > i ) jika dan hanya jika sistem tersebut tidak crash i jam pertama. Ini terjadi dengan probabilitas (1 − p)i. Dengan demikian: ∞ X 1 1 E (C) = (1 − p)i = =. 1 − (1 − p) p i =0 Prinsip umum: Jika sebuah sistem fail setiap time-step dengan probabilitas p, maka jumlah step yang diharapkan hingga (dan termasuk) failure yang pertama adalah p1. Reza Pulungan Probabilitas dan Proses Stokastika 9 Ekspektasi Bersyarat Seperti halnya probabilitas dari event, ekspektasi juga dapat bersyarat pada event-event tertentu. Deﬁnition Conditional expectation (ekspektasi bersyarat) E (R | A) dari variabel random R jika event A dideﬁnisikan oleh: X E (R | A) = x · Pr(R = x | A). x ∈range(R) Reza Pulungan Probabilitas dan Proses Stokastika 10 Ekspektasi Bersyarat Misalnya kita dapat menghitung ekspektasi dari pelemparan sebuah dadu yang tidak bias, dengan syarat pelemparan menghasilkan nilai paling sedikit 4. Andaikan R adalah v.r. untuk hasil pelemparan sebuah dadu, maka: 6 X E (R | R ≥ 4) = i · Pr(R = i | R ≥ 4), i =1 1 1 1 = 1·0+2·0+3·0+4· +5· +6· , 3 3 3 = 5. Reza Pulungan Probabilitas dan Proses Stokastika 11 Hukum Ekspektasi Total Salah satu kegunaan lain dari ekspektasi bersyarat adalah kita bisa memecah-mecah perhitungan ekspektasi yang rumit menjadi kasus-kasus yang lebih sederhana. Ini diungkapkan oleh teorema berikut. Theorem (The Law of Total Expectation) Andaikan R adalah v.r. pada sample space S dan andaikan A1 , A2 , · · · adalah suatu partisi dari S. Maka: X E (R) = E (R | Ai ) · Pr(Ai ). i Reza Pulungan Probabilitas dan Proses Stokastika 12 Hukum Ekspektasi Total Contoh: andaikan 49.8% dari semua manusia adalah laki-laki dan sisanya perempuan. Juga asumsikan bahwa ekspektasi dari tinggi laki-laki adalah 180 cm, sementara ekspektasi dari tinggi perempuan adalah 165 cm. Berapakah ekspektasi dari tinggi seorang manusia? Kita dapat menghitung ini dengan merata-ratakan tinggi laki-laki dan perempuan. Andaikan H adalah tinggi dari seseorang yang dipilih secara random, M adalah event bahwa seseorang tersebut laki-laki, dan F adalah event bahwa seseorang tersebut perempuan. Maka: E (H ) = E (H | M ) · Pr(M ) + E (H | F ) · Pr(F ), = 180 · 0.498 + 160 · 0.502, = 172.47. Reza Pulungan Probabilitas dan Proses Stokastika 13 Ekspektasi dari Fungsi Ekspektasi dapat juga dideﬁnisikan untuk fungsi-fungsi dari variabel random. Deﬁnition Andaikan R : S −→ V adalah sebuah variabel random dan f : V −→ R adalah sebuah fungsi total pada range dari R. Maka: X E (f (R)) = f (R(ω)) · Pr(ω). ω∈S Secara ekuivalen: X E (f (R)) = f (x ) · Pr(R = x ). x ∈range(R) Reza Pulungan Probabilitas dan Proses Stokastika 14 Ekspektasi dari Fungsi Misalkan R adalah variabel random untuk nilai yang diperoleh dari pelemparan sebuah dadu yang tidak bias. Maka: 1 1 1 1 1 1 1 1 1 1 1 1 1 49 E = · + · + · + · + · + · =. R 1 6 2 6 3 6 4 6 5 6 6 6 120 Reza Pulungan Probabilitas dan Proses Stokastika 15 Ekspektasi dan Gambling Banyak hal menarik tentang ekspektasi yang dapat dijelaskan dengan gambling. Kita lihat yang paling sederhana. Andaikan anda menang $A dengan probabilitas p dan kalah $B dengan probabilitas (1 − p), maka expected return (hasil yang diharapkan) adalah: p · A − (1 − p) · B. Umpamanya anda melemparkan koin yang fair dan menang $1 untuk head dan kalah $1 untuk tail, maka expected return anda adalah: 1 1 · 1 − (1 − ) · 1 = 0. 2 2 Pada kasus ini permainan tersebut disebut fair karena expected return sama dengan nol. Reza Pulungan Probabilitas dan Proses Stokastika 16 Splitting the Pot Namun gambling bisa jadi sangat rumit. Andaikan dua orang teman anda, Erick dan Nick, mengajak anda taruhan. Masing-masing meletakkan $2 dan menuliskan “head” atau “tail” secara rahasia. Salah seorang pemain melemparkan koin. $6 akan dibagi rata oleh pemain yang menebak dengan benar. Anda tidak begitu mempercayai Erick dan Nick, jadi anda bertanya-tanya apakah setup dari permainan ini fair. Kita dapat memodelkan permainan ini dan menghitung expected return dengan menggunakan metode empat langkah. Reza Pulungan Probabilitas dan Proses Stokastika 17 Splitting the Pot Diagram pohon dari permasalahan taruhan dengan Erick dan Nick. you guess Eric guesses Nick guesses your probability right? right? right? payoff yes !"# $0 !"$ yes !"# no !"# $1 !"$ yes !"# $1 !"$ yes !"# no !"# no !"# $4 !"$ yes !"# !$2 !"$ yes !"# no !"# no !"# !$2 !"$ yes !"# !$2 !"$ no !"# no !"# $0 !"$ Reza Pulungan Probabilitas dan Proses Stokastika 18 Splitting the Pot Berdasarkan model tersebut, anda dapat menghitung expected return: 1 1 1 1 E (payoff ) = 0 · +1· +1· +4· + 8 8 8 8 1 1 1 1 + (−2) · + (−2) · + (−2) · + 0 · , 8 8 8 8 = 0. Sejauh ini kelihatannya game tersebut fair. Reza Pulungan Probabilitas dan Proses Stokastika 19 Splitting the Pot Diagram pohon dari permasalahan taruhan dengan Erick dan Nick. you guess Eric guesses Nick guesses your probability right? right? right? payoff yes !"# $0 !"$ yes !"# no !"# $1 !"$ yes !"# $1 !"$ yes !"# no !"# no !"# $4 !"$ yes !"# !$2 !"$ yes !"# no !"# no !"# !$2 !"$ yes !"# !$2 !"$ no !"# no !"# $0 !"$ Reza Pulungan Probabilitas dan Proses Stokastika 20 Splitting the Pot—Collusion Karena game tersebut fair, anda memutuskan untuk ikut bertaruh. Yang mengejutkan adalah anda kalah. Setelah 1000 kali taruhan anda malah kalah $500. Erick dan Nick bilang anda hanya kurang beruntung saja; namun anda tidak percaya. Dengan menggunakan tail dari distribusi binomial, probabilitas bahwa anda kalah $500 dalam 1000 taruhan, anda temukan, sangat-sangat kecil sekali. Apa mungkin anda benar-benar sedang sial; atau Nick dan Erick berkolusi melawan anda? Reza Pulungan Probabilitas dan Proses Stokastika 21 Splitting the Pot—Collusion Tentu saja, Erick dan Nick hanya dapat menebak hasil dari pelemparan koin dengan probabilitas 1/2; namun bagaimana kalau mereka selalu menebak berbeda? you guess Eric guesses Nick guesses your probability right? right? right? payoff yes $ $0 $ yes !"# no ! $1 !"% yes ! $1 !"% yes !"# no !"# no $ $4 $ yes $ !$2 $ yes !"# no !"# no ! !$2 !"% yes ! !$2 !"% no !"# no $ $10 $ Reza Pulungan Probabilitas dan Proses Stokastika 22 Splitting the Pot Berdasarkan model yang baru ini, anda dapat menghitung expected return: 1 1 E (payoff ) = 0 · 0 + 1 · + 1 · + 4 · 0+ 4 4 1 1 + (−2) · 0 + (−2) · + (−2) · + 0 · 0, 4 4 1 =−. 2 Ini benar-benar buruk. Dengan berkolusi, Erick dan Nick membuat anda “diharapkan” kehilangan $0.5 setiap taruhan. Itulah alasan mengapa anda kalah $500 dalam 1000 taruhan. Reza Pulungan Probabilitas dan Proses Stokastika 23 Ekspektasi dari Jumlahan Ekspektasi mematuhi sebuah aturan yang sederhana dan bermanfaat: linieritas. Theorem Untuk sembarang variabel-variabel random R1 dan R2 : E (R1 + R2 ) = E (R1 ) + E (R2 ). Teorema di atas dapat diperluas dengan mudah: Theorem Untuk sembarang variabel-variabel random R1 dan R2 , dan konstanta-konstanta a1 , a2 ∈ R: E (a1 · R1 + a2 · R2 ) = a1 · E (R1 ) + a2 · E (R2 ). Reza Pulungan Probabilitas dan Proses Stokastika 24 Ekspektasi dari Jumlahan Untuk kasus lebih dari dua buah variabel, kita peroleh: Corollary (Linearity of Expectation) Untuk sembarang variabel-variabel random R1 , · · · , Rk dan konstanta-konstanta a1 , · · · , ak ∈ R: k ! k X X E ai · Ri = ai · E (Ri ). i =1 i =1 Yang membuat linieritas ekspektasi sangat penting, adalah karena tidak diperlukan asumsi tentang independence. Independence sangat sulit dan merupakan asumsi yang berbahaya. Reza Pulungan Probabilitas dan Proses Stokastika 25 Jumlahan dari v.r.i Linieritas dari ekspektasi khususnya sangat berguna jika kita berurusan dengan jumlahan dari variabel random indikator. Misalkan pada suatu makan malam, n orang menitipkan topi mereka. Topi-topi tersebut dicampur-baurkan dan pada waktu mereka pulang, mereka menerima topi secara random. Oleh karena itu, masing-masing orang menerima topinya sendiri dengan probabilitas 1/n. Berapakah ekspektasi dari jumlah orang yang memperoleh topi mereka sendiri? Andaikan G adalah v.r. untuk jumlah orang yang memperoleh topi mereka sendiri. Oleh karena itu kita ingin menentukan E (G). Reza Pulungan Probabilitas dan Proses Stokastika 26 Jumlahan dari v.r.i Apa yang dapat kita lakukan? Satu-satunya yang kita ketahui adalah bahwa probabilitas masing-masing memperoleh topinya sendiri adalah 1/n. Kita dapat menyelesaikan ini dengan mudah dengan menggunakan fakta linieritas ekspektasi. Triknya adalah mengungkapkan G sebagai jumlahan dari variabel-variabel random indikator. Andaikan Gi adalah v.r.i. untuk event bahwa orang ke-i memperoleh topinya sendiri, maka: G = G1 + G2 + · · · + Gn. Jelas variabel-variabel random indikator ini tidak saling independent. Namun tidak menjadi masalah kalau kita menggunakan ekspektasi. Reza Pulungan Probabilitas dan Proses Stokastika 27 Jumlahan dari v.r.i Karena Gi adalah v.r.i., dari lemma sebelumnya kita peroleh: 1 E (Gi ) = Pr(Gi = 1) =. n Dengan menggunakan linieritas ekspektasi: E (G) = E (G1 + G2 + · · · + Gn ), = E (G1 ) + E (G2 ) + · · · + E (Gn ), 1 1 1 = + + ··· + , |n n {z n} n = 1. Reza Pulungan Probabilitas dan Proses Stokastika 28 Jumlahan dari v.r.i Secara umum, kita memiliki metode yang bagus untuk menghitung ekspektasi dari jumlah event yang akan terjadi. Theorem Diberikan sembarang kumpulan dari n buah event A1 , A2 , · · · , An ⊆ S. Maka expected number (ekspektasi jumlah) event yang akan terjadi adalah: n X Pr(Ai ). i =1 Kita tidak perduli sama sekali dengan independence dari event-event tersebut. Reza Pulungan Probabilitas dan Proses Stokastika 29 Ekspektasi Distribusi Binomial Andaikan kita memiliki sebuah koin yang bias dengan probabilitas memperoleh head p. Secara independent koin tersebut dilemparkan n kali. Berapakah expected number kita memperoleh head? Andaikan J adalah v.r. untuk jumlah head yang muncul dari n pelemparan tersebut. Maka J memiliki distribusi binomial: n Pr(J = k ) = · p k · (1 − p)n−k. k Maka ekspektasi dari v.r. tersebut: n n X X n E (J ) = k · Pr(J = k ) = k· · p k · (1 − p)n−k. k k =0 k =0 Persamaan di atas sangat sulit untuk disederhanakan! Reza Pulungan Probabilitas dan Proses Stokastika 30 Ekspektasi Distribusi Binomial Kita coba cara lain. Kita coba dengan menggunakan linieritas ekspektasi untuk v.r.i. Namun bagaimana cara mengungkapkan J sebagai jumlahan dari v.r.i.? Andaikan Ji adalah v.r.i. untuk pelemparan yang ke-i , yaitu: 1, jika pelemparan ke-i head, Ji = 0, jika pelemparan ke-i tail. Oleh karena itu: J = J1 + J2 + · · · + Jn. Dan: n X E (J ) = Pr(Ji ) = n · p. i =1 Reza Pulungan Probabilitas dan Proses Stokastika 31 Ekspektasi Distribusi Binomial Semudah itu! Jika kita melemparkan n buah koin yang mutually independent, kita memang mengharapkan memperoleh n · p head. Namun bagaimana jika koin yang digunakan tidak mutually independent? Tidak jadi masalah. Dari linieritas ekspektasi, ekspektasi tidak mengasumsikan independence sama sekali. Btw, dengan menggunakan fakta linieritas ekspektasi, kita baru saja memperlihatkan bahwa: n X n k· · p k · (1 − p)n−k = n · p. k k =0 Reza Pulungan Probabilitas dan Proses Stokastika 32 The Coupon Collector Problem Andaikan setiap kotak cereal berisi sebuah kupon dengan warna tertentu. Terdapat 5 kemungkinan warna. Kupon-kupon dimasukkan ke dalam kotak-kotak cereal secara uniform dan independent. Jika seorang konsumer berhasil mengumpulkan 5 kupon dengan warna-warna yang lengkap, maka dia berhak mendapatkan hadiah. Berapakah ekspektasi dari jumlah kotak cereal yang mesti dibeli seorang konsumer untuk memperoleh ke-5 kupon dengan warna berbeda tersebut? Masalah ini disebut dengan coupon collector problem. Masalah seperti ini sering muncul: misalnya ada 42 partai politik di Indonesia; berapakah ekspektasi jumlah orang yang mesti anda kumpulkan agar paling tidak ada satu orang anggota untuk semua kemungkinan partai politik? Reza Pulungan Probabilitas dan Proses Stokastika 33 The Coupon Collector Problem Andaikan seorang kolektor sudah memperoleh kupon-kupon dalam bentuk barisan berikut: biru hijau hijau merah biru kuning biru kuning putih. Kita partisi barisan tersebut menjadi 5 blok: biru |{z} hijau hijau merah biru kuning biru kuning putih. | {z } | {z } | {z } | {z } X0 X1 X2 X3 X4 Aturannya adalah sebuah blok berakhir, jika kita memperoleh kupon dengan warna baru (yang sebelumnya tidak ada). Reza Pulungan Probabilitas dan Proses Stokastika 34 The Coupon Collector Problem Secara umum, andaikan ada n buah warna dan Xk adalah panjang dari blok yang ke-k , maka jumlah kotak cereal yang harus dikumpulkan agar kupon-kupon dengan ke-n warna berhasil dikumpulkan adalah: T = X0 + X1 + X2 + · · · + Xn−1. Sekarang kita fokuskan bagaimana menentukan Xk. Di awal blok k , kita sudah memiliki k macam warna dan di akhir dari blok, kita akan memiliki satu warna tambahan. Jika kita memiliki k warna, probabilitas bahwa sebuah kotak cereal berisi salah satu warna tersebut adalah k /n. Oleh karena itu, probabilitas bahwa sebuah kotak cereal berisi sebuah warna tambahan adalah 1 − kn = n−kn. Reza Pulungan Probabilitas dan Proses Stokastika 35 The Coupon Collector Problem Oleh karena itu, probabilitas bahwa sebuah kotak cereal berisi sebuah warna tambahan adalah 1 − kn = n−kn. Lihat kembali pembahasan kita tentang MTTF, maka: 1 n E (Xk ) = =. p n−k Dengan demikian, ekspektasi jumlah kotak cereal yang harus dibuka sampai sebuah warna baru diperoleh pada n blok yang ke-k adalah n−k. Reza Pulungan Probabilitas dan Proses Stokastika 36 The Coupon Collector Problem Berdasarkan linieritas ekspektasi: E (T ) = E (X0 + X1 + · · · + Xn−1 ), = E (X0 ) + E (X1 ) + · · · + E (Xn−1 ), n n n n = + + ··· + + , n−0 n−1 2 1 1 1 1 1 =n + ··· + + , n n−1 2 1 1 1 1 1 =n + ··· + + , 1 2 n−1 n = nHn , ∼ n ln(n). Kita menemukan Harmonic Numbers lagi! Reza Pulungan Probabilitas dan Proses Stokastika 37 The Coupon Collector Problem Untuk kasus 5 kupon kita tadi, ekspektasi jumlah cereal yang harus dibeli untuk memperoleh ke-5 warna adalah kira-kira 5 · ln(n) = 8.05. Untuk partai politik 42 · ln(42) = 156.98. Reza Pulungan Probabilitas dan Proses Stokastika 38 Inﬁnite Sums Linieritas ekspektasi juga berlaku untuk tak hingga banyaknya variabel random. Theorem Andaikan R0 , R1 , · · · adalah variabel-variabel random sedemikian sehingga: ∞ X E (|Ri |) i =0 konvergen (< ∞). Maka: ∞ ! ∞ X X E Ri = E (Ri ). i =0 i =0 Reza Pulungan Probabilitas dan Proses Stokastika 39 Ekspektasi Perkalian Jika ekspektasi dari jumlahan sama dengan jumlahan dari ekspektasi, hal yang sama tidak selalu berlaku untuk perkalian. Namun demikian, ada kasus khusus di mana itu berlaku, yaitu ketika variabel-variabel random yang terlibat independent. Theorem Untuk sembarang dua buah variabel random yang independent R1 dan R2 : E (R1 · R2 ) = E (R1 ) · E (R2 ). Reza Pulungan Probabilitas dan Proses Stokastika 40 Ekspektasi Perkalian Hasil sebelumnya dapat diperluas. Corollary Jika variabel-variabel random R1 , R2 , · · · , Rk mutually independent, maka: k ! k Y Y E Ri = E (Ri ). i =1 i =1 Reza Pulungan Probabilitas dan Proses Stokastika 41 Ekspektasi Pembagian Jika S dan T adalah variabel-variabel random, maka berdasarkan linieritas dari ekspektasi, kita tahu: E (S + T ) = E (S) + E (T ). Demikian juga, jika S dan T independent, kita telah melihat bahwa: E (S · T ) = E (S) · E (T ). Bagaimana dengan pembagian? Apakah berlaku: S E (S) E = ? T E (T ) Reza Pulungan Probabilitas dan Proses Stokastika 42 Ekspektasi Pembagian Jawabannya adalah tidak (pada umumnya). Dengan demikian: S E (S) E 6= ? T E (T ) Yang paling penting untuk diingat adalah bahwa: 1 1 E 6=. T E (T ) Yang mengejutkan adalah meskipun fakta di atas sudah diketahui, banyak orang yang masih memakai fakta yang salah dalam kehidupan sehari-hari. Reza Pulungan Probabilitas dan Proses Stokastika 43 Ekspektasi Pembagian: Kesalahan Benchmark RISC CISC CISC/RISC E-string search 150 120 0.8 F-bit test 120 180 1.5 Ackerman 150 300 2.0 Rec 2-sort 2800 1400 0.5 Average 1.2 Benchmark RISC CISC RISC/CISC E-string search 150 120 1.25 F-bit test 120 180 0.67 Ackerman 150 300 0.5 Rec 2-sort 2800 1400 2.0 Average 1.1 Reza Pulungan Probabilitas dan Proses Stokastika 44 Ekspektasi Pembagian: Kesalahan Ada masalah pada kedua interpretasi, karena mereka menggunakan ekspektasi pembagian, yang kita sudah tahu tidak benar. Karena ekspektasi pembagian salah, sebuah data dapat diinterpretasikan berbeda, dan dua kesimpulan bisa diperoleh. Kita lihat persoalan ini dari sudut pandang yang benar: interpretasi probabilistik. Reza Pulungan Probabilitas dan Proses Stokastika 45 Ekspektasi Pembagian: Kesalahan Andaikan sample space adalah himpunan dari program-program benchmark yang ada. Andaikan R adalah variabel random untuk panjang dari program RISC dan C adalah v.r. untuk panjang program CISC. Kita ingin membandingkan ekspektasi E (R) dan E (C), yaitu rata-rata panjang mereka. Untuk menghitung kedua ekspektasi kita mesti mengassign probabilitas untuk masing-masing sample (program benchmark). Namun, karena kita tidak memiliki informasi kita asumsikan bahwa probabilitasnya adalah uniform. Reza Pulungan Probabilitas dan Proses Stokastika 46 Ekspektasi Pembagian: Kesalahan Sekarang kita hitung. X E (R) = i · Pr(R = i ), i ∈range(R) 1 1 1 1 = 150 · + 120 · + 150 · + 2800 · , 4 4 4 4 = 805. X E (C) = i · Pr(C = i ), i ∈range(C) 1 1 1 1 = 120 · + 180 · + 300 · + 1400 · , 4 4 4 4 = 500. Nah, sekarang E (R)/E (C) = 1.61. Kesimpulan: Program RISC rata-rata 61% lebih panjang dibandingkan program CISC! Reza Pulungan Probabilitas dan Proses Stokastika 47

Probabilitas dan Proses Stokastika PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue