Dysponujemy probabilistycznym testem pierwszości liczb dającym następujące rezultaty:
- test zastosowany do liczby pierwszej zawsze daje odpowiedź: Nie wiadomo
- test zastosowany do liczby złożonej daje odpowiedź: Nie wiadomo z prawdopodobieństwem 1/2, a odpowiedź: Liczba jest złożona z prawdopodobieństwem 1/2.
Wielokrotne stosowanie testu daje niezależne wyniki.
Wylosowano liczbę ze zbioru w którym 99.9% to liczby złożone, a 0.1% to liczby pierwsze. Następnie poddano wylosowaną liczbę n-krotnemu testowi i otrzymano za każdym razem odpowiedź: Nie wiadomo.
Jakie jest prawdopodobieństwo, że wylosowana liczba jest liczbą pierwszą?
Ile razy należy wykonać test, aby w opisanej wyżej sytuacji móc stwierdzić, że wylosowana liczba jest pierwsza z prawdopodobieństwem większym od 999/1000?
Testowanie wylosowanej liczby
-
Yenneferzyca
- Użytkownik
- Posty: 46
- Rejestracja: 12 sie 2009, o 20:09
- Płeć: Kobieta
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Testowanie wylosowanej liczby
Niech:
\(\displaystyle{ B_1}\) - zdarzenie polegające na wylosowaniu liczby pierwszej,
\(\displaystyle{ B_2}\) - zdarzenie polegające na wylosowaniu liczby złożonej,
\(\displaystyle{ H}\) - zdarzenie polegające na tym, że w \(\displaystyle{ n}\) testach dla wylosowanej liczby wyjdzie "nie wiadomo".
Szukamy wartości \(\displaystyle{ P( B_1 |H)}\). Zgodnie ze wzorem Bayes'a jest:
\(\displaystyle{ P(B_1 |H) = \frac{ P(B_1) \cdot P(H | B_1)}{P(B_1) \cdot P(H | B_1)+P(B_2) \cdot P(H | B_2)}}\)
W naszym wypadku:
\(\displaystyle{ P(B_1) = 0.001 \\
P(B_2) = 0.999 \\
P(H | B_1) = 1 \\
P(H | B_2) = \frac{1}{2^n}}\)
Mamy więc:
\(\displaystyle{ P(B_1|H) = \frac{ 0.001 \cdot 1}{0.001 \cdot 1 + 0.999 \cdot \frac{1}{2^n}} = \frac{1}{1+ 999 \cdot \frac{1}{2^n}}}\)
W drugiej części zadania natomiast trzeba rozwiązać nierówność:
\(\displaystyle{ \frac{1}{1+ 999 \cdot \frac{1}{2^n}} \geq \frac{999}{1000}}\)
która jest równoważna:
\(\displaystyle{ 2^n \geq 999^2}\)
Pozostaje sprawdzić z kalkulatorem w ręku która potęga dwójki przekracza liczbę \(\displaystyle{ 998001}\) - mi wyszło \(\displaystyle{ n=20}\), czyli należy wykonać test dwadzieścia razy.
Q.
\(\displaystyle{ B_1}\) - zdarzenie polegające na wylosowaniu liczby pierwszej,
\(\displaystyle{ B_2}\) - zdarzenie polegające na wylosowaniu liczby złożonej,
\(\displaystyle{ H}\) - zdarzenie polegające na tym, że w \(\displaystyle{ n}\) testach dla wylosowanej liczby wyjdzie "nie wiadomo".
Szukamy wartości \(\displaystyle{ P( B_1 |H)}\). Zgodnie ze wzorem Bayes'a jest:
\(\displaystyle{ P(B_1 |H) = \frac{ P(B_1) \cdot P(H | B_1)}{P(B_1) \cdot P(H | B_1)+P(B_2) \cdot P(H | B_2)}}\)
W naszym wypadku:
\(\displaystyle{ P(B_1) = 0.001 \\
P(B_2) = 0.999 \\
P(H | B_1) = 1 \\
P(H | B_2) = \frac{1}{2^n}}\)
Mamy więc:
\(\displaystyle{ P(B_1|H) = \frac{ 0.001 \cdot 1}{0.001 \cdot 1 + 0.999 \cdot \frac{1}{2^n}} = \frac{1}{1+ 999 \cdot \frac{1}{2^n}}}\)
W drugiej części zadania natomiast trzeba rozwiązać nierówność:
\(\displaystyle{ \frac{1}{1+ 999 \cdot \frac{1}{2^n}} \geq \frac{999}{1000}}\)
która jest równoważna:
\(\displaystyle{ 2^n \geq 999^2}\)
Pozostaje sprawdzić z kalkulatorem w ręku która potęga dwójki przekracza liczbę \(\displaystyle{ 998001}\) - mi wyszło \(\displaystyle{ n=20}\), czyli należy wykonać test dwadzieścia razy.
Q.
-
Yenneferzyca
- Użytkownik
- Posty: 46
- Rejestracja: 12 sie 2009, o 20:09
- Płeć: Kobieta