Wahrscheinlichkeit Fehlidentifizierung bei CRC32 Prüfsumme

13.09.2010, 11:24

gstueb

Wahrscheinlichkeit Fehlidentifizierung bei CRC32 Prüfsumme

Meine Frage:
Hallo,

wenn ich einen Topf mit 2^32 Zahlen habe und 10000 mal eine Zahl ziehe und wieder zurücklege, wie hoch ist dann wie Wahrscheinlichkeit, dass ich eine Zahl mehrmals ziehe?

Hintergrund: Jemand verwendet in einem Programm eine CRC32 Checksumme, um ca. 10000 Dateien voneinander zu unterscheiden. Ich bin mir ziemlich sicher, dass das keine gute Idee vom Programmautor war.

Danke & Gruß,
Gregor

Meine Ideen:
Das ganze ähnelt imho vom Ansatz her ja der bekannten Frage, wie hoch bei 23 Personen in einem Raum die Wahrscheinlichkeit ist, dass 2 am gleichen Tag Geburtstag haben. Nur das es in meinem Fall 2^32 Tage und 10000 Personen sind.

13.09.2010, 12:10

Zellerli

Auf diesen Beitrag antworten »

Ja, ist ein ähnliches Problem.

Beides geht mit dem Kugel-Fächer-Modell.

Idee beim Geburtstagsparadoxon:
365 Fächer und ich lege in jedes (zufällig) eine von 23 Kugeln. Es soll keine Doppelbelegung geben.

Wie viele Fächer hast du und wie viele Kugeln?

Und dann gilt Laplace:
$\begin{eqnarray*} P=\frac{\text{Anzahl günstiger Ereignisse}}{\text{Anzahl aller möglichen Ereignisse}} \end{eqnarray*}$

Alle möglichen sind recht einfach (für jede Kugel gibt es die volle Anzahl an Fächern).
Alle günstigen erhält man, indem man sich für jede Kugel einzeln fragt: Wieviele Möglichkeiten gibt es jetzt noch für die nächste?

13.09.2010, 15:51

gstueb

Auf diesen Beitrag antworten »

Zitat:

Beides geht mit dem Kugel-Fächer-Modell.

Danke... Ich habe ja schon ein wenig rumprobiert, und mit Hilfe der Wikipedia-Seite Geburtstagsparadoxon komme ich auf folgenden Ansatz:

$\begin{eqnarray*} \frac{(2^{32} )!}{(2^{32}-10000)!*2^{32}} \end{eqnarray*}$

Ist das richtig? Könnte mir das jemand für mein konkretes Problem mit 2^32 Fächern und 10000 Kugeln ausrechnen?

[edit] ... nein, ich sehe gerade selbst, dass dies nicht richtig ist. Ich brauch' doch noch weitere Hilfe ...

13.09.2010, 17:06

Zellerli

Auf diesen Beitrag antworten »

Ist aber fast richtig. Momentan ist diese "Wahrscheinlichkeit" größer 1.

Aber du hast schon richtig angesetzt:
günstige: $\begin{eqnarray*} \frac{2^{32}!}{(2^{32}-10000)!} \end{eqnarray*}$
Überlegung: Für die erste Kugel gibt es $\begin{eqnarray*} 2^{32} \end{eqnarray*}$ Möglichkeiten.
Für die zweite dann nur noch $\begin{eqnarray*} 2^{32}-1 \end{eqnarray*}$ , weil sie ja nicht mehr im selben Fach landen darf.
Für die dritte dann nur noch $\begin{eqnarray*} 2^{32}-2 \end{eqnarray*}$ , usw.
Für die 10 000ste dann nur noch $\begin{eqnarray*} 2^{32}-9999 \end{eqnarray*}$ Möglichkeiten. Das ist dann die Fakultät, die beim 10 000. Faktor aufhört (also kürzt man alle weiteren Faktoren per Division weg). Das ist dann der o.g. Term.

Absolut richtig also.

Aber:
alle möglichen: $\begin{eqnarray*} 2^{32} \end{eqnarray*}$ was fehlt da noch?
Folge ruhig der obigen Überlegung für die "günstigen", nur ist jetzt eben für jede Kugel alles erlaubt...
Ich denke mal das hast du nur übersehen, weil da bereits jetzt schon eine Potenz steht für die Anzahl der Fächer.

13.09.2010, 23:09

gstueb

Auf diesen Beitrag antworten »

Zitat:

Original von Zellerli
Ist aber fast richtig. Momentan ist diese "Wahrscheinlichkeit" größer 1.

Dann würde ich sagen, dass der Faktur n=10000 noch fehlt:

$\begin{eqnarray*} \frac{2^{32}! }{(2^{32}-10000)!*2^{32*n} } \end{eqnarray*}$

oder? Kannst Du mir, falls das stimmt, noch einen Tipp geben, wie ich das zusammenkürzen bzw. ausrechnen kann?

Ich meine, letztendlich würde dann ja irgendwie so etwas stehenbleiben:

$\begin{eqnarray*} \frac{2^{32} * (2^{32}-1) * (2^{32}-2) .. * (2^{32}-n+1)}{2^{32} * 2^{32} * 2^{32}.. } \end{eqnarray*}$

Wie rechnet man das denn vollends aus?

14.09.2010, 01:24

Zellerli

Auf diesen Beitrag antworten »

Mehr ist da nicht zu kürzen.
Ist subjektiv ob es "schöner" ist, wenn du die erste $\begin{eqnarray*} 2^{32} \end{eqnarray*}$ wegkürzt.
Oder ob die Formulierung als Produkt, statt der Formulierung als Bruch aus Fakultäten schöner ist.
Das würde übrigens so aussehen:

$\begin{eqnarray*} \prod_{i=1}^{1000} \frac{2^{32}-i+1}{2^{32}} \end{eqnarray*}$

Ausrechnen tut man das mit dem Rechner Augenzwinkern

Falls du Näherungen brauchst um Rechenkapazität zu sparen gilt z.B. die Stirling Formel.

14.09.2010, 01:55

gstueb

Auf diesen Beitrag antworten »

Zitat:

Original von Zellerli
Mehr ist da nicht zu kürzen.
Ausrechnen tut man das mit dem Rechner Augenzwinkern

Ich hab' auf meinen PC keine Software installiert, die mit diesen Zahlen zurechtkommt. Falls Du eine solche installiert hast: Könntest Du mir das Ergebnis nennen?

Im konkreten Fall geht es mir ja nur darum, zu belegen, dass es keine gute Idee ist, 10000 Dateien Anhand einer CRC32 Checksumme zu identifizieren. Ich möchte mich jetzt ungern auch noch in die Funktionsweise der Stirling-Formel einlesen. Augenzwinkern

14.09.2010, 02:32

Zellerli

Auf diesen Beitrag antworten »

Wolfram alpha spuckt was aus.

Du musst nur aufpassen: Das Ergebnis ist die Wahrscheinlichkeit dafür, dass keine Doppelbelegung auftritt. Wenn deine Vermutung stimmt, müsste diese Wahrscheinlichkeit gering sein.

14.09.2010, 10:22

gstueb

Auf diesen Beitrag antworten »

Zitat:

Original von Zellerli
Wolfram alpha spuckt was aus.

Du musst nur aufpassen: Das Ergebnis ist die Wahrscheinlichkeit dafür, dass keine Doppelbelegung auftritt. Wenn deine Vermutung stimmt, müsste diese Wahrscheinlichkeit gering sein.

Hmm, dann beträgt die Wahrscheinlichkeit für eine Fehl-Identifizierung tatsächlich nur ca. 1,2 % ... das hätte ich höher eingeschätzt. Ich werde noch ein kleines Testprogramm schreiben um das Ergebnis zu verifizieren.

Vielen Dank für die Hilfe.

Gruß,
Gregor

Neue Frage »

Antworten »

Wahrscheinlichkeit Fehlidentifizierung bei CRC32 Prüfsumme

Verwandte Themen