Proste pytanie o kombinację / prawdopodobieństwo oparte na długości łańcucha i możliwych znakach

Zakładając „całkowitą losowość” i ciąg o długości 20 znaków, przy czym każdy znak może być jednym z 62 możliwych znaków:

Jaka jest łączna liczba możliwych kombinacji? (Zgadywanie 20 do potęgi 62.)
Ponadto, jeśli nowe ciągi są losowo wybierane jeden po drugim i dodawane do listy wybranych do tej pory ciągów, to ile ciągów należy wybrać, zanim szansa na wybranie już zaznaczonego ciągu jest mniejsza niż 1 na 100000 ( )? $10^{-5}$

Uwaga: 62 pochodzi od: cyfr (0-9), wielkich liter (AZ) i małych liter (az).

probability combinatorics

— błędy
źródło

Drugi punkt możesz odczytać (co najmniej) na dwa możliwe sposoby. Zastanawiam się, kim jesteś zainteresowany. ( 1 ) Prawdopodobieństwo, że ty ciąg pasuje do jednego z poprzednich ciągów lub ( 2 ) Prawdopodobieństwo, że do czasu wybrania tego ciągu istnieje pewna duplikat w kolekcji narysowanych do tej pory ciągów. Odpowiedzi na te dwa pytania będą bardzo różne. :)

n

$n$

n

$n$

— kardynał

Być może rozważenie dwuznakowego alfabetu wyjaśni różnicę. Niech się litery i . Możemy zapytać: ( 1 ) Po co mamy co najmniej 99% szans, że ty ciąg będzie duplikatem poprzedniego ciągu? o o 8 ponieważ tylko w ten sposób, że nie jest w przypadku naszego sekwencja albo lub , który posiada całkowite prawdopodobieństwo . Albo pytamy ( 2 ) Za co mamy co najmniej 99% szans widząc jakiś duplikat? W tym przypadku ponieważ do tego czasu widzieliśmy trzy łańcuchy

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)}$

n

$n$

n = 3

$n = 3$

H

$H$ lub powtórzono co najmniej raz.

T

$T$

— kardynał

Odpowiedź Matta obsługuje ( 1 ), która zasadniczo odpowiada na pytanie, czy „mój” ciąg pasuje do cudzego. Ale jeśli martwisz się, że łańcuchy dwóch innych osób również mogą potencjalnie pasować, to jesteś zainteresowany ( 2 ). Sprowadza się to do tego, czy masz określony ciąg zainteresowań, z którym porównujesz wszystkie inne, czy też porównujesz ze sobą wszystkie ciągi. Nie jestem jednak pewien, czy to wyjaśnię. (Twój problem sprowadza się do jednego z dwóch wariantów słynnego tak zwanego „problemu urodzinowego”.)

— kardynał

Kardynał jak zwykle ma rację. Zakładałem, że masz jeden ciąg „docelowy”, dla którego generujesz listę domysłów. Jeśli zamiast tego generujesz ciągi losowo i chcesz poznać liczbę, którą można bezpiecznie wygenerować przed dopasowaniem dwóch ciągów, odpowiedź jest naprawdę inna. Zmienię swoją odpowiedź, aby rozwiązać ten przypadek, jeśli nie masz nic przeciwko.

— Matt Krause,

Mój poprzedni przykład nie wyjaśniłem całkowicie. Przepraszam za to. Myślałem o dwuliterowym alfabecie i rysowałem ciągi o długości jeden . W związku z tym, kiedy pisał , który stał na , , ..., , .

{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$

— kardynał

Całkowita liczba możliwości

1) Zamknij! Masz 62 opcje dla pierwszego znaku, 62 dla drugiego itd., Więc otrzymujesz , co jest absurdalnie dużą liczbą. $62 \cdot 62 \cdot 62 \cdot \cdots 62 = 62^{20}$

Zderzenie z ciągiem „docelowym”

2) Jak ustaliliśmy powyżej, istnieje potencjalnych ciągów. Chcesz wiedzieć, ile trzeba odgadnąć, aby mieć więcej niż 1 na 100 000 szans na odgadnięcie ciągu „docelowego”. Zasadniczo pytasz, co Aby to zrobić, musisz zaokrąglić x w górę (lub dodać jeden, jeśli są dokładnie równe), ale jak zobaczysz za sekundę, to tak naprawdę nie ma znaczenia. $62^{20}$

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

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

Za pomocą podstawowej algebry możemy zmienić to ustawienie jako

\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}$

Robienie matematyki, to około , więc nazwijmy to wszystko lub, bardziej zwięźle, cholernie dużo. $6.2^{20}$ $7 \cdot 10^{15}$ $7 \cdot 10^{30}$

Dlatego oczywiście długie hasła działają naprawdę dobrze :-) W przypadku prawdziwych haseł należy oczywiście martwić się ciągami o długości mniejszej lub równej dwadzieścia, co jeszcze bardziej zwiększa liczbę możliwości.

Duplikaty na liście

Teraz rozważmy inny scenariusz. Ciągi są generowane losowo i chcemy ustalić, ile można wygenerować, zanim będzie szansa 1: 100 000 na dopasowanie dwóch ciągów. Klasyczna wersja tego problemu nazywa się Problemem Urodzinowym (lub „Paradoksem”) i pyta, jakie jest prawdopodobieństwo, że dwie spośród n osób mają te same urodziny. Artykuł w Wikipedii [1] wygląda przyzwoicie i zawiera kilka tabel, które mogą okazać się przydatne. Niemniej jednak postaram się dać ci smak odpowiedzi tutaj.

Kilka rzeczy, o których należy pamiętać:

- Prawdopodobieństwo dopasowania i braku dopasowania musi 1, więc i odwrotnie. $P(\textrm{match}) = 1 - P(\textrm{no match})$

-W przypadku dwóch niezależnych zdarzeń i prawdopodobieństwo . $A$ $B$ $P(A \& B) = P(A) \cdot P(B)$

Aby uzyskać odpowiedź, zaczniemy od obliczenia prawdopodobieństwa nie znalezienia dopasowania dla określonej liczby ciągów . Kiedy już wiemy, jak to zrobić, możemy ustawić to równanie na wartość progową (1/100 000) i rozwiązać dla . Dla wygody nazwijmy liczbą możliwych ciągów znaków ( ). $k$ $k$ $N$ $62^{20}$

Będziemy „chodzić” po liście i obliczać prawdopodobieństwo, że ciąg ^ {th} pasuje do dowolnego ciągu „powyżej” na liście. Dla pierwszego ciągu mamy całkowitą liczbę ciągów i nic na liście, więc . W przypadku drugiego ciągu wciąż istnieje całkowitych możliwości, ale jedno z nich zostało „wykorzystane” przez pierwszy ciąg, więc prawdopodobieństwo dopasowania dla tego ciągu wynosi W przypadku trzeciego ciągu istnieją dwa sposoby dopasowania, a zatem sposoby, aby tego nie , więc i tak dalej. Zasadniczo prawdopodobieństwo $k$ $N$ $P_{k=1}(\textrm{no match}) = \frac{N}{N} = 1$ $N$ $P_{k=2}(\textrm{no match}) = \frac{N-1}{N}$ $N-2$ $P_{k=3}(\textrm{no match}) = \frac{N-2}{N}$ $k$ ciąg nie pasujący do pozostałych to

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

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

Chcemy jednak prawdopodobieństwa braku dopasowania między dowolnymi ciągami . Ponieważ wszystkie zdarzenia są niezależne (na pytanie), możemy po prostu pomnożyć te prawdopodobieństwa razem, tak jak to: Można to trochę uprościć: W pierwszym kroku po prostu mnoży się ułamki, w drugim stosuje się definicję silni ( ), aby zastąpić produkty $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$ z czymś nieco łatwiejszym do zarządzania, a ostatni krok zamienia się w dwumianowy współczynnik. To daje nam równanie prawdopodobieństwa braku dopasowania po wygenerowaniu ciągów. Teoretycznie możesz ustawić tę wartość na i rozwiązać dla . W praktyce trudno będzie znaleźć odpowiedź, ponieważ mnożymy / dzielimy przez ogromne liczby - silnia rosną bardzo szybko ( Ma więcej niż 150 cyfr).

k

$k$

\frac{1}{100, 000}

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

k

$k$

100!

$100!$

Istnieją jednak przybliżenia, zarówno do obliczania silni, jak i do całego problemu. Ten artykuł [2] sugeruje gdzie p jest prawdopodobieństwem braku dopasowania. Jego testy osiągnęły maksimum przy , ale nadal są dość dokładne. Po podłączeniu twoich liczb otrzymuję około .

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}$

Bibliografia

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

[2] Mathis, Frank H. (czerwiec 1991). „Ogólny problem urodzinowy”. Przegląd SIAM (Society for Industrial and Applied Mathematics) 33 (2): 265–270. JSTOR Link

— Matt Krause
źródło

+1 Niesamowite, biorąc pod uwagę, że moje słabe umiejętności matematyczne spowodowały, że zadałem pytanie, więc pozostawiam pytanie bez odpowiedzi na jeden dzień, ale wygląda mi dobrze i jest o wiele bardziej jasne od odpowiedzi, niż się spodziewałem - dziękuję!

— błąka się

Miło, że mogłem pomóc! Daj mi znać, jeśli coś jest niejasne. Dla kopnięć sprawdziłem liczby. Będziesz potrzebował 7044234255469980229683302646164 domysłów; tak jak powiedziałem - dużo!

— Matt Krause,

+1 @Matt Krause: +1 do komentarza poniżej odpowiedzi; Twoja odpowiedź i zaangażowanie w udzielenie najlepszej możliwej odpowiedzi jest wzorowe, godne odnotowania i dziękuję za całą ciężką pracę!

— oblewa