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

Das Königsberger Brückenproblem

Veröffentlicht am 8. November 2008 in Angewandtes, Graphentheorie, Mathematik, Probleme and Rätsel. 2 Comments Tags: , , , , , .

Rücken Sie Ihre Sitzgelegenheit zurecht, machen Sie es sich bequem, seien Sie bereit für eine virtuelle Zeitreise; wir begeben uns zurück ins 18. Jahrhundert.

Wir befinden uns jetzt im damaligen Königsberg (heute Kaliningrad). Nach einem gemütlichen Spaziergang durch die Stadt kommen wir schließlich an den Pregel. Wir überqueren eine der sieben Brücken und stehen inmitten der sogenannten Kneiphof-Insel.

Ein älterer Mann kommt auf uns zu und bietet eine Wette: “Schaffen Sie es, jede der sieben Brücken genau einmal zu passieren und am Ende wieder hier an ihrem Ausgangspunkt zu landen? Ich biete einen Reichstaler.” (Anm.: Kaufkraft im 18.Jh etwa 15€)

Lageskizze der Königsberger Brücken

Lageskizze der Königsberger Brücken

Sollten Sie diese Wette annehmen?

Natürlich nicht! Es ist unmöglich, einen solchen Weg zu finden. Doch warum? Und wie lässt sich das beweisen? (Diese beiden Fragen hängen oft eng miteinander zusammen.)

Setzen wir zur Auflösug unseren Stadtrundgang fort. Wir kommen zu einem kleinen Haus, irgendwo in Königsberg. Es ist das Haus Leonhard Eulers, einer der größten Mathematiker der Geschichte. Euler war es, der unsere Fragen im Jahre 1736 beantworten konnte.

Dazu tat er etwas für die Mathematik seiner Zeit noch recht ungewöhnliches: Er ließ die genauen Details des Brückenplans weg und untersuchte nur ihre Struktur, die Beziehung der Wege untereinander. Die genauen Maße der Wege waren uninteressant.

So wandelte Euler das praktische Problem um in eines der Graphentheorie, dessen Anfang heute bei diesen Entdeckungen Eulers gesehen wird. Er verwandte neue Begriffe, die “Knoten” und die “Kanten”, die zusammen einen Graphen bilden.

Graph der Königsberger Brücken

Die Knoten sind dabei die vier zu erreichenden Teile der Stadt; die Kanten als Verbindungen zwischen den Knoten stellen unsere Brücken dar.

Gesucht ist nun ein Weg, der bei demselben Knoten beginnt und endet und dabei jede Kante genau einmal benutzt.

Wir sehen schnell, dass an jedem der Knoten eine ungerade Anzahl von Kanten liegt (man spricht von einem ungeraden Grad der Knoten). Ein Knoten, der zugleich Start- und Endknoten unserer Reise ist, müsste allerdings einen geraden Grad besitzen, ansonsten muss mindestens eine Brücke zweimal überquert werden. Das ist uns jedoch nicht erlaubt, wir können also keinen solchen Weg finden.

(Für eine sehr gut gestaltete nähere Erläuterung des Themas siehe http://www.matheprisma.uni-wuppertal.de/Module/Koenigsb/)

Paradoxes Fahrrad-Rätsel

Veröffentlicht am 3. Oktober 2008 in Angewandtes, Mathematik, Probleme and Rätsel. 0 Comments Tags: , , , .

Fahrrad

Stellen Sie sich vor, Sie nehmen an einem Fahrrad-Rennen teil. Die Strecke besteht aus zwei Runden irrelevanter Länge, eine davon haben Sie bereits absolviert. Bisher beträgt Ihre Durchschnittsgeschwindigkeit 20 km/h, Sie hatten sich aber vorgenommen, nach dem gesamten Rennen mit einer durchschnittlichen Geschwindigkeit von 40km/h ins Ziel zu gelangen.

Wie schnell müssen Sie also nun in der zweiten Runde fahren, um diese Wunsch-Gesamtgeschwindigkeit zu erreichen?

Plausibel erscheinen zunächst 60km/h.

Doch ganz so einfach ist es natürlich nicht. In Wahrheit können Sie das Rennen gar nicht mehr mit der gewünschten Durchschnittsgeschwindigkeit von 40km/h beenden! Egal, wie kräftig Sie in die Pedale treten, eine Gesamt-Durchschnittsgeschwindigkeit von 40km/h zu erreichen ist unmöglich!

Warum? Nunja, für die erste Hälfte der Strecke benötigten Sie 20km/h. Wenn wir die Streckenlänge mit s bezeichnen gilt also für die benötigte Zeit t = \frac{1}{2}s : 20 \text{km/h} = \frac{1}{40}\text{km/h} \cdot s. Um das Ziel mit einer Geschwindigkeit von 40km/h zu erreichen, müssten Sie für die beiden Runden zusammen jedoch ebenfalls t = s : 40\text{km/h} = \frac{1}{40}\text{km/h} \cdot s benötigen; die zweite Runde müssten Sie also in 0 Sekunden absolvieren, was nicht nur praktisch unmöglich ist!

Genau so verhält es sich natürlich, wenn Sie bereits 99 von 100 Runden mit einer Geschwindigkeit von 99km/h gefahren sind und 100km/h erreichen möchten.

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.