Frage:
Wie groß ist die Wahrscheinlichkeit, p Primzahlen aus n Zufallszahlen auszuwählen?
Anubhav
2011-01-01 15:48:46 UTC
view on stackexchange narkive permalink


Die Wahrscheinlichkeit, dass eine Zahl zwischen 1 und x eine Primzahl ist, beträgt $ \ frac {1} {\ ln {x}} $ gemäß dem Primzahlsatz und auch die Gesamtzahl der Primzahlen zwischen $ 1 $ bis $ x $ ist $ \ frac {x} {\ ln {x}} $. Wenn wir jedoch $ n $ (32 Bit) Zufallszahlen auswählen, wie hoch ist die Wahrscheinlichkeit, dass $ p $ Primzahlen sind?

Oder einfach ausgedrückt

Wie hoch ist die Wahrscheinlichkeit, $ p $ Primzahlen aus $ n $ Zufallszahlen (32 Bit) auszuwählen.

TIA ..

Einer antworten:
#1
+16
onestop
2011-01-01 16:20:35 UTC
view on stackexchange narkive permalink

Es gibt 203.280.221 Primzahlen unter $ 2 ^ {32} $. ( Quelle). Die Wahrscheinlichkeit, dass eine zufällige 32-Bit-Zahl eine Primzahl ist, beträgt also $ 203.280.221 / 2 ^ {32} \ ca. 0.04733 $. Angenommen, Sie möchten eine Auswahl mit Ersetzung, dh dieselbe Zahl kann mehrmals ausgewählt werden, ergibt sich die Wahrscheinlichkeit, $ p $ Primzahlen aus $ n $ 32-Bit-Zufallszahlen auszuwählen, aus der Wahrscheinlichkeit Massenfunktion der Binomialverteilung, $$ \ frac {n!} {p! (np)!} 0.04733 ^ p (1-0.04733) ^ {np}. $$

Dies gilt auch für ersatzlose Stichproben, vorausgesetzt $ n << 2 ^ {32} $. Wenn wir beispielsweise $ n = 2 ^ {20} $ Zahlen ohne Ersatz abgetastet haben und festgestellt haben, dass sie alle keine Primzahlen sind, hat sich die Wahrscheinlichkeit einer Primzahl bei der nächsten Ziehung nur auf $ 0,047341 $ erhöht. Wenn sie alle Primzahlen sind, ist die Wahrscheinlichkeit auf $ 0,047097 $ gesunken. Die Wahrscheinlichkeit bei jeder Ziehung muss zwischen diesen beiden Grenzen liegen.


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 2.0-Lizenz, unter der er vertrieben wird.
Loading...