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

9

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 ( )?105

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

błędy
źródło
2
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. :)nn
kardynał
1
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ńcuchyHTnnnTTTTHHHHHT2(n1)nn=3Hlub powtórzono co najmniej raz. T
kardynał
1
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ł
1
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,
1
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}HHHHTs1=Hs2=Hsn1=Hsn=T
kardynał

Odpowiedzi:

11

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ą.62626262=6220

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

x62201105

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

105x6220105x(6.210)20105x6.2201020x6.2201015

Robienie matematyki, to około , więc nazwijmy to wszystko lub, bardziej zwięźle, cholernie dużo.6.2207101571030

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(match)=1P(no match)

-W przypadku dwóch niezależnych zdarzeń i prawdopodobieństwo .ABP(A&B)=P(A)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 ( ).kkN6220

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ństwokNPk=1(no match)=NN=1NPk=2(no match)=N1NN2Pk=3(no match)=N2Nk ciąg nie pasujący do pozostałych to

Pk(no match)=Nk+1N

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ć produktyk

P(No Matches)=NNN1NN2NNk+1N
P(No Matches)=N(N1)(N2)(Nk+1)NkP(No Matches)=N!Nk(Nk)!P(No Matches)=k!(Nk)Nk
k!=(k)(k1)(k2)1Nk+1N 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).k1100,000k100!

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+0.252Nln(p)
N=48,0003.71015

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ę
1
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