Tagged: probability

Peluang kecelakaan Satu di antara Sejuta: Jika 999.999 selamat dan Anda orang ke-sejuta, Masihkah Anda Melanjukan?

Seorang sahabat pernah menceletukkan pikiran isengnya yang sangat legitimate untuk dipertanyakan: misalnya kecelakaan suatu maskapai penerbangan adalah 1 dibanding 1.000.000. Seandainya kita tahu bahwa 999.999 penerbangan sebelumnya selamat, dan kita akan memasuki penerbangan yang ke 1.000.000. Beranikah kita masuk ke dalam pesawat itu? Pastikah terjadi kecelakaan di penerbangan tersebut?

Ini adalah pertanyaan yang sangat menarik! Jika ternyata penerbangan itu tidak mengalami kecelakaan, bukankah ini berarti bahwa peluang kecelakaannya tidak lagi satu dibanding sejuta (karena dari 1 juta penerbangan, tidak ada satupun yang kecelakaan)? Lalu jika memang “selalu” ada 1 dari sejuta penerbangan yang mengalami kecelakaan, apa itu berarti penerbangan ke-sejuta kita pasti kecelakaan?

Untuk meluruskan kebingungan ini, kita perlu mendefinisikan ulang apa makna peluang suatu kejadian dan distribusinya. Pertama-tama, perlu kita pahami bahwa biasanya, statistik yang diberikan media tentang suatu kejadian (katakanlah kecelakaan pesawat) adalah estimasi berdasarkan data historis. Artinya, nilai proporsi ini bukan nilai yang sesungguhnya, tapi dengan selang kepercayaan tertentu, kita dapat yakin estimasi ini cukup “dekat” dengan proporsi dalam dunia nyata. Lebih jauh lagi, nilai estimasi ini sangat bergantung pada data historis yang dimiliki sebelumnya. Hal ini akan semakin jelas setelah kita diskusikan bagian berikut.

Untuk memahami fenomena ini, kita akan memakai model yang jauh lebih umum dan lebih mudah untuk dianalisis. Misalkan ada n (pilih n cukup besar nanti, minimal sejuta lah) buah apel dalam keranjang dan hanya ada 1 buah yang busuk di antaranya. Maka, dengan cepat kita dapat simpulkan bahwa ketika kita ambil sebuah apel secara acak, peluang kita peroleh apel busuk adalah satu dibanding n. Perhatikan bahwa nilai peluang dalam kasus ini adalah nilai eksak dan bukan estimasi. Peluang mendapatkan apel busuk adalah betul-betul 1/n. Lalu jika kita lakukan pengambilan buah secara acak (dan setelah diambil, buah dikembalikan lagi) sebanyak n-1 kali dan selalu diperoleh apel yang baik, berapa peluang apel ke sejuta busuk? Perhatikan bahwa jika semua pengambilan selalu disertai dengan pengembalian, maka pemilihan buah dalam suatu percobaan tidak bergantung pada pemilihan buah dalam percobaan yang lain. Dalam bahasa statistik, setiap pengambilan buah saling bebas satu sama lain. Dengan demikian, jika kita diberi informasi bahwa n-1 pengambilan pertama tidak memberikan apel busuk, informasi itu tidak memberi pengaruh apapun dalam perhitungan peluang apel ke-sejuta. Dengan kata lain, peluang busuknya apel kesejuta sama dengan peluang busuknya apel pertama, yang tidak lain adalah 1/n. Anehkah? Jika kita tetapkan n=6, maka kasus ini akan sama dengan kasus melempar dadu. Peluang kita peroleh angka 1 adalah 1/6. Lalu, jika kita melempar dadu sebanyak 5 kali dan kita tidak peroleh angka 1, berapa peluang dadu keenam bermata 1? Tentu 1/6 bukan, sama seperti pelemparan yang lain? Ya, tidak ada yang aneh dari semua perhitungan ini.

Namun demikian, kita dapat kembali mempertanyakan hal ini dengan cara yang berbeda. Bukankah peluang pengambilan apel busuk satu dibanding n berarti bahwa dalam n kali pengambilan, ada satu diantaranya yang busuk? Jadi apa hal ini menjamin dalam n kali pengambilan, pasti ada 1 apel busuk? Jawabannya adalah TIDAK. Kita akan buktikan secara matematis. Dalam sekali pengambilan, peluang terambil apel sehat adalah \left(1-\dfrac{1}{n}\right). Maka, peluang tidak ditemukan apel busuk dalam n kali pengambilan adalah \left(1-\dfrac{1}{n}\right)^n, yang konvergen menuju 1/e\approx 0.3679 ketika n\rightarrow \infty. Perhatikan bahwa nilai ini berbeda dengan nilai peluang yang kita analisis di paragraf sebelumnya (di sini, tidak ada syarat/kondisi yang diberikan). Jadi, perhitungan kita mengatakan bahwa TIDAK PASTI bahwa selalu ditemukan satu apel busuk dalam n kali pengambilan; lebih tepatnya kejadian ini terjadi dengan peluang sekitar 36.79%, suatu angka yang lebih kecil dari 100%.

Sekarang, mari kembali ke cerita pesawat kita. Dalam kasus ini, nilai peluang satu dibanding sejuta bukanlah nilai peluang secara eksak, karena kita tidak bisa membuktikan secara matematis bahwa proporsi kecelakaan pesawat secara apriori memang betul-betul tepat 1 dibanding sejuta. Lalu bagaimana kita dapat mengklaim nilai peluang ini? Kemungkinan besar nilai ini diperoleh dari estimatornya, yang didapat dari pengolahan data sebelumnya. Tentu perhitungan estimator ini mengasumsikan distribusi terjadinya kecelakaan saat ini sama dengan di waktu yang lampau dan kejadian kecelakaan setiap penerbangan saling bebas satu sama lain. Tentu karena perhitungan kita adalah estimasi, maka kita akan selalu memiliki error. Menariknya, kejadian yang terjadi saat ini dapat mengubah nilai estimator menjadi lebih akurat, padahal di saat yang sama nilai estimator tersebut dalam prakteknya digunakan untuk memprediksi realisasi kejadian tersebut. Dengan kata lain, ketika seseorang dapat menyimpulkan peluang kecelakaan adalah 1 banding sejuta, maka sebetulnya sudah ada cukup banyak penerbangan yang sudah diambil data sampelnya (minimal sejuta). Dan sebaliknya, jika kita hanya mengetahui data 999.999 penerbangan saja, kita belum dapat menyimpulkan bahwa estimator peluang kecelakaan adalah 1 banding sejuta. Dengan demikian, cerita yang menjadi pokok permasalahan kita kurang realistis dan mengasumsikan proposisi yang kurang tepat.

Namun demikian, sekalipun kita dapat memperoleh nilai peluang secara eksak (seperti dalam cerita apel busuk), toh BELUM PASTI bahwa selalui ada sebuah kecelakaan dalam sejuta kali penerbangan. Jadi, kepastian yang kita peroleh bahwa penerbangan ke-sejuta tidak pasti mengalami kecelakaan, datang dari dua hal: suku error dari estimator kita dan perhitungan peluang teoretik kita. Dengan demikian, ketika Anda tahu bahwa Anda adalah penumpang ke-sejuta, jangan panik dan buang-buang tiket Anda. Anda hanya perlu melihat angka statistik ini dari perspektif lain dan menyadarinya bahwa itu hanya tipuan belaka. 🙂

Berulang Tahun di Tanggal yang Sama, Kebetulankah?

Pernahkah Anda mengenal seseorang yang berulangtahun di tanggal yang sama dengan ulang tahun Anda? Mungkin Anda mengenal satu atau dua orang. Tentu saja tidak mungkin semua orang berulang tahun di hari yang sama dengan ulang tahun Anda. Ada 365 (atau 366 jika 29 Februari terhitung) kemungkinan tanggal ulang tahun yang dapat dimiliki oleh seseorang yang baru Anda kenal. Dengan demikian, peluang orang tersebut memiliki ulang tahun yang sama dengan Anda adalah 1 dibanding 365. Suatu proporsi yang cukup kecil, yang berarti bahwa Anda dapat berharap hanya ada 1 orang yang berulangtahun di hari ulang tahun Anda untuk setiap 365 orang yang baru Anda kenal. Berangkat dari pengamatan ini, Anda mungkin berpikir bahwa dua orang yang memiliki ulang tahun yang sama adalah kejadian yang tidak terlalu sering terjadi dalam skala yang cukup kecil. Namun benarkah hal ini?

Anda dapat menanyakan pada seorang guru kelas atau pegawai rumah sakit yang menyimpan data diri sejumlah murid atau pasien. Walaupun hanya ada cukup sedikit murid dalam suatu kelas, atau pasien yang masuk dalam satu hari, kerap sekali mereka menemukan setidaknya ada 2 orang yang berulangtahun di hari yang sama. Tentu saja, jika kita mengumpulkan data diri 366 orang, kita dapat memastikan adanya suatu tanggal yang menjadi ulang tahun 2 orang atau lebih, karena hanya ada 365 kemungkinan tanggal lahir (hal ini sering juga disebut prinsip sangkar merpati dalam matematika diskrit). Namun demikian, Anda boleh membuktikan melalui pengamatan pribadi Anda, bahwa Anda tidak perlu mengumpulkan sampai ratusan orang hanya untuk menemukan dua orang berulang tahun di tanggal yang sama. Bahkan, hanya dengan mengumpulkan data diri 25 orang saja, Anda mungkin akan menemukan fenomena ini dengan peluang yang cukup tinggi.

Secara sekilas, pernyataan di atas mungkin terdengar mengherankan, karena jika kita hanya memiliki 25 data yang secara acak yang terambil dari 365 kemungkinan yang ada, data tersebut seharusnya “terpencar-pencar” ke seluruh kemungkinan tanggal yang ada dan tidak seharusnya saling “bertabrakan” karena masih ada banyak “tanggal kosong” yang belum terpakai. Namun demikian, fakta matematis dapat menunjukkan bahwa memang peluang terjadinya fenomena ini cukup tinggi, yaitu 56,87%. Lebih jauh lagi, jika kita menambah data menjadi 58 orang, kita sudah memiliki peluang sebesar 99%!

Bagaimana kita dapat memperoleh angka ini? Kita akan mengasumsikan bahwa tidak ada orang yang berulang tahun di 29 Februari, sehingga hanya ada 365 kemungkinan tanggal. Juga kita asumsikan bahwa proporsi tanggal kelahiran seluruh umat manusia berdistribusi seragam, artinya tidak ada satu tanggal yang bertendensi untuk memiliki lebih banyak orang yang lahir di tanggal tersebut, dibanding dengan tanggal yang lain.

Katakanlah kita mempunyai k\le 365 buah data. Perhitungannya cukup sederhana. Kita akan menghitung peluang kejadian komplemennya, yaitu peluang setiap orang memiliki ulang tahun yang berbeda. Kita akan menghitung peluang tidak adanya ulang tahun bersama selangkah demi selangkah. Ketika kita menginput data pertama, tentu tidak mungkin kita menemukan ulang tahun bersama, karena hanya ada 1 buah data yang kita miliki. Untuk memastikan tanggal inputan kedua berbeda dengan tanggal data pertama, hanya ada 364 kemungkinan dari 365 kemungkinan yang dimiliki oleh data kedua tersebut (karena 1 tanggal sudah dipakai oleh data pertama). Demikian seterusnya sampai data ke-k dimasukkan, hanya ada 365-k+1 kemungkinan dari 365 kemungkinan yang ada. Dengan demikian, peluang kejadian yang kita harapkan adalah perkalian dari peluang kejadian tidak adanya ulang tahun bersama yang sudah kita uraikan selangkah demi selangkah, yaitu

\dfrac{365}{365}.\dfrac{364}{365}.\dfrac{363}{365}\dots\dfrac{365-k+1}{365}

Perkalian bilangan-bilangan ini dapat dengan mudah kita hitung menggunakan aplikasi spreadsheet. Ingat bahwa nilai yang kita hitung adalah kejadian komplemennya. Dengan demikian, peluang adanya ulang tahun bersama adalah 1 dikurang nilai peluang komplemen tersebut. Berikut merupakan screenshot perhitungan dalam spreadsheet.

25      58

Mengejutkan! Tanpa perlu menampung data yang terlalu banyak, kita hampir selalu dapat menemukan orang-orang yang berulangtahun di hari yang sama!

Jika kita melihat lebih dalam, fenomena ini dapat diperumum ke dalam konteks yang lebih luas. Seandainya terdapat n buah kemungkinan tanggal (pada kenyataannya memang hanya ada 365 tanggal, tapi kita akan sedikit bermain-main untuk melihat hal menarik lainnya). Maka pertanyaan yang menarik adalah seberapa sedikit data yang perlu kita kumpulkan untuk memastikan bahwa ada data yang memiliki ulang tahun bersama dengan peluang yang cukup besar?

Pertama, kita akan sedikit memperjelas definisi matematis pertanyaan ini. Seberapa “besar” kah peluang yang “cukup besar” yang ingin kita capai? Pertanyaan ini akan kita jawab secara asimtotik, yaitu bagaimana nilai peluang ini berperilaku ketika nilai n sangat besar. Secara matematis, kita akan mencari nilai limit peluang tersebut ketika n\rightarrow \infty. Mengapa membicarakan suatu nilai yang sangat besar menjadi menarik? Karena jika nilai n berhingga, yaitu suatu konstanta saja, kita dapat melakukan komputasi dengan cukup mudah melalui bantuan komputer. Dan, ketika kita dapat memahami apa yang terjadi di suatu nilai yang sangat besar, kita dapat memahami apa yang terjadi di nilai yang lebih kecil dengan lebih mudah. Dengan demikian, kita definisikan suatu kejadian dikatakan terjadi “dengan peluang cukup besar” jika limit peluang kejadian tersebut mendekati 1 ketika n\rightarrow \infty.

Dengan demikian, pertanyaan di atas dapat diformulasikan sebagai berikut: Carilah suatu fungsi k(n) terkecil (secara asimtotik), sehingga ketika kita mengumpulkan k(n) data tanggal lahir, ada setidaknya 2 data yang memiliki ulang tahun yang sama dengan peluang cukup besar. Dengan cara yang sama, kita akan mencoba untuk menghitung peluang kejadian komplemennya. Dengan kata lain, kita mencari k(n) terkecil sehingga peluang tidak adanya ulang tahun bersama di antara k(n) data menuju 0. Katakanlah p_k merupakan nilai peluang tersebut. Maka

p_k=\dfrac{n}{n}.\dfrac{n-1}{n}\dots\dfrac{n-k+1}{n}=\left(1-\dfrac{0}{n}\right) . \left(1-\dfrac{1}{n}\right)\dots \left(1-\dfrac{k-1}{n}\right)=\prod\limits_{i=0}^{k-1} \left(1-\dfrac{i}{n}\right)

Kita akan mengaproksimasi nilai ini melalui ketidaksamaan (1-x)\le e^{-x}, yang berlaku untuk semua bilangan real x (dapat dibuktikan dengan kalkulus sederhana). Dengan demikian, kita dapatkan

p_k \le \prod\limits_{i=0}^{k-1} e^{-i/n} = \exp\left(-\sum\limits_{i=0}^{k-1} \frac{i}{n}\right) = \exp\left(-\dfrac{O(k^2)}{n}\right)

di mana kesamaan terakhir diperoleh dari rumus deret aritmatika. Dengan demikian, jika kita memilih k(n) sehingga k^2/n merupakan barisan yang menuju tak berhingga saat n\rightarrow \infty, kita akan mendapati p_k \rightarrow 0. Dengan demikian, fungsi apapun yang “lebih besar” dari \sqrt{n} akan membuat p_k \rightarrow 0. Secara matematis, kita dapat menulisnya sebagai berikut, k(n)=\sqrt{\omega n} untuk sembarang \omega=\omega(n), barisan yang divergen selambat apapun itu (arbitrarily slowly). Jadi, ketika k(n)= \sqrt{\omega n}, kita akan menemukan ulang tahun bersama “dengan peluang cukup besar”.

Di sisi lain, ketika kita memiliki k(n)=\Theta(\sqrt{n}), kita akan dapati bahwa p_k=e^{O(1)}, artinya p_k konvergen ke suatu nilai peluang yang positif. Artinya ketika \Theta(\sqrt{n}), kita tidak akan menemukan ulang tahun bersama “dengan peluang cukup besar”. Dengan demikian, simpulan atas penyelidikan kita adalah: \Theta(\sqrt{n}) ada fungsi terbesar sehingga kita tidak akan menemukan ulang tahun bersama “dengan peluang cukup besar” dengan k(n) buah data.

Sebagai contoh, jika kita ambil k(n)=\sqrt{n\log n}, maka p_k\le O(1/n). Ini berarti bahwa ketika kita memiliki \sqrt{n\log n} data, peluang kita tidak mendapati ulangtahun bersama hanya kira-kira sebesar 1/n, suatu nilai yang sangat kecil, bahkan semakin kecil ketika n membesar. Dari n kemungkinan, hanya diperlukan \sqrt{n\log n} data saja untuk mendapatkan ulang tahun bersama “dengan peluang cukup besar”. \sqrt{n\log n} adalah suatu nilai yang sangat kecil dibanding n. Sebagai perbandingan, jika n=10000, maka \sqrt{n\log n} \approx 303,48, suatu nilai yang secara signifikan jauh lebih kecil! Secara sekilas tidak terlihat masuk akal, namun perhitungan matematis membuktikannya!

Jadi, apakah memiliki ulang tahun bersama adalah suatu hal yang jarang? Tentu ya jika Anda membandingkan dengan ulang tahun Anda secara spesifik. Tapi ketika Anda mengumpulkan sedikit data namun dengan cepat menemukan sekelompok orang yang memiliki tanggal ulang tahun yang sama, itu bukan suatu kebetulan. Ada suatu realitas di luar sana yang mengatur bahwa hal semacam ini adalah memang wajar adanya, kendatipun intuisi kita tidak selalu sinkron dengannya. Ada suatu paradox yang mengejutkan, yang tersembunyi secara anggun di balik kesederhanaan yang universal.

Tepok Nyamuk (1) – How much would you suffer from the loss?

Matematika dalam bermain. Bermain dalam matematika.

Salah satu permainan kartu yang cukup populer di Indonesia adalah “Tepok Nyamuk”. Dalam permainan ini, setiap peserta dibagikan sejumlah kartu secara berimbang dalam keadaan tertutup. Setelah itu, salah seorang pemain akan membuka kartu teratas miliknya sambil berteriak “dua”, sementara pemain berikutnya melakukan hal yang sama dan meneriakkan “tiga”, dan seterusnya. Urutan angka yang diucapkan pemain dilakukan secara sirkuler sesuai urutan kartu remi, artinya setelah angka 10, pemain berikutnya akan mengucapkan “Jack”, “Queen”, “King”, “As” dan kemudian kembali lagi ke “dua”. Proses ini akan berhenti ketika nilai kartu yang dikeluarkan seorang pemain sama persis dengan nilai yang disebutkannya itu. Pada saat itu, setiap pemain harus secepat mungkin menepuk kartu tersebut dan pemain terakhir yang menepuk kalah dalam ronde itu, sehingga ia harus mengambil semua kartu yang sudah dikeluarkan sebelumnya untuk masuk ke dalam kartu di tangannya. Pemain pertama yang berhasil menghabiskan kartu di tangannya menjadi pemenang permainan ini.

Tentu permainan ini sangat menarik dan menantang, karena kita harus memusatkan konsentrasi dan kewaspadaan kita ketika kartu-kartu dikeluarkan. Jika kita terlalu lambat untuk menyadari kecocokan urutan yang disebut dan kartu yang dikeluarkan, maka bersiap-siaplah untuk menanggung beban kartu yang bisa jadi tambahan kartu tangan kita!

Namun demikian, di tengah keceriaan dan keseruan permainan ini, kita dapat membuat suatu pertanyaan strategis yang dapat membantu kita memahami inti permainan ini. Ketika kecocokan terjadi dan semua pemain menepuk kartu, kita mempunyai peluang untuk menjadi pemain yang kalah dalam tepukan itu. Jika kita kalah, maka banyak kartu di tangan akan bertambah. Jika tidak, maka tentu banyak kartu tangan kita akan lebih sedikit dari sebelum ronde dimulai (karena diambil si kalah). Nah, seandainya kita kalah dalam suatu ronde, kira-kira berapa perkiraan kartu yang akan kita terima? Tentu saja jawabannya bervariasi! Mungkin saja dalam sekali putaran, sudah terjadi kecocokan, sehingga kartu yang dikeluarkan hanya sedikit. Tapi mungkin juga kecocokan tidak juga terjadi walaupun kita sudah mengeluarkan semua kartu yang kita punya! Tentu saja ini adalah kejadian yang stokastik, namun kita akan berusaha menyelidiki berapa rata-rata kartu yang harus dikeluarkan dalam satu ronde sampai sebuah kecocokan terjadi. Let’s introduce the math!

[prerequisite untuk pemahaman penuh tentang model matematika di bawah hanyalah statistika dasar]

Untuk memperoleh hasil, kita dapat mendekati masalah ini dengan model yang lebih sederhana. Katakanlah kita ubah aturan permainan sehingga setiap pemain tidak memegang kartu di tangan, dan yang ada hanya sebuah deck kartu lengkap dalam keadaan tertutup. Dalam setiap giliran, pemain memilih satu kartu secara acak dan membukanya sambil menyebut sebuah nilai secara terurut. Ketika tidak terjadi kecocokan, maka pemain akan mengembalikan kartu tersebut ke dalam deck secara acak pula. Tentu ini metode bermain yang sangat tidak praktis dan tidak menyenangkan, namun dengan model ini, kita akan memperoleh suatu model matematika yang sangat indah! Tentu saja dengan metode ini, peluang seseorang menyebutkan urutan dan mengeluarkan kartu dengan cocok adalah 1 banding 13, karena terdapat 52 kartu dalam sebuah deck lengkap dan terdapat tepat empat kartu yang nilainya cocok dengan (berapapun) nilai yang disebutkan oleh sang pemain. Fakta inilah yang akan menjadi dasar perhitungan kita!

Sekarang, kita definisikan suatu peubah acak X, yang menyatakan banyak kartu yang perlu dikeluarkan sampai terjadi kecocokan. Seandainya X bernilai k, maka ini berarti bahwa k-1 kartu pertama yang dikeluarkan tidak sesuai dengan nilai urutan yang disebut para pemain, dan kartu ke-k harus menjadi kartu pertama yang nilainya cocok. Seperti yang telah kita bahas di atas, peluang sebuah kartu dikeluarkan dengan cocok adalah 1/13, maka peluang sebuah kartu dikeluarkan tidak cocok adalah 1-1/13=12/13. Dengan demikian, peluang kejadian X=k terjadi adalah sebesar \dfrac{12^{k-1}}{13^k}. Dengan demikian, kita peroleh X merupakan sebuah peubah acak berdistribusi geometrik dengan parameter p=\frac{1}{13} (referensi:http://en.wikipedia.org/wiki/Geometric_distribution). Dan dengan mudah, kita dapat klaim bahwa rata-rata nilai X adalah sebesar \frac{1}{p}=13. (Prove this! It’s fun! Petunjuk: gunakan fungsi pembangkit peluang).

Dengan demikian, kita telah peroleh jawabannya! Ketika kita kalah dalam suatu ronde, maka rata-rata kartu yang akan kita terima adalah sebesar 13 kartu! Jumlah yang cukup banyak ya ternyata! Tentu saja dalam kenyataanya, nilai rata-rata yang akan kita peroleh mungkin sedikit berbeda karena model matematika yang kita pakai berbeda dengan kenyataannya, sehingga nilai inipun juga merupakan estimasi dari rata-rata yang sebenarnya. Namun demikian, saya cukup yakin bahwa nilai rata-rata ini cukup baik untuk memberika gambaran pada permainan yang sebenarnya. Well, sejujurnya saya belum pernah melakukan “test lab” dengan mencatat semua data kartu yang diterima si kalah dan merata-rata nilai tersebut. Jika ada seseorang yang bersedia melakukan itu dan memberitahu hasilnya ke saya untuk mencocokkan apakah benar hasil yang diperoleh memang betul dekat dengan 13, that would be great!

Pertanyaan berikutnya yang mungkin relevan, adalah berapa banyak ronde yang kita perlukan untuk menyelesaikan permainan ini? Seandainya ada 4 pemain, maka masing-masing pemain menerima 13 kartu tangan di awal. Karena dalam 1 ronde, si kalah harus menerima tambahan rata-rata sebanyak 13 kartu, maka kartu tangan pemain lain akan berkurang sekitar \frac{13}{4} kartu, atau sekitar 3 kartu. Dalam kasus terbaik, ketika ada seorang yang tidak pernah kalah sama sekali sepanjang permainan, dia akan menyelesaikan permainan itu dalam 4-5 ronde. Namun apakah nilai ini adalah nilai rata-rata banyak ronde yang diperlukan? Tentu saja tidak! Bagaimana kita menghitung nilai rata-rata ini secara rigorous? Tunggu postingan saya selanjutnya. 🙂

[Silakan coba-coba dulu kalo penasaran. Hint: Markov Chain]

How Many Purchasing do You Need to Gather All Collection of Gifts?

We often find interesting marketing strategy of some cereal manufacture, that is providing some “action figures” in the box wrap. Of course there are many collection of the figure gifts, and yet you can not confirm what kind of figure you will get whenever you buy a box until you purchase it and open the seal. Suppose there are 10 kinds of figure collection. If you are lucky enough, you may gather all of the collection in 10 purchasing in a row, or that means that you always get a different collection every time you buy a cereal! What a lovely event! However, you may also experience some frustrating moment where you have gather 9 collections and you never get the 10th, although you have purchased a numerous cereals (and unfortunately, the cereal is never get eaten!). You buy a cereal and you think that this time you must get the 10th one, but that is not happening! Damn! The company is cheating me! How many more I should buy to get the 10th one? Does that 10-different-gifts-in-row event that rare? Can I be that lucky one?

These questions give us a very interesting mathematical problem, namely coupon collector problem. Suppose there are d collection of figure. How many purchasing do you expect to collect all the d collection? In the calculation of the expectation, we may find many interesting combinatorial properties involving in the progress. OK, let us start!

First, we define a sequence of event \{A_n\}_1^\infty for each n, A_n represent an event of in the n-th purchasing, for the first time you gather every d collections. Let p_n be the probability of the event A_n, which is p_n=P(A_n). Well, the event A_n is completely the event you really want to experience. Clearly that if we have the event A_n, then the number of purchasing we need is n. It would be very nice if n is as small as possible. However, we are about to calculate for which value of n in which most likely everybody experience the event A_n? By the basic statistics, we have the expectation of the number of purchasing needed to collect all the collection is \mu=\sum\limits_{n\geq 1} np_n.

Next, how would we calculate the value of p_n? To begin this, we introduce the notion \begin{Bmatrix} n \\ k \end{Bmatrix}, which denote the Stirling number of the second kind.

\begin{Bmatrix} n \\ k \end{Bmatrix} = number of partitions of \{1,2,\dots, n,\} into exactly k class.

For example, if n=4 and k=2, then we are about to collect every possible partitions of \{1,2,3,4\} into exactly 2 class. Below is the lists of every possible partitions:

\{ \{1,2\}, \{3,4\} \}

\{ \{1,3\}, \{2,4\} \}

\{ \{1,4\}, \{2,3\} \}

This means that \begin{Bmatrix} 4 \\ 2 \end{Bmatrix}=3. Note that the order of the classes in the partition is not considered significant. Well, now we are ready to calculate the value of p_n.

The sample space of the event in this context is the set of all possible outcomes in the sequence of n purchasing. For every purchase, we have d possibilities of outcomes. Therefore the size of the sample space is d^n. Now we move into how many possible outcomes in which the event A_n happen. Suppose we have the event A_n occurred, means that when you purchase the n-th cereal, for the first time, you get the last collection (one thing you’d die for) which you have not owned yet before. Surely this must be the very condition, right? So, we can partition the times of purchasing, \{1,\dots,n\}, into exactly d classes, which means that if k belongs to the class j, then in the purchasing of k, you got the collection number j. Of course you can not have a class of size zero, since you have to gather every collection in the n purchasing. And also, n must be in a class having no other else in that class, i.e \{n\} must be a single class. This means, we should not worry about the class of n, since it always to be solitary. However, we still deal with those n-1 purchasing before the last one over the d-1 choices of collectibles. So in order to produce the partition, we have \begin{Bmatrix} n-1 \\ d-1 \end{Bmatrix} types of partitions. Moreover, since the order of the partition is such a matter for us, we multiply again this number to d!, as we have d classes in the partition.

Therefore, p_n=\dfrac{d!\begin{Bmatrix} n-1 \\ d-1 \end{Bmatrix}}{d^n}

However, how would we calculate the mean of number of purchasing? First we define a probability generating function of p_n, which is

P(x)=\sum\limits_{n\geq 1} p_n x^n

By some combinatorial analysis, (I wouldn’t talk about this in this post, maybe later :D), we can get the formula of the GF:

P(x)=\dfrac{x^d(d-1)!}{(x-d)(x-2d)\dots (x-(d-1)d)}

However, we can compute the expectation by \mu=P'(1). Therefore, by differentiating the generating function, we can get

\mu =d H_d where H_d is the harmonic number H_d=1+\frac{1}{2}+\dots + \frac{1}{d} and therefore the average number of purchasing so that you can collect every d collectibles is d\left(1+\frac{1}{2}+\dots + \frac{1}{d}\right). (You could check by yourself if you want!) Seems not friendly enough to understand? Okay, let say d=10. Then the average number is 10(1+1/2+1/3+…+1/10)=29.2897. This means most people complete the collections after the 29th purchasing. So, if you have bought 20 boxes, and you still have 7 collection, that’s fine. Everybody experience the same, you should ‘try’ harder! So, hey, what if the number of collectibles is not 10? Yes, you can compute the expected number by yourself. It’s easy enough to do naive computation by calculator. So, are you hunting for those gifts? You’d better check your lucky number!

Have fun with mathematics! Good luck!

 

 

Reference: Wilf, Herbert S. Generatingfunctionology. Academic Press. 1994