Archive for the 'Wahrscheinlichkeit' Category

Das Geburtstagsparadoxon

Veröffentlicht am 25. Mai 2009 in Angewandtes, Kombinatorik, Mathematik, Paradoxa, Probleme and Wahrscheinlichkeit. 2 Comments Tags: , , , , , .

Geburtstagstorte
Wieder einmal ein Artikel über paradox Erscheinendes aus der (kombinatorischen) Wahrscheinlichkeitsrechnung: Das sogenannte “Geburtstagsparadoxon”.

Beim Geburtstagsparadoxon geht es um die – erstaunlich hohe – Wahrscheinlichkeit, dass bei einer vorher festgelegten (zufälligen) Menge von mehreren Personen mindestens zwei von ihnen am selben Tag ihren Geburtstag feiern.

Um die Fehleinschätzung zu demonstrieren: Was glauben Sie, ab welcher Personenzahl diese Wahrscheinlichkeit 50% übersteigt? 100 Personen? 366? Oder gar über 500? (*)

Falsch! Bereits bei 23 Personen liegt die Wahrscheinlichkeit für einen Doppelgeburtstag bei 50,73%! Das glauben Sie nicht? Nun gut, gehen wir der Sache auf den Grund.

Recht einfach ist es, wenn wir einfach alle Personen der Reihe nach durchgehen und jedes Mal aufs Neue die Wahrscheinlichkeit dafür berechnen, dass unter den bisher betrachteten Personen ein Doppelgeburtstag liegt. Anschließend verallgemeinern wir diese Vorgehensweise und erhalten eine Formel für die Berechnung der Wahrscheinlichkeit bei einer gegebenen Zahl n von Personen. Also gut:

Eine Person: Es kann kein Doppelgeburtstag auftreten, es ist egal, wann die erste Person ihren Geburtstag feiert.

Zwei Personen: Nur zu \frac{1}{365} tritt ein Doppelgeburtstag auf, nämlich genau dann, wenn die 2. Person NICHT an einem der bereits “vergebenen” Tage Geburtstag hat, es bleiben also 1-(\frac{364}{365}) = \frac{1}{365} \approx 0,27\%

Drei Personen: Wie schon bei Person Nummer zwei erläutert tritt KEIN Doppelgeburtstag genau dann auf, wenn Person drei ihren Geburtstag weder mit der ersten, noch mit der zweiten Person teilt. Das ist in (\frac{364}{365} \cdot \frac{363}{365}) = 99,18\% der Fälle so. Übrig bleiben 1-(\frac{364}{365} \cdot \frac{363}{365}) = 0,82\% FÜR einen Doppelgeburtstag. Noch immer sehr niedrig.

Vier Personen: Führen wir das gleiche Muster fort: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365}) \approx 1,64\%. Eine Verdopplung immerhin.

Fünf Personen: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdot \frac{361}{365}) \approx 2,71\%. Allzu rasant scheint der Wert ja nicht zu steigen.

Sechs Personen: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \frac{362}{365} \cdot \frac{361}{365} \cdot \frac{360}{365}) \approx 4,05\%.
… Um es nicht allzu langwierig zu machen springen wir nun direkt zu 20 Personen:

20 Personen: 1-(\frac{364}{365} \cdot \frac{363}{365} \cdot \ldots \cdot \frac{346}{365}) \approx 41,14\%

21 Personen: 1-(\frac{364}{365} \cdot \ldots \cdot \frac{345}{365}) \approx 44,37\%

22 Personen: 1-(\frac{364}{365} \cdot \ldots \cdot \frac{344}{365}) \approx 47,57\%

23 Personen: 1-(\frac{364}{365} \cdot \ldots \cdot \frac{344}{365}) \approx 50,73\%

Erstaunlich. Mal wieder.

Für interessierte sei auch noch die Formel genannt, mit der sich die Wahrscheinlichkeit für einen Doppelgeburtstag unter n Personen berechnen lässt:

P(n) = 1 - \frac{365!}{(365 - n)! \cdot 365^n}

Die Werte sind allerdings nur theoretisch – in der Praxis ist die Wahrscheinlichkeit sogar noch etwas größer.
Das liegt vor allem daran, dass die Geburtstage selten gleichmäßig über das Jahr verteilt sind.So gibt es eine deutliche Tendenz für die Sommermonate.

Fußnoten:

* Bereits bei 135 Personen rundet Sage auf 100%, bei einer Genauigkeit von zehn Nachkommastellen.

PIN-Nummern-Paradoxa

Veröffentlicht am 18. Juni 2008 in Angewandtes, Kombinatorik, Mathematik and Wahrscheinlichkeit. 11 Comments Tags: , , , , .

In diesem Eintrag möchte ich ein Beispiel für eine Anwendung eines mathematischen Beweises auf das “wirkliche Leben” zeigen.

Es geht um einige Überlegungen zu der Sicherheit von PIN-Nummern [Wikipedia]. Auf unserem Weg, diese Sicherheitsfragen zu klären werden wir auch noch zufällig eine interessante Beobachtung machen. Der Artikel ist vorerst nur auf die PIN-Nummern von EC-Karten bezogen, alle Gedanken und Berechnungen sollten jedoch genauso für andere Systeme gelten und/oder übertragbar sein.

Die erste Frage, die sich stellt, ist die nach der Wahrscheinlichkeit, eine vierstellige PIN-Nummer zu erraten. Dazu müssen wir zunächst die Anzahl der möglichen verschiedenen vierstelligen PIN-Nummern berechnen. Für die erste Ziffer steht eine Ziffer von 1 bis 9 zur Verfügung, den drei weiteren Ziffern außerdem eine 0. Es gibt also {9} \cdot 10 \cdot 10 \cdot 10 = 9000 verschiedene vierstellige PIN-Nummern. Das scheint sehr wenig zu sein.

Die Wahrscheinlichkeit, eine bestimmte PIN-Nummer richtig zu erraten beträgt aber demnach P = \frac{1}{9000} = 0{,}011\%, was ziemlich gering ist. Die richtige PIN-Nummer nach drei Versuchen zu raten, die in der Regel erlaubt sind, bis die Karte gesperrt wird, beträgt die Wahrscheinlichkeit mit \frac{1}{9000} + \frac{1}{8999} + \frac{1}{8998} \approx 0,033337 nur wenig mehr als 0,033%, ist also immer noch sehr gering. Unter 1000 EC-Karten, deren PIN-Nummern man durch Raten herauszufinden, sind im Durchschnitt also nur etwa 3 richtig. Sorge oder gar Angst um die Sicherheit ist also, trotz der “nur” 9000 verschiedenen Möglichkeiten, fehl am Platze.

Aber halt! Es gibt nur 9000 verschiedene PIN-Nummern? Wenn wir das Schubfachprinzip zu Rate ziehen, stellen wir fest, dass es mit Sicherheit zwei Menschen geben muss, deren PIN-Nummern identisch sind. Und das nicht nur in Deutschland oder einem bestimmten Bundesland; in nahezu jeder Stadt gibt es wohl mindestens ein Paar identischer PIN-Nummern. Doppelte PIN-Nummern kommen also häufiger vor, als man intuitiv vermuten würde. Und trotzdem kann man sich darauf verlassen, dass das PIN-Verfahren ein sicheres ist. Verblüffend!

Überrascht war ich auch, als ich feststellen musste, dass die PIN meiner EC-Karte und die vorgegebene PIN für meine neue Handy-SIM-Karte sich bloß an einer einzigen Stelle um eine einzige Ziffer unterschieden.

Wie groß war schon die Wahrscheinlichkeit dafür? Um den Blog-Eintrag nicht unnötig und abschreckend groß erscheinen zu lassen führe ich die Berechnungen hier nicht weiter aus. Das Endergebnis möchte ich jedoch nicht vorenthalten, die a-priori-Wahrscheinlichkeit für dieses Ereignis betrug etwa 0,003%, das entspricht einer Chance von etwa 1 zu 868. Hätten Sie unter Berücksichtigung der vorherigen Erkenntnis der Häufigkeit von doppelten PIN-Nummern ein solches Ergebnis erwartet?

Wir sehen, die Wahrscheinlichkeitsrechnung legt einige Dinge zu Tage, die unserer Intuition völlig zuwiderlaufen. Faszinierend, wie ich finde.

Wer noch weitere Beispiele für solche Täuschungen kennt ist herzlich dazu eingeladen, diese in einem Kommentar zu ergänzen.

Auflösung des Ziegenproblems

Veröffentlicht am 31. Mai 2008 in Mathematik, Probleme and Wahrscheinlichkeit. 0 Comments Tags: , , , , , , , .

Auflösung des ZiegenproblemsHier also die Auflösung des Ziegenproblems für diejenigen, die es nicht länger erwarten können oder möchten.

Wer den Artikel über das Ziegenproblem noch nicht gelesen hat, dem sei dazu geraten, es vor der Lektüre dieses Artikels zu tun (http://blog.florian-severin.de/2008/05/das-ziegenproblem).

Wie dort erwähnt sind die Wahrscheinlichkeiten, den Hauptpreis zu gewinnen, gefragt. Mit welcher Entscheidung hat man dann die besseren Chancen? Um das herauszufinden, beginnen wir mit der Ausgangssituation, es soll also eine von drei Türen gewählt werden. Nach dieser Auswahl können zwei verschiedene Fälle aufgetreten sein: Entweder, die ausgewählte Tür ist die, hinter der der Hauptgewinn wartet (Fall A). Im anderen Fall wurde eine der beiden Türen gewählt, hinter denen eine Ziege verborgen ist (Fall B).

Die Wahrscheinlichkeit für Fall A liegt offensichtlich bei \frac{1}{3}, die für Fall B bei \frac{2}{3}. Man schreibt dies als P(A) = \frac{1}{3} (sprich: “P von A ist gleich ein Drittel”) bzw. P(B) = \frac{2}{3} (sprich: “P von B ist gleich zwei Drittel”).

Im nächsten Schritt wählt der Moderator eine der beiden nicht vom Spieler gewählten Türen aus, hinter der sich eine Ziege verbarg. Nun steht der Spieler vor der Wahl, ob er wechseln möchte oder nicht.

Gehen wir zunächst davon aus, der Spieler verfolgt die Strategie, niemals zu wechseln. Dann beträgt die Wahrscheinlichkeit zu gewinnen genau der Wahrscheinlichkeit dafür, dass Fall A eintritt also \frac{1}{3}. In Fall B, also mit einer Wahrscheinlichkeit von \frac{2}{3} verliert der Spieler.

Wenn der Spieler sich von vornherein darauf festlegt, immer zu wechseln, so beträgt die Wahrsceheinlichkeit für einen Gewinn genau der Wahrscheinlichkeit für Fall B, also \frac{2}{3}. In Fall A, also mit einer Wahrscheinlichkeit von \frac{1}{3} verliert er.

Eine andere denkbare Strategie wäre z. B., eine Münze zu werfen und damit den Zufall entscheiden lassen, ob man wechselt oder nicht. Dann beträgt die Wahrscheinlichkeit für einen Gewinn \frac{2}{3} \cdot \frac{1}{2} \ {(f\ddot ur\ Fall\ A)} + \frac{2}{3} \cdot \frac{1}{2}\ {(f\ddot ur\ Fall\ B)} = \frac{3}{6}= \frac{1}{2}. Die Chance auf einen Gewinn ist also immernoch höher, wenn man immer wechselt.

Weitere Überlegungen und alternative Beweise (es gibt einige, der hier erläuterte ist einer der einfacheren) finden ihren Platz gerne in den Kommentaren.

Das Ziegenproblem

Veröffentlicht am 31. Mai 2008 in Mathematik, Probleme and Wahrscheinlichkeit. 0 Comments Tags: , , , .

ZiegenproblemDas Ziegenproblem [Wikipedia] ist ein bekanntes Problem der Wahrscheinlichkeitsrechnung.

Man stelle sich vor, man befindet sich in einer Quiz-Show, bei der es darum geht, aus drei Türen diejenige auszuwählen, hinter der der Hauptgewinn (z. B. ein Auto) wartet. Hinter den anderen beiden Türen befindet sich jeweils eine Ziege.

Der Spieler wählt nun zunächst eine der drei Türen aus. Darauf hin öffnet der Moderator eine der beiden anderen Türen, hinter der sich eine Ziege befindet. Übrig bleibt also die eine Tür die den Hauptgewinn verbirgt sowie die Tür, hinter der die andere Ziege wartet. Der Spieler wird nun vor die Wahl gestellt: Entweder er bleibt bei der zuvor ausgewählten Tür, oder er wechselt.

Welche Entscheidung verspricht nun die größere Chance, den Hauptpreis zu gewinnen? Intuitiv ist die mehrheitliche Meinung, beide Wahrscheinlichkeiten seien gleich groß. Das stimmt jedoch nicht! Da ich mit diesem Blog aber auch zum Nachdenken über die Mathematik und ihre Probleme anregen und aufrufen möchte, gibt es in diesem Beitrag keine Erklärung dafür. Der interessierte Leser möge sich also zunächst selbst Gedanken darüber machen, warum das so ist, und bei welcher Entscheidung man bessere Chancen hat.

Wer nicht darüber nachdenken möchte, oder zu keinem Ergebnis gekommen ist, dem sei auch die Möglichkeit gegeben, sich die Auflösung des Ziegenproblems anzuschauen.