Dulu ketika zamannya saya ikut SRM top coder, kalau dapat soal dengan kalimat perintah "Find the expected value of ...", saya langsung merasa seram. Alasannya karena saya tidak tahu apa itu expected number. Belum lagi tiba-tiba contoh keluaran yang ada adalah angka pecahan yang misterius, contohnya:
Tulisan ini akan menjelaskan apa itu expected value, supaya kalian para pembaca tidak merasa seram seperti saya dulunya.
Sebuah dadu memiliki 6 sisi, dengan angka dari 1 sampai dengan 6. Peluang setiap sisi untuk menjadi nilai hasil pelemparan sama, yaitu 1/6. Tentukan nilai harapan hasil pelemparan dadu ini!
Untuk soal ini, Anda mungkin pernah mengerjakannya saat SMP.
Sebelum menjelaskan apa sebenarnya nilai harapan, ada baiknya kita melihat bentuk rumusnya terlebih dahulu.
\(\displaystyle
E = \sum_{x \in S} p(x)v(x)
\)
Dengan:
\(S = \lbrace1, 2, 3, 4, 5, 6\rbrace\)
Peluang untuk setiap kejadian tersebut adalah sama, yaitu 1/6. Sehingga:
\(p(1) = p(2) = p(3) = p(4) = p(5) = p(6) = \frac{1}{6}\)
Yang mungkin asing bagi Anda adalah nilai dari kejadian. Secara sederhana, Anda dapat menganggapnya sebagai nilai yang diberikan atas suatu kejadian (lho!). Pada kasus ini, nilai dari suatu kejadian adalah muka dadu yang menjadi hasil pelemparan. Sehingga v(1) = 1, v(2) = 2, v(3) = 3, dan seterusnya. Dituliskan lebih formal:
\(v(x) = x\)
Jika dimasukkan ke dalam rumus, didapatkan:
\(
\begin{eqnarray*}
E &=& p(1)v(1) + p(2)v(2) + p(3)v(3) + p(4)v(4) + p(5)v(5) + p(6)v(6)\\
&=& \frac{1}{6}1 + \frac{1}{6}2 + \frac{1}{6}3 + \frac{1}{6}4 + \frac{1}{6}5 + \frac{1}{6}6\\
&=& 3.5
\end{eqnarray*}
\)
Jadi nilai harapannya adalah 3.5
Lalu apa maksud angka ini?
Artinya, bila aktivitas melempar dadu sebanyak 1 kali ini diulang berkali-kali dan hasilnya dirata-rata, maka nilai yang didapatkan akan mendekati 3.5. Bila Anda perhatikan, perhitungan ini mirip sekali dengan rata-rata. Namun perbedaannya akan terlihat pada contoh berikutnya.
Diketahui peluang kemunculan muka dadu untuk kali ini adalah:
\(p(1) = 0.2\)
\(p(2) = 0.3\)
\(p(3) = 0.1\)
\(p(4) = 0.1\)
\(p(5) = 0.2\)
\(p(6) = 0.1\)
Penyelesaiannya serupa dengan sebelumnya, cukup masukkan ke rumus yang ada:
\(
\begin{eqnarray*}
E &=& p(1)v(1) + p(2)v(2) + p(3)v(3) + p(4)v(4) + p(5)v(5) + p(6)v(6)\\
&=& 0.2\times1 + 0.3\times2 + 0.1\times3 + 0.1\times4 + 0.2\times5 + 0.1\times6\\
&=& 3.1
\end{eqnarray*}
\)
Nilainya 3.1, ternyata lebih kecil dari ketika dadunya tidak cacat. Masuk akal, karena kali ini peluang dadu menunjukkan angka yang kecil lebih besar daripada angka besar.
Perhatikan pula perbedaannya dengan perhitungan rata-rata. Kita tidak semata-mata melakukan rata-rata, tetapi kita memperhatikan peluang setiap kejadiannya. Rata-rata sejenis ini juga disebut dengan rata-rata berbobot (weighted average). Pada kenyataannya, konsep rata-rata yang diajarkan semasa sekolah SD adalah kasus khusus dari rata-rata yang sebenarnya, yaitu ketika semua kejadian memiliki bobot yang sama.
Sejauh ini konsepnya cukup mudah. Kita cukup mencacah semua kemungkinan kejadian yang ada, menentukan peluangnya, menentukan nilainya, lalu masukkan ke rumus. Apa yang bisa menjadi masalah? Ketika banyaknya kejadian yang ada sangat besar!
Pak Dengklek memiliki N biskuit di meja kerjanya. Setiap jam, Pak Dengklek akan memakan 1 atau 2 biskuit. Peluang memakan 1 atau 2 biskuit seimbang, yaitu 50%. Tentu saja ketika hanya bersisa 1 biskuit, peluang memakan 1 biskuit adalah 100%. Jika biskuit telah habis, Pak Dengklek berhenti memakan biskuit. Setelah berlalu K jam, berapa nilai harapan dari banyaknya biskuit yang ia makan?
Secara sederhana, kita dapat merepresentasikan kejadian sebagai rangkaian aktivitas memakan biskuit. Misalnya N=5 dan K=4, maka contoh kejadiannya:
Peluang setiap kejadian bergantung pada kondisi biskuit saat itu, apakah masih bersisa 1, 2, atau lebih.
Nilai dari suatu kejadian adalah jumlah angka pada rangkaian yang ada.
Masalah utama dari soal ini adalah besarnya ukuran himpunan semesta. Jika disadari, ukuran ruang semestanya memiliki pertumbuhan seperti bilangan fibonacci ke-K. Artinya nilainya eksponensial, dan akan sangat besar bahkan untuk N dan K bernilai puluhan.
Strategi yang dapat digunakan adalah dengan tidak terpaku pada perumusan yang ada. Kita dapat memandang masalah perhitungan nilai harapan dari sisi yang lain, yaitu secara rekursif.
Pada kondisi awal, terdapat N biskuit. Terdapat:
\(f(N, 1) = 0.5(1 + f(N-1,2)) + 0.5(2 + f(N-2,2))\)
Bagian ini memang cukup mengejutkan. Namun jika Anda bayangkan bahwa nilai harapan untuk jam ke-2 telah ditemukan (baik untuk bersisa N-1 atau N-2 biskuit), maka rumus tersebut menjadi masuk akal.
Jadi dengan hanya fokus ke transisi dari jam ke-1 ke jam ke-2, kita mengubah permasalahan yang ada menjadi rekursif. Sebagai bonus, rumus rekursif ini memungkinkan kita menyelesaikan perhitungannya dengan DP (dynamic programming). Rumus lebih lengkapnya:
\(\displaystyle
f(x,t) = \left\{
\begin{array}{ll}
0 &, (t > K) \lor (x = 0) \\
1 + f(x-1, t+1) &, (t \le K) \land (x = 1) \\
0.5(1 + f(x-1, t+1)) + 0.5(2 + f(x-2,t+1)) &, (t \le K) \land (x > 1)
\end{array} \right. \)
Penjelasan kasus basis: untuk kasus jam (t) telah melebihi K, atau biskuit telah habis, nilai harapan biskuit yang dimakan adalah 0.
Jawabannya ada di f(N, 1).
Rumusan DP lain yang juga benar, adalah dengan perhitungan nilai kejadiannya di basis:
\(\displaystyle
f(x,t) = \left\{
\begin{array}{ll}
N-x &, t > K \\
f(x, t+1) &, (t \le K) \land (x = 0) \\
f(x-1, t+1) &, (t \le K) \land (x = 1) \\
0.5f(x-1, t+1) + 0.5f(x-2,t+1) &, (t \le K) \land (x > 1)
\end{array} \right. \)
Bila Anda bayangkan percabangan dari pohon rekursifnya, dapat disadari bahwa pada akhirnya perkalian-perkalian peluang yang ada sampai ke basis adalah peluang suatu rangkaian kejadian terjadi. Nilai tersebut kemudian dikalikan dengan nilai kejadiannya, yaitu banyaknya biskuit yang telah dimakan, berupa N-x. Semuanya pada akhirnya dijumlahkan dan didapatkan jawaban pada f(N, 1).
Penggunaan DP untuk menyelesaikan soal ini memberikan kompleksitas O(NK), yang bekerja dengan cepat bahkan untuk N dan K bernilai ribuan.
1.12938104018102Kemudian suatu ketika saya mendapatkan pencerahan, bahwa ternyata expected value adalah nilai harapan. Seketika saya langsung bisa mengerjakan soal-soal dasar tentang expected value.
Tulisan ini akan menjelaskan apa itu expected value, supaya kalian para pembaca tidak merasa seram seperti saya dulunya.
Permasalahan Motivasi 1: angka dadu
Mulai dari contoh sederhana, yaitu angka dadu:Sebuah dadu memiliki 6 sisi, dengan angka dari 1 sampai dengan 6. Peluang setiap sisi untuk menjadi nilai hasil pelemparan sama, yaitu 1/6. Tentukan nilai harapan hasil pelemparan dadu ini!
Untuk soal ini, Anda mungkin pernah mengerjakannya saat SMP.
Sebelum menjelaskan apa sebenarnya nilai harapan, ada baiknya kita melihat bentuk rumusnya terlebih dahulu.
\(\displaystyle
E = \sum_{x \in S} p(x)v(x)
\)
Dengan:
- E: expected value
- S: himpunan semesta dari semua kejadian yang mungkin
- x: suatu kejadian
- p(x): peluang kejadian x terjadi
- v(x): nilai dari kejadian x
\(S = \lbrace1, 2, 3, 4, 5, 6\rbrace\)
Peluang untuk setiap kejadian tersebut adalah sama, yaitu 1/6. Sehingga:
\(p(1) = p(2) = p(3) = p(4) = p(5) = p(6) = \frac{1}{6}\)
Yang mungkin asing bagi Anda adalah nilai dari kejadian. Secara sederhana, Anda dapat menganggapnya sebagai nilai yang diberikan atas suatu kejadian (lho!). Pada kasus ini, nilai dari suatu kejadian adalah muka dadu yang menjadi hasil pelemparan. Sehingga v(1) = 1, v(2) = 2, v(3) = 3, dan seterusnya. Dituliskan lebih formal:
\(v(x) = x\)
Jika dimasukkan ke dalam rumus, didapatkan:
\(
\begin{eqnarray*}
E &=& p(1)v(1) + p(2)v(2) + p(3)v(3) + p(4)v(4) + p(5)v(5) + p(6)v(6)\\
&=& \frac{1}{6}1 + \frac{1}{6}2 + \frac{1}{6}3 + \frac{1}{6}4 + \frac{1}{6}5 + \frac{1}{6}6\\
&=& 3.5
\end{eqnarray*}
\)
Jadi nilai harapannya adalah 3.5
Lalu apa maksud angka ini?
Artinya, bila aktivitas melempar dadu sebanyak 1 kali ini diulang berkali-kali dan hasilnya dirata-rata, maka nilai yang didapatkan akan mendekati 3.5. Bila Anda perhatikan, perhitungan ini mirip sekali dengan rata-rata. Namun perbedaannya akan terlihat pada contoh berikutnya.
Permasalahan Motivasi 2: angka dadu peang
Ternyata ada kecacatan pada dadu yang dimiliki, sehingga peluang suatu muka dadu muncul tidak lagi sama dengan muka dadu lainnya.Diketahui peluang kemunculan muka dadu untuk kali ini adalah:
\(p(1) = 0.2\)
\(p(2) = 0.3\)
\(p(3) = 0.1\)
\(p(4) = 0.1\)
\(p(5) = 0.2\)
\(p(6) = 0.1\)
Penyelesaiannya serupa dengan sebelumnya, cukup masukkan ke rumus yang ada:
\(
\begin{eqnarray*}
E &=& p(1)v(1) + p(2)v(2) + p(3)v(3) + p(4)v(4) + p(5)v(5) + p(6)v(6)\\
&=& 0.2\times1 + 0.3\times2 + 0.1\times3 + 0.1\times4 + 0.2\times5 + 0.1\times6\\
&=& 3.1
\end{eqnarray*}
\)
Nilainya 3.1, ternyata lebih kecil dari ketika dadunya tidak cacat. Masuk akal, karena kali ini peluang dadu menunjukkan angka yang kecil lebih besar daripada angka besar.
Perhatikan pula perbedaannya dengan perhitungan rata-rata. Kita tidak semata-mata melakukan rata-rata, tetapi kita memperhatikan peluang setiap kejadiannya. Rata-rata sejenis ini juga disebut dengan rata-rata berbobot (weighted average). Pada kenyataannya, konsep rata-rata yang diajarkan semasa sekolah SD adalah kasus khusus dari rata-rata yang sebenarnya, yaitu ketika semua kejadian memiliki bobot yang sama.
Sejauh ini konsepnya cukup mudah. Kita cukup mencacah semua kemungkinan kejadian yang ada, menentukan peluangnya, menentukan nilainya, lalu masukkan ke rumus. Apa yang bisa menjadi masalah? Ketika banyaknya kejadian yang ada sangat besar!
Permasalahan Motivasi 3: cemilan kerja
Masalah kali ini tidak ada kaitannya dengan dadu:Pak Dengklek memiliki N biskuit di meja kerjanya. Setiap jam, Pak Dengklek akan memakan 1 atau 2 biskuit. Peluang memakan 1 atau 2 biskuit seimbang, yaitu 50%. Tentu saja ketika hanya bersisa 1 biskuit, peluang memakan 1 biskuit adalah 100%. Jika biskuit telah habis, Pak Dengklek berhenti memakan biskuit. Setelah berlalu K jam, berapa nilai harapan dari banyaknya biskuit yang ia makan?
Secara sederhana, kita dapat merepresentasikan kejadian sebagai rangkaian aktivitas memakan biskuit. Misalnya N=5 dan K=4, maka contoh kejadiannya:
1111 => 1 setiap jamnya 1121 => 1 pada dua jam pertama, lalu 2 pada jam ke-3, dan 1 pada jam ke-4 1211 ... 221 => 2 pada dua jam pertama, lalu 1 pada jam terakhir
Peluang setiap kejadian bergantung pada kondisi biskuit saat itu, apakah masih bersisa 1, 2, atau lebih.
Nilai dari suatu kejadian adalah jumlah angka pada rangkaian yang ada.
Masalah utama dari soal ini adalah besarnya ukuran himpunan semesta. Jika disadari, ukuran ruang semestanya memiliki pertumbuhan seperti bilangan fibonacci ke-K. Artinya nilainya eksponensial, dan akan sangat besar bahkan untuk N dan K bernilai puluhan.
Strategi yang dapat digunakan adalah dengan tidak terpaku pada perumusan yang ada. Kita dapat memandang masalah perhitungan nilai harapan dari sisi yang lain, yaitu secara rekursif.
Pada kondisi awal, terdapat N biskuit. Terdapat:
- 0.5 peluang untuk memakan 1 biskuit, menyisakan N-1 biskuit pada jam ke-2
- 0.5 peluang untuk memakan 2 biskuit, menyisakan N-2 biskuit pada jam ke-2
\(f(N, 1) = 0.5(1 + f(N-1,2)) + 0.5(2 + f(N-2,2))\)
Bagian ini memang cukup mengejutkan. Namun jika Anda bayangkan bahwa nilai harapan untuk jam ke-2 telah ditemukan (baik untuk bersisa N-1 atau N-2 biskuit), maka rumus tersebut menjadi masuk akal.
Jadi dengan hanya fokus ke transisi dari jam ke-1 ke jam ke-2, kita mengubah permasalahan yang ada menjadi rekursif. Sebagai bonus, rumus rekursif ini memungkinkan kita menyelesaikan perhitungannya dengan DP (dynamic programming). Rumus lebih lengkapnya:
\(\displaystyle
f(x,t) = \left\{
\begin{array}{ll}
0 &, (t > K) \lor (x = 0) \\
1 + f(x-1, t+1) &, (t \le K) \land (x = 1) \\
0.5(1 + f(x-1, t+1)) + 0.5(2 + f(x-2,t+1)) &, (t \le K) \land (x > 1)
\end{array} \right. \)
Penjelasan kasus basis: untuk kasus jam (t) telah melebihi K, atau biskuit telah habis, nilai harapan biskuit yang dimakan adalah 0.
Jawabannya ada di f(N, 1).
Rumusan DP lain yang juga benar, adalah dengan perhitungan nilai kejadiannya di basis:
\(\displaystyle
f(x,t) = \left\{
\begin{array}{ll}
N-x &, t > K \\
f(x, t+1) &, (t \le K) \land (x = 0) \\
f(x-1, t+1) &, (t \le K) \land (x = 1) \\
0.5f(x-1, t+1) + 0.5f(x-2,t+1) &, (t \le K) \land (x > 1)
\end{array} \right. \)
Bila Anda bayangkan percabangan dari pohon rekursifnya, dapat disadari bahwa pada akhirnya perkalian-perkalian peluang yang ada sampai ke basis adalah peluang suatu rangkaian kejadian terjadi. Nilai tersebut kemudian dikalikan dengan nilai kejadiannya, yaitu banyaknya biskuit yang telah dimakan, berupa N-x. Semuanya pada akhirnya dijumlahkan dan didapatkan jawaban pada f(N, 1).
Penggunaan DP untuk menyelesaikan soal ini memberikan kompleksitas O(NK), yang bekerja dengan cepat bahkan untuk N dan K bernilai ribuan.
Tidak ada komentar :
Posting Komentar