Kombinasi sederhana / pertanyaan probabilitas berdasarkan panjang string dan karakter yang memungkinkan

Dengan asumsi "keacakan lengkap" dan diberi string dengan panjang 20 karakter di mana masing-masing karakter mungkin salah satu dari 62 karakter yang mungkin:

Berapa jumlah total kombinasi yang mungkin? (Menebak 20 pangkat 62.)
Juga, jika string baru dipilih secara acak satu demi satu dan ditambahkan ke daftar string yang dipilih sejauh ini, berapa banyak string yang harus dipilih sebelum kemungkinan memilih string yang telah dipilih di bawah 1-in-100000 ( $10^{-5}$ )?

Catatan: 62 berasal dari: digit angka (0-9), huruf besar (AZ), dan huruf kecil (az).

probability combinatorics kesalahan besar
sumber

Poin kedua Anda dapat dibaca dalam (setidaknya) dua cara yang memungkinkan. Saya ingin tahu yang Anda tertarik. ( 1 ) Probabilitas bahwa string ke-

n

$n$ cocok dengan salah satu string sebelumnya atau ( 2 ) Probabilitas bahwa pada saat string ke-

n

$n$ dipilih, ada beberapa duplikat dalam koleksi string yang ditarik sejauh ini. Jawaban untuk dua pertanyaan ini akan sangat berbeda. :)

kardinal

Mungkin mempertimbangkan alfabet dua karakter akan membuat perbedaan menjadi jelas. Biarkan huruf menjadi

dan

. Kita dapat bertanya: ( 1 ) Untuk

apa yang kita miliki setidaknya 99% peluang string ke-

menjadi duplikat dari string sebelumnya? The

di sini adalah 8 karena satu-satunya cara kita gagal adalah jika urutan kami adalah baik

atau

, yang memiliki probabilitas total

. Atau, kami bertanya ( 2 ) Untuk apa

H

$H$

T

$T$

n

$n$

n

$n$

n

$n$

T T T \dots T H

$TTT \cdots TH$

H H H \dots H T

$HHH\cdots HT$

2^{- (n - 1)}

$2^{-(n-1)}$

apakah kita memiliki setidaknya 99% peluang untuk melihat duplikat? Dalam hal ini

karena pada saat kita telah melihat tiga string

atau

telah diulang setidaknya satu kali.

n

$n$

n = 3

$n = 3$

H

$H$

T

$T$

kardinal

Jawaban Matt menangani ( 1 ), yang pada dasarnya menjawab pertanyaan tentang apakah string "saya" cocok dengan milik orang lain. Tapi, jika Anda khawatir tentang string dua orang lain juga berpotensi cocok, maka Anda tertarik ( 2 ). Itu tergantung pada apakah Anda memiliki serangkaian minat tertentu yang Anda bandingkan dengan semua orang lain atau apakah Anda membandingkan semua string satu sama lain. Saya tidak yakin apakah saya membuatnya lebih jelas. (Masalah Anda bermuara pada salah satu dari dua varian yang disebut "masalah ulang tahun" yang terkenal).

kardinal

Kardinal, seperti biasa, benar. Saya berasumsi bahwa Anda memiliki satu string "target", yang untuknya Anda membuat daftar tebakan. Jika sebaliknya, Anda menghasilkan string secara acak dan ingin tahu nomor yang aman dibuat sebelum dua string apa pun cocok, maka jawabannya memang sangat berbeda. Saya akan mengubah jawaban saya untuk mengatasi kasus itu, jika Anda setuju.

Matt Krause

Saya tidak membuat contoh saya sebelumnya sepenuhnya jelas. Maaf soal itu. Saya sedang memikirkan alfabet dua huruf

dan menggambar string satu panjang . Oleh karena itu, ketika saya menulis

, yang berdiri untuk

, ...,

{H, T}

$\{H,T\}$

H H H \dots H T

$HHH\cdots HT$

s_{1} = H

$s_1 = H$

s_{2} = H

$s_2 = H$

s_{n - 1} = H

$s_{n-1} = H$

s_{n} = T

$s_n = T$

kardinal

Jumlah total kemungkinan

1) Tutup! Anda punya 62 pilihan untuk karakter pertama, 62 untuk ke-2, dll, jadi Anda berakhir dengan , yang merupakan angka yang sangat besar. $62 \cdot 62 \cdot 62 \cdot \cdots 62 = 62^{20}$

Tabrakan dengan String "Target"

2) Seperti yang kami tegaskan di atas, ada string potensial. Anda ingin tahu berapa banyak yang harus Anda tebak untuk memiliki peluang lebih dari 1 dalam 100.000 untuk menebak string "target". Pada dasarnya, Anda bertanya apa $62^{20}$ Untuk membuatnya tepat, Anda harus mengumpulkan x (atau menambahkan satu, jika mereka sama persis), tetapi seperti yang akan Anda lihat dalam hitungan detik, itu tidak masalah.

\frac{x}{62^{20}} \geq \frac{1}{10^{5}}

$\frac{x}{62^{20}} \ge \frac{1}{10^5}$

Melalui aljabar dasar, kita dapat mengaturnya kembali menjadi

\begin{aligned} 10^{5} x & \geq 62^{20} \\ 10^{5} x & \geq (6.2 \cdot 10)^{20} \\ 10^{5} x & \geq {6.2}^{20} \cdot 10^{20} \\ x & \geq {6.2}^{20} \cdot 10^{15} \end{aligned}

$\begin{aligned} 10^5x &\ge 62^{20}\\ 10^5{x} &\ge (6.2 \cdot 10)^{20}\\ 10^5x &\ge 6.2^{20} \cdot 10^{20}\\ x &\ge 6.2^{20} \cdot 10^{15} \end{aligned}$

Melakukan matematika, adalah sekitar , jadi mari kita sebut semuanya atau, lebih ringkasnya, banyak sekali. $6.2^{20}$ $7 \cdot 10^{15}$ $7 \cdot 10^{30}$

Ini, tentu saja, mengapa kata sandi panjang bekerja dengan sangat baik :-) Untuk kata sandi asli, tentu saja, Anda harus khawatir tentang untaian yang panjangnya kurang dari atau sama dengan dua puluh, yang meningkatkan jumlah kemungkinan lebih banyak lagi.

Duplikat dalam daftar

Sekarang, mari kita pertimbangkan skenario lainnya. String dihasilkan secara acak dan kami ingin menentukan berapa banyak yang dapat dihasilkan sebelum ada peluang 1: 100.000 dari dua string yang cocok. Versi klasik dari masalah ini disebut Masalah Ulang Tahun (atau 'Paradox') dan menanyakan berapa kemungkinan bahwa dua orang memiliki ulang tahun yang sama. Artikel wikipedia [1] terlihat bagus dan memiliki beberapa tabel yang mungkin berguna bagi Anda. Namun demikian, saya akan mencoba memberi Anda rasa untuk jawabannya di sini juga.

Beberapa hal yang perlu diingat:

-Kemungkinan kecocokan dan tidak memiliki kecocokan harus berjumlah 1, jadi dan sebaliknya. $P(\textrm{match}) = 1 - P(\textrm{no match})$

-Untuk dua peristiwa independen dan , probabilitas . $A$ $B$ $P(A \& B) = P(A) \cdot P(B)$

Untuk mendapatkan jawabannya, kita akan mulai dengan menghitung probabilitas tidak melihat kecocokan untuk sejumlah string . Setelah kita tahu bagaimana melakukan itu, kita dapat menetapkan persamaan itu sama dengan ambang (1 / 100.000) dan menyelesaikannya untuk . Untuk kenyamanan, sebut saja jumlah string yang mungkin ( ). $k$ $k$ $N$ $62^{20}$

Kita akan 'berjalan' ke bawah daftar dan menghitung probabilitas bahwa string ^ {th} cocok dengan salah satu string "di atas" dalam daftar. Untuk string pertama, kami memiliki total string dan tidak ada dalam daftar, jadi $k$ $N$ . Untuk string kedua, masih adakemungkinan total, tetapi salah satu dari mereka telah "habis" oleh string pertama, sehingga probabilitas kecocokan untuk string ini adalah $P_{k=1}(\textrm{no match}) = \frac{N}{N} = 1$ $N$ Untuk string ketiga, ada dua cara untuk itu kecocokan dan oleh karena itucara untuk tidak, jadi $P_{k=2}(\textrm{no match}) = \frac{N-1}{N}$ $N-2$ dan seterusnya. Secara umum, probabilitasstringtidak cocok dengan yang lain adalah $P_{k=3}(\textrm{no match}) = \frac{N-2}{N}$ $k$

P_{k} (no match) = \frac{N - k + 1}{N}

$P_{k}(\textrm{no match})= \frac{N-k+1}{N}$

$k$

P (No Matches) = \frac{N}{N} \cdot \frac{N - 1}{N} \cdot \frac{N - 2}{N} \dots \frac{N - k + 1}{N}

$P(\textrm{No Matches}) = \frac{N}{N} \cdot \frac{N-1}{N} \cdot \frac{N-2}{N} \cdots \frac{N-k+1}{N}$

\begin{aligned} P (No Matches) & = \frac{N \cdot (N - 1) \cdot (N - 2) \dots (N - k + 1)}{N^{k}} \\ P (No Matches) & = \frac{N!}{N^{k} \cdot (N - k)!} \\ P (No Matches) & = \frac{k! \cdot (\binom{N}{k})}{N^{k}} \end{aligned}

$\begin{aligned} P(\textrm{No Matches}) &= \frac{N \cdot (N-1) \cdot (N-2) \cdots (N-k+1)}{N^k} \\ P(\textrm{No Matches}) &= \frac{N!}{N^k \cdot (N-k)!} \\ P(\textrm{No Matches}) &= \frac{k! \cdot \binom{N}{k}}{N^k} \\ \end{aligned}$

k! = (k) \cdot (k - 1) \cdot (k - 2) \dots 1

$k! = (k) \cdot (k-1) \cdot (k-2) \cdots 1$

N - k + 1 \dots N

$N-k+1 \cdots N$

k

$k$

\frac{1}{100, 000}

$\frac{1}{100,000}$

k

$k$

100!

$100!$

k = 0.5 + \sqrt{0.25 - 2 N \ln (p)}

$k = 0.5 + \sqrt{0.25 - 2N\ln(p)}$

N = 48, 000

$N=48,000$

3.7 \cdot 10^{15}

$3.7 \cdot 10^{15}$

Referensi

[1] http://en.wikipedia.org/wiki/Birthday_problem

[2] Mathis, Frank H. (Juni 1991). "Masalah Ulang Tahun yang Disamaratakan". Ulasan SIAM (Masyarakat untuk Industri dan Matematika Terapan) 33 (2): 265-270. Tautan JSTOR

Matt Krause
sumber

+1 Luar biasa, mengingat dengan jelas kemampuan matematika saya yang buruk menghasilkan pertanyaan, jadi saya akan meninggalkan pertanyaan itu tanpa jawaban selama sehari, tetapi terlihat baik bagi saya, dan jauh lebih jelas dari jawaban daripada yang saya harapkan - terima kasih!

kesalahan

Senang untuk membantu! Beri tahu saya jika ada yang tidak jelas. Untuk tendangan, saya berlari angka. Anda membutuhkan tebakan 7044234255469980229683302646164; seperti yang saya katakan - banyak!

Matt Krause

+1 @Matt Krause: +1 untuk komentar Anda di bawah jawaban; jawaban dan komitmen Anda untuk memberikan jawaban terbaik adalah teladan, patut dicatat, dan terima kasih atas semua kerja keras Anda!

kesalahan

Kombinasi sederhana / pertanyaan probabilitas berdasarkan panjang string dan karakter yang memungkinkan

Jawaban:

Jumlah total kemungkinan

Tabrakan dengan String "Target"

Duplikat dalam daftar

Referensi