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).

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}} \ge \frac{1}{10^5}$$

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

$$\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}(\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(\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(\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) \cdots 1$$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$$\frac{1}{100,000}$$k$$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 - 2N\ln(p)}$$ $N=48,000$$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