Pendahuluan

Misalkan saya bertanya kepada Anda berapa banyak orang yang harus berada di kamar sehingga dua dari mereka memiliki hari ulang tahun dengan kemungkinan 50% dalam satu hari. Apa yang akan menjadi jawabannya? Inilah yang disebut paradoks ulang tahun.

Paradoks berbunyi:

Jika ada 23 orang di ruangan itu, maka dengan probabilitas 50% dua dari mereka dilahirkan pada hari yang sama.

Beberapa versi paradoks membuat pernyataan lebih kuat:

Jika ruangan itu memiliki 70 orang, maka dengan probabilitas 99%, dua di antaranya lahir pada hari yang sama.

Pada awalnya, ini tampak mengejutkan dan berlawanan dengan intuisi saya. Mari kita cari tahu mengapa ini benar. Untuk menyederhanakan tugas, kami membuat asumsi berikut:

1. Kami berasumsi bahwa semua orang di ruangan itu tidak dilahirkan pada tahun kabisat. Kami membuat asumsi ini sehingga kami tidak perlu menganalisis dua kasus yang berbeda.
2. Tidak ada anak kembar di kamar. Dengan sepasang kembar, solusinya akan sepele.
3. Kami berasumsi bahwa orang dilahirkan secara merata dan acak. Apa artinya ini? Orang-orang kemungkinan lahir pada hari yang sama. Jika ini diformalkan sedikit, maka probabilitas kelahiran pada hari yang dipilih sama dengan $$$\ frac {1} {365}$ .
4. Orang dilahirkan secara independen satu sama lain. Ini berarti bahwa tanggal lahir seseorang tidak memengaruhi tanggal lahir orang lain.

Perlu dicatat bahwa kondisi ini tidak harus diamati di dunia nyata. Khususnya, di dunia nyata, orang tidak dilahirkan dengan keacakan yang seragam. Tautan ini memiliki statistik untuk hari-hari di mana orang dilahirkan. Meskipun model kami bukan cerminan akurat dari dunia nyata, kesederhanaannya membuatnya lebih mudah untuk menganalisis masalah.

Saya harus mengatakan bahwa jika ada 366 orang atau lebih di sebuah ruangan, maka dijamin memiliki dua orang dengan ulang tahun yang sama. Ini mengikuti prinsip Dirichlet (“prinsip merpati dan kotak”): jika ada 366 orang dan 365 hari, maka setidaknya dua orang harus memiliki ulang tahun yang sama.

Bayangkan ada satu orang di ruangan itu, maka kemungkinan ulang tahunnya yang sama dengan orang lain adalah 0. Biarkan $$$(A_n)$ akan menjadi hasil di antaranya $$$n$ orang tidak memiliki satu hari ulang tahun. Biarkan $$$\ Pr [A_n]$ - probabilitas itu di antara $$$n$ orang-orang di ruangan itu, setiap orang memiliki hari ulang tahun pada hari mereka. Demikian pula, mari $$$\ overline {A_n}$ akan menjadi pelengkap $$$A_n$ , yaitu sebuah hasil di antaranya $$$n$ orang dua orang memiliki ulang tahun yang sama.

$$

$$\ Pr [A_n] + \ Pr [\ overline {A_n}] = 1$$

$$

$$\ Pr [A_1] = 1 \ text {karena hanya ada satu orang di ruangan}$$

Misalkan ada dua orang di ruangan itu, A dan B. Tanpa kehilangan generalisasi, bayangkan orang itu lahir pada 1 Januari. Agar B dan A memiliki hari ulang tahun yang berbeda, B harus dilahirkan pada hari apa pun kecuali 1 Januari. Orang B akan memiliki 364 opsi ulang tahun.

$$

$$\ Pr [A_2] = \ Pr [\ text {B berbeda dari A}] = \ frac {364} {365}$$

Bayangkan ada tiga orang di ruangan itu, A, B, dan C. Misalkan orang A lahir pada 1 Januari, sehingga semuanya lahir pada hari yang berbeda, orang B hanya punya 364 hari, seperti pada contoh sebelumnya. Karena A dan B memakan waktu dua hari, orang C hanya dapat dilahirkan pada 365 - 2 = 363 hari.

$$

$$\ Pr [A_3] = \ Pr [\ teks {B berbeda A dan C berbeda dari B, A}] = \ frac {364} {365} \ times \ frac {363} {365}$$

Sesuatu yang lebih menarik terjadi di sini: misalkan ruangan sudah ada $$$k - 1$ orang. Ketika dia memasuki ruangan $$$k$ orang itu $$$k$ orang memiliki ulang tahun yang berbeda, dua hasil pasti benar

1. Semua $$$k - 1$ orang yang memasuki ruangan sebelum dia harus memiliki ulang tahun yang berbeda. Apa kemungkinan ini? $$$\ Pr [A_ {k-1}]$ .
2. $$$k$ - orang itu perlu memiliki ulang tahun yang berbeda dari yang lainnya $$$k - 1$ orang di dalam ruangan. Apa kemungkinan ini? $$$\ frac {365 - (k-1)} {365}$ .

Perlu juga dicatat bahwa dua hasil yang disajikan di atas saling independen, karena dengan asumsi (4) dibuat pada awal posting, $$$k$ Orang kedua dilahirkan secara terpisah dari yang lainnya.

$$$$ tampilan $$ \ begin {persamaan *} \ begin {split} \ Pr [A_k] & = \ Pr [k - 1 \ text {orang-orang di ruangan memiliki ulang tahun yang berbeda} \ textbf {AND} \\ & \ \ \ \ \ \ \ \ teks {orang k memiliki ulang tahun yang berbeda dari} k - 1 \ teks {orang}] \\ & = \ Pr [k - 1 \ teks {orang-orang di ruangan memiliki ulang tahun yang berbeda}] \\ & \ \ \ \ \ kali \ Pr [\ teks {orang k memiliki hari ulang tahun yang berbeda dari} k - 1 \ teks {orang}] \\ & = \ Pr [A_ {k-1}] \ kali \ frac { 365 - (k-1)} {365} \ end {split} \ end {persamaan *} $$ menampilkan $$

Sekarang kami menghitung probabilitas:

$$$$ menampilkan $$ \ mulai {persamaan *} \ mulai {split} \ Pr [A_1] & = 1 \\ \ Pr [A_2] & = \ Pr [A_1] \ kali \ frac {364} {365} = \ frac {364} {365} \ sekitar 0,997 \\ \ Pr [A_3] & = \ Pr [A_2] \ times \ frac {363} {365} = \ frac {364} {365} \ times \ frac {363} {365} \ sekitar 0,991 \\ \ Pr [A_4] & = \ Pr [A_3] \ kali \ frac {362} {365} \ sekitar 0.983 \\ & \ vdots \\ \ Pr [A_ {22}] & = \ Pr [A_ {21}] \ times \ frac {344} {365} \ sekitar 0,525 \\ \ Pr [A_ {23}] & = \ Pr [A_ {22}] \ times \ frac {343} {365 } \ kira-kira 0,493 \\ \ end {split} \ end {persamaan *} $$ menampilkan $$

Sejak kita dapatkan $$$\ Pr [A_ {23}] = 0,493 <0,5$ , ini berarti bahwa probabilitas ulang tahun yang sama untuk dua orang adalah sama

$$

$$\ Pr [\ overline {A_ {23}}] = 1 - \ Pr [A_ {23}] = 1 - 0,493 = 0,507> 0,5$$

Dengan peningkatan $$$n$ probabilitas cenderung 1 dan mencapainya.

Tugas yang lebih sulit

Misalkan kita ingin menggeneralisasi masalah ini ke kasus ketika ada $$$n$ orang dan $$$m$ mungkin ulang tahun. Memiliki $$$n, m$ , bisakah kita menentukan kemungkinan bahwa dua orang akan memiliki hari ulang tahun yang sama?

Anda dapat menggunakan sistem yang sama: kami akan memiliki hasil $$$A_n$ menunjukkan semua $$$n$ orang yang lahir pada hari yang berbeda. Dalam kasus satu orang, tidak ada yang berubah

$$

$$\ Pr [A_1] = 1$$

Dalam kasus di mana ada dua orang, kami menunjuk mereka sebagai A dan B. Untuk orang B yang akan lahir di hari lain, orang B harus memiliki hari ulang tahun di antara $$$m - 1$ opsi lain.

$$

$$\ Pr [A_2] = \ frac {m-1} {m}$$

Dalam kasus tiga orang, orang B harus memiliki hari ulang tahun yang berbeda dari hari ulang tahun A. Orang C harus memiliki hari yang berbeda dengan hari ulang tahun A dan B.

$$

$$\ Pr [A_3] = \ frac {m-1} {m} \ times \ frac {m-2} {m}$$

Umumnya untuk apa saja $$$n$ kita dapat menggunakan rumus rekursif yang sama seperti pada bagian sebelumnya:

$$

$$\ Pr [A_n] = \ Pr [A_ {n-1}] \ times \ frac {m - (n-1)} {m}$$

Misalkan jika kita ingin menemukan ekspresi dalam bentuk tertutup untuk $$$\ Pr [A_n]$ , lalu kami menguraikan ekspresi

$$$$ menampilkan $$ \ begin {persamaan *} \ begin {split} \ Pr [A_n] & = \ Pr [A_ {n-1}] \ times \ frac {m - (n-1)} {m} \ \ & = \ Pr [A_ {n-2}] \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ Pr [A_ {n-3}] \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n -1)} {m} \\ & \ \ vdots \\ & = \ Pr [A_2] \ times \ frac {m-2} {m} \ times \ frac {m-3} {m} \ times \ cdots \ times \ frac {m - (n-3)} {m} \ times \ frac {m - (n-2)} {m} \ times \ frac {m - (n-1)} {m} \\ & = \ prod_ {i = 1} ^ {n-1} \ frac {mi} {m} = \ prod_ {i = 1} ^ {n-1} 1 - \ frac {i} {m} \\ & \ approx \ prod_ {i = 1} ^ {n-1} e ^ {\ frac {-i} {m}} \ text {menggunakan identitas} 1 - x \ approx e ^ {- x} \\ & = e ^ {- \ sum_ {i = 1} ^ {n-1} \ frac {i} {m}} \\ & = e ^ {\ frac {-n (n-1)} {2m}} \ approx e ^ {\ frac {-n ^ 2} {2m}} \ end {split} \ end {persamaan *} $$ menampilkan $$

Perkiraan hasil ini adalah $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}}$ . Meskipun kami dapat menemukan lebih banyak batas perkiraan, ini memberi kami perkiraan yang cukup. Satu-satunya identitas yang kami gunakan dalam perkiraan ini:

$$

$$1 - x \ kira-kira ^ {- x}$$

Dalam bentuk abstraknya, paradoks ulang tahun memiliki banyak kegunaan dalam komputasi komputer. Secara khusus, ini digunakan dalam hashing, yang dengan sendirinya memiliki banyak kegunaan. Kesimpulan yang dibuat dalam tugas ini adalah kunci untuk menganalisis probabilitas hashing dua elemen menjadi satu kunci. Masalah ini selanjutnya dapat digeneralisasikan ke masalah probabilistik bola dan baskom (masalah bola dan sampah), yang akan kita tinggalkan untuk posting lain.

Aplikasi

Paradoks ulang tahun bukan hanya tugas buatan atau trik pesta yang menarik, ia memiliki banyak aplikasi dunia nyata. Secara pribadi, saya percaya bahwa analisis probabilistik yang digunakan dalam bukti berguna dalam menganalisis tugas-tugas lain yang melibatkan pengacakan. Secara khusus, ini berkaitan dengan pengembangan fungsi hash kriptografi. Kita akan melihat bagaimana analisis yang dibuat di atas bisa sangat berguna dalam menciptakan fungsi hash dengan perlindungan terhadap serangan "ulang tahun".

Pertama, mari kita tentukan apa fungsi hash. Fungsi hash $$$h: U \ rightarrow [0, m-1]$ Merupakan fungsi yang melakukan pemetaan dari suatu set $$$U$ dalam angka dalam kisaran $$$[0, m-1]$ . Fungsi $$$h$ didefinisikan sebagai $$$h (x) = x \ mod m$ - contoh fungsi hash dari $$$\ mathbb {N} \ rightarrow [0, m-1]$ . Fungsi hash memiliki banyak kegunaan, terutama dalam kombinasi dengan struktur data tabel hash yang populer. Ini juga digunakan dalam kriptografi, di mana jenis fungsi hash tertentu yang disebut "fungsi hash cryptoraphic" digunakan.

Salah satu dari banyak sifat yang harus dimiliki fungsi hasp cryptoraphic adalah resistensi tabrakan. Pasti sulit menemukan dua itu $$$u_1, u_2 \ dalam U$ sehingga mereka membentuk tabrakan, yaitu $$$h (u_1) = h (u_2)$ .

Ini adalah perlawanan terhadap tabrakan yang akan kita fokuskan. Pertama, saya akan menjelaskan mengapa ini adalah properti yang diinginkan. Untuk melakukan ini, pertama-tama kita akan mempertimbangkan tanda tangan digital.

Di masa lalu, orang dan organisasi menggunakan tanda tangan dan stempel untuk "menandatangani" dokumen. Baru-baru ini, telah ada transisi ke tanda tangan elektronik atau digital. Tanda tangan digital harus memenuhi tiga sifat dasar.

1. Saat menandatangani dokumen, Anda harus dapat memverifikasi siapa yang menandatangani dokumen.
2. Setelah menandatangani dokumen, tidak ada yang bisa memalsukannya.
3. Orang yang telah menandatangani dokumen selanjutnya tidak dapat membantah penandatanganan dokumen.

Tanda tangan digital adalah cara membuktikan kebenaran suatu dokumen atau pesan. Tanda tangan digital memastikan bahwa pesan yang diterima dibuat oleh pengirim yang dikenal dan tidak diubah.

Katakanlah kita punya dokumen $$$m$ . Bagaimana kita menandatanganinya?

Setiap pengguna / organisasi memiliki kunci pribadi yang unik $$$p_k$ dan kunci publik $$$pub_k$ . Mereka menggunakan fungsi penandatanganan untuk menandatangani dokumen dengan kunci pribadi mereka sendiri. Namun, tanda tangan digital hanya dapat menandatangani sejumlah kecil dokumen. Cakupan fungsi tanda tangan kecil. Salah satu cara untuk mengatasi masalah ini adalah dengan membuat dokumen yang lebih kecil yang mewakili dokumen asli, tetapi dalam ukuran yang jauh lebih kecil. Paling sering, fungsi hash diterapkan pada dokumen besar ini. Fungsi hash digunakan untuk memetakannya dari ruang besar ke yang lebih kecil, dan hasil dari operasi semacam itu disebut "sidik jari". Tanda tangan menggunakan sidik jari dan kunci pribadi untuk membuat tanda tangan. Prosedurnya dapat dijelaskan sebagai berikut:

1. Dapatkan kunci pribadi $$$p_k$ .
2. Hash dokumen $$$m$ dan dapatkan $$$h (m)$ .
3. Tanda tangan $$$h (m)$ menggunakan kunci pribadi $$$p_k$ .
4. Kami kirim $$$sign (h (m), p_k)$ dan kunci publik $$$pub_k$ siapa pun yang ingin mengkonfirmasi dokumen.

Siapa pun yang memilikinya $$$sign (h (m), p_k))$ dan kunci publik, dapat memeriksa apakah dokumen tersebut benar-benar $$$m$ ditandatangani oleh orang yang tepat.

Masalah: misalkan penyerang Eva menemukan dua dokumen $$$m, m '$ dimana $$$m$ - ini adalah kontrak saat ini, dan $$$m '$ - dokumen penipuan sedemikian rupa sehingga $$$h (m) = h (m ')$ . Misalkan Hawa tahu sebelumnya bahwa Alice hanya akan masuk $$$m$ tapi tidak $$$m '$ . Sebelum menandatangani, fungsi hash kriptografis diterapkan pada dokumen $$$h$ . Eve pergi ke Alice dan memintanya untuk menandatangani dokumen $$$m$ menggunakan urutan yang dijelaskan di atas. Sekarang, Eve dapat mengklaim bahwa Alice menandatangani dokumen penipuan $$$m '$ karena $$$h (m) = h (m ')$ . Alice tidak akan dapat membuktikan dengan cara apa pun bahwa dia tidak menandatangani $$$m '$ .

Dalam contoh di atas $$$h$ ternyata merupakan fungsi tahan tabrakan, sehingga Eve dapat menemukan dua set data masuk yang hash nilai yang sama. Eve dapat mengklaim bahwa Alice menandatangani $$$m '$ meskipun sebenarnya dia hanya menandatangani $$$m$ . Ini menggarisbawahi pentingnya resistensi tabrakan dan menunjukkan mengapa tanda tangan digital rentan jika fungsi hash tidak stabil.

Biarkan $$$h: U \ rightarrow [0, m-1]$ akan menjadi fungsi hash. Asumsikan bahwa data input secara acak dan independen hash ke salah satu elemen $$$m$ .

Tugas serangan "ulang tahun" adalah untuk menemukan jumlah elemen terkecil $$$n$ yang dapat di hash dengan $$$h$ sehingga kita dapat menemukan dua elemen $$$x, y \ dalam U$ dimana $$$h (x) = h (y)$ .

Saat menyerang "ulang tahun," penyerang akan mengambil secara acak $$$x \ dalam U$ dan menjaga pasangan $$$(x, h (x))$ . Penyerang akan berulang kali memilih dan menyimpan pasangan ini sampai ia menemukan dua nilai $$$x, y$ dimana $$$h (x) = h (y)$ . Kita perlu menentukan berapa kali penyerang perlu mengulangi operasi ini sampai dia menemukan tabrakan.

Untuk menganalisis serangan "ulang tahun", Anda dapat menggunakan prinsip yang sama yang kami gunakan untuk paradoks ulang tahun. Dalam serangan "ulang tahun" $$$m$ menunjukkan jumlah hari dalam setahun, dan $$$U$ mirip dengan orang memasuki ruangan. Orang-orang di-hash pada hari ulang tahun mereka, yang bisa menjadi salah satu artinya. $$$m$ . Katakanlah kita perlu menemukan tabrakan dengan probabilitas 99%. Kita perlu tahu apa yang terkecil $$$n$ , di mana hash dari dua nilai akan menjadi satu ulang tahun (di dunia fungsi hash, ini berarti bahwa dua set data input hash ke dalam nilai yang sama).

Kami sebelumnya menunjukkan itu $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}}$

Kami ingin bertanya $$$\ Pr [\ overline {A} _n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {99} {100}$ itu adalah $$$\ Pr [A_n] \ approx e ^ {\ frac {-n ^ 2} {2m}} = \ frac {1} {100}$ .

$$$$ menampilkan $$ \ begin {persamaan *} \ begin {split} e ^ {\ frac {-n ^ 2} {2m}} & = \ frac {1} {100} \\ \ frac {n ^ 2} {2m} & = \ ln 100 \\ n ^ 2 & = 2 m \ ln 100 \\ n & = \ sqrt {2 m \ ln 100} \ end {split} \ end {persamaan *} $$ tampilkan $$

Analisis yang ditunjukkan di atas memberitahu kita bahwa untuk mendapatkan tabrakan dalam fungsi hash dengan interval ukuran $$$m$ penyerang perlu melakukan hash secara seragam dan independen $$$\ sqrt {2 m \ ln 100} = O (\ sqrt {m})$ untuk jaminan yang hampir lengkap (probabilitas 99%) bahwa dua elemen di-hash dengan nilai yang sama.

Misalkan kita ingin mendapatkan tabrakan dengan probabilitas 50%; maka kita perlu $$$n = \ sqrt {2 m \ ln 2}$ . Kesimpulan penting di sini adalah bahwa untuk mendapatkan tabrakan dengan probabilitas lebih dari 0,5, kita harus memotong pesanan $$$\ sqrt {m}$ elemen. Ini konsisten dengan analisis kami sebelumnya untuk $$$m = 365$ karena $$$\ sqrt {2 \ ln 2 \ cdot 365}$ kira-kira sama dengan 23.

Tugas Tambahan

1. Memiliki $$$n$ orang $$$m$ hari dan angka tertentu $$$k$ temukan probabilitas yang tepat $$$k$ orang-orang memiliki ulang tahun yang sama.
2. Mari kita sedikit mengubah tugas di atas. Katakanlah kita punya $$$m$ hari dan angka tertentu $$$k$ . Apa yang akan menjadi nilai terkecil $$$n$ di mana tidak kurang $$$k$ orang akan berulang tahun dengan probabilitas minimal 0,5? Bisakah Anda menggeneralisasi tugas ini dengan segala kemungkinan $$$p> 0$ ?
3. Misalkan kita memiliki 100 angka dari 1 hingga 100, serta mesin menebak angka acak dari 1 hingga 100 dalam urutan yang seragam dan acak. Berapa kali kita perlu menggunakan mesin seperti yang diharapkan, sehingga mesin menebak semua angka dari 1 hingga 100?
4. Bisakah Anda menggeneralisasi tugas ini ke siapa saja $$$n$ ?
5. Misalkan kita memiliki fungsi hash yang secara acak menampilkan elemen di wilayah memori. Biarkan total area $$$m$ . Berapa banyak item $$$n$ apakah kita perlu menambahkan ekspektasi matematis ke struktur data kita sehingga setidaknya dua elemen di hash di setiap wilayah?