Bin in einer Klausur mal über folgende Aufgabe gestolpert, bin nich so wirklich voran gekommen und hab dann die 4 punkte dies gab mal liegengelassen.. Mich intressiert die Lösung aber trotzdem.
Frage: n Studenten geben vor der Klausur ihre Handys ab, und erhalten sie danach in zufälliger reihenfolge wieder.. wieviele Studenten werden Durchschnittlich ihre eigenen Handys danach wieder haben. (Ich nehme an das is der Erwartungswert)
also ich hab mir gedacht p(handy zurück) = 1/n p(falsches Handy) = 1 - 1/n = (n-1)/n
hab dann bissl rumgerechnet nachgedacht und hab mir für den erwartungswert E(n) überlegt:
E(n) = [summe von i = 1 bis n] (i * (1/n)^i * ((n-1)/n)^(n-i))
Hab dann versucht das ganze über induktion zu beweisen und bin gefailt. Evtl. muss ich noch die reihenfolge berücksichtigen, Schulwarscheinlichkeitsrechnung ist aber leider schon ein wenig länger her..
Jemand ne gute idee? Mit beweis am besten aber nicht zwingend.
kivaas2011-03-04T01:53:27Z
Beste Antwort
Wir haben n Handys und n Studenten. Ob die Leute die Handys der Reihe nach oder alle gleichzeitig kriegen, ist für die Aufgabe wurscht.
Die Wahrscheinlichkeit, dass der erste Student sein eigenes Handy kriegt, ist tatsächlich 1/n, das hast du richtig.
Bei dem zweiten Studenten ist die Wahrscheinlichkeit dann: (1/(n-1) *(1 - 1/n)) - das ist die Wahrscheinlichkeit, dass sein Handy unter den verbleibenden war und er genau dieses bekommt, also ohne die Wahrscheinlichkeit, dass der erste Student seins gekriegt hat und es daher nicht mehr da ist.
Bei dem dritten Studenten ist die Wahrscheinlichkeit dann (1/(n-2) * (1 - 1/n - (1/n-1)*(1 - 1/n))) - das ist die Wahrscheinlichkeit, dass seins unter den noch vorhanden war und er es kriegt, minus die Wahrscheinlichkeit, dass einer der vorherigen Studenten seins hat.
Schreibst du diese alle nacheinander auf, erkennst du eine Folge. Und wie du schon richtig bemerkt hast: das riecht förmlich nach vollständiger Induktion.
Der Fall von n=1 ist trivial, der einzige Student kriegt auf jedenfall sein eigenes, nämlich das einzige Handy.
Der Fall von n=2 ist ebenfalls recht einfach: Die Wahrscheinlichkeit, dass der erste Student nachher sein eigenes Handy hat, ist 50%. Die Wahrscheinlichkeit, dass der zweite sein eigenes kriegt, ist Null, falls der erste Student das Handy des zweiten bekommen hat, und Eins, falls der erste Student sein eigenes Handy bekommen hat, also insgesamt doch wieder 50%.
Der Fall von n=3 liefert die Wahrscheinlichkeit von 1/3, dass der erste Student sein eigenes Handy kriegt. Kriegt er es, so haben der zweite und dritte Student jeweils eine 50%ige Chance, jeweils ihr eigenes zu bekommen. Kriegt dagegen der erste nicht sein eigenes hat der zweite zu 1/3 die Chance, das seins schon weg ist, zu 1/3 die Chance, dass es der dritte Student kriegt, und zu 1/3 die Chance, dass es noch da ist und er es kriegt.
usw. usf.
Insgesamt ergibt sich also unabhängig von der Reihenfolge immer eine Wahrscheinlichkeit von 1/n, dass jemand sein eigenes Handy bekommt.
Bei n Studenten ist die Anzahl derer, die ihr eigenes Teil bekommen, tatsächlich der Erwartungswert nach deiner Formel.
Eben kurz ausprobieren mit n=1: E(1) = 1*(1/1)^1 * (0/1)^0 = 1 => stimmt.
Nun ziehen wir den n-ten Summanden aus der Summe raus, erhalten also
Wenn also E(n-1) richtig ist, so ist auch E(n) richtig. Und da wir bereits wissen, dass für E(1) die Aussage stimmt, haben wir die ganze Sache per Induktion bewiesen.
Ich nehme mal an, dass Ihr etwas Ãhnliches vorher im Unterricht besprochen habt; tatsächlich ist das ein nicht ganz triviales Problem mit einer relativ einfachen Antwort: Der Erwartungswert ist (näherungsweise) 1.
Der Erwartungswert ist ja eine Summe über Zahlen folgender Form:
(*) k * (n über k) * D( n - k ) * 1/n!
für k=0,...,n. Dabei ist (n über k) der Binomialkoeffizient, und D( n - k) ist die sogenannte "Subfakultät" (oder auch die Anzahl fixpunktfreier Permutationen der Zahlen 1, ... , n-k).
Erklärung: Insgesamt gibt es n! Möglichkeiten, die Handys an die Studenten zu verteilen. (Weil es n! Möglichkeiten gibt, die n Handys anzuordnen.) Wenn dabei genau k Studenten ihr eigenes Handy bekommen, so gibt es dafür (n über k) * D( n - k ) Möglichkeiten; denn es gibt erst einmal (n über k) Möglichkeiten, die k Studenten auszuwählen, die ihr eigenes Handy erhalten, und alle anderen (n-k) Handys müssen so verteilt werden, dass kein Student sein eigenes Handy erhält. Das würde einer fixpunktfreien Permutation der übrigen (n-k) Handys entsprechen.
Der Ausdruck (*) ist also k * Wahrscheinlichkeit, dass genau k Studenten ihr eigenes Handy bekommen.
Jetzt ist näherungsweise D( n - k ) = (n - k)! / e
mit der Eulerschen Zahl e. Insgesamt lässt sich der Summand (*) dann näherungsweise zusammenkürzen auf
1/e * 1/(k-1)!.
Der Erwartungswert ist also (nach einem "Shift" der Summationsvariablen) ungefähr
1/e * Summe(k=0 bis n-1) 1/k!.
Die Summe auf der rechten Seite ist aber näherungsweise e. Also ist das Ergebnis näherungsweise 1.
Formuliert wird die Aufgabe übrigens häufiger in der Form "n Briefe werden zufällig auf n (adressierte) Briefumschläge verteilt" - falls Du nach mehr Hinweisen oder einer ausführlicheren Herleitung googeln möchtest.