Archive for the 'Kombinatorik' 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.

Warum gewinne ich nicht im Lotto?

Veröffentlicht am 21. August 2008 in Angewandtes, Kombinatorik and Mathematik. 13 Comments Tags: , , .

In diesem Artikel werden wir der Frage auf den Grund gehen. Dazu lernen wir zunächst die Begriffe der Fakultät und des Binomialkoeffizienten kennen, die beide aus der Kombinatorik stammen. Grob gesagt beschäftigt sich die Kombinatorik damit, Dinge abzuzählen. Oft geht es um Anordnungen von Dingen (populäres Beispiel: die möglichen Ziehungen der Lottozahlen bzw. -kugeln). Damit hängt die Kombinatorik teilweise eng mit der Wahrscheinlichkeitsrechnung zusammen, wie es z.B. in dem Artikel über PIN-Nummern zu erkennen ist.

Fakultät

Mithilfe der Fakultät kann man z.B. die Permutationen abzählen, die Anzahl der Vertauschungen einer bestimmen Anzahl von Objekten. Dazu zunächst ein Beispiel: Wir wollen die Anzahl aller Anordnungen berechnen, die es bei 5 Personen gibt, die auf 5 Stühle “verteilt” werden sollen. Gehen wir das Ganze einmal durch: Für die erste Person stehen uns alle 5 Stühle zur Verfügung. Die zweite Person müssen wir auf einen der verbleibenden 4 Stühle setzen. Es ergeben sich also {5} \cdot 4 = {20} Möglichkeiten für zwei Personen. Für jede weitere Person gibt es immer genau einen Stuhl weniger, auf dem die Person Platz nehmen kann, als die Person zuvor zur Auswahl hatte. Man erhält also {5} \cdot (5-1) \cdot (5-2) \cdot (5-3) \cdot (5-4) = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5 \cdot 4 \cdot 3 \cdot 2 = {120} Möglichkeiten. Genau dieses Produkt nennt man “Fakultät von 5″ und schreibt 5{!}$. Allgemein definieren wir die Fakultät von n, geschrieben als n! als n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 3 \cdot 2 \cdot 1 = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 3 \cdot 2 . Die Größe der Fakultät einer Zahl steigt sehr rasant an und schon bei 3-stelligen Zahlen benötigt ein (durchschnittlicher) Computer längere Zeit zur Berechnung. Dem erwähnten Problem der Anordnungen von Lottozahlen lässt sich so allerdings nicht auf die Schliche kommen, da nur 6 aus 49 Kugeln insgesamt ausgewählt werden und die Reihenfolge außerdem irrelevant ist.

Der Binomialkoeffizient

Der mitdenkende Leser erkennt vielleicht schon, wie dieses Problem zu umgehen ist. Zunächst überlegen wir uns, wie viele Möglichkeiten es gibt, 6 aus 49 Kugeln auszuwählen. Wir gehen so vor, wie oben bei Berechnung der Fakultät: Für die erste Kugel, die gezogen wird, gibt es 49 Möglichkeiten, für die zweite noch 48, für die dritte 47 und so weiter… Insgesamt ergibt sich {49} \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 = \frac{49!}{43!} = \frac {49!}{(49-6)!} Allerdings haben wir die Reihenfolge der Ziehungen der Kugeln noch nicht berücksichtigt, dass heißt jede mögliche Kombination kommt mehrmals vor. Genauer gesagt: In jeder möglichen Anordnung. Um die richtige Zahl der möglichen Ziehungen (ohne Relevanz der Reihenfolge) zu erhalten, müssen wir den Wert also noch durch die Anzahl der Anordnungen teilen. Das ist genau 6!, wie oben erläutert. Also ist die Zahl der möglichen Ziehungen beim Lotto genau \frac {49!}{(49-6)!6!} = \frac {49!}{(6!(49-6)!} Wie bereits oben angedeutet genau das der Binomialkoeffizient , sprich “49 über 6″. Allgemein ist \binom{n}{k} = \frac{n!}{(n-k)!k!} (gilt nur für natürliche Zahlen n, k was bei “alltäglichen” Abzählaufgaben jedoch meist erfüllt ist) Um die Wahrscheinlichkeit zu erhalten, mit der man ein Lottospiel gewinnt muss man nun noch den Kehrwert dieser Gesamtzahl der möglichen Ziehungen bilden, also den Anteil der eigenen ausgewählten Kombination an der Gesamtzahl berechnen: \frac {1}{\binom{49}{6}} = \frac{1}{\frac{49!}{43!\cdot6!}} = \frac{43!\cdot6!}{49!} = \frac{1}{13983816} \approx 0{,}00000715 \% , was sehr sehr gering ist.

Selbst wenn man 14 Millionen verschiedenene Lottoscheine abgeben würde befände sich darunter im Durchschnitt nur ein einziger mit “6 Richtigen”. Und darum gewinnen Sie nicht im Lotto. (Wer schon einmal im Lotto gewonnen hat und diese Aussage somit aus persönlicher Erfahrung widerlegen kann ist natürlich herzlich eingeladen, dies in einem Kommentar zu tun.)

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.