Geburtstagproblem < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Betrachten wir das Geburtstagsproblem für Marsbewohner, mit einem Marsjahr von 686 Tagen. Ein Marsianer gibt eine Party. Wieviele Leute muss er mindestens einlade, damit es sich für ihn lohn, darauf zu wetten, dass keine zwei am selben Tag Geburtstag haben?
Wir haben:
r= 686
n=#Leute (gesucht)
A:= Keine zwei haben am gleichen Tag Geburtstag
P(A) [mm] \ge [/mm] 1/2 (damit es sich lohnt zu wetten)
Jetzt kommt meine Frage:
Warum ist
P(A) = [mm] exp(-n^2/2r)
[/mm]
Kann mir bitte jemand erklären, wie das zustande kommt?
Danke schon mal
|
|
| |
|
> Betrachten wir das Geburtstagsproblem für Marsbewohner, mit
> einem Marsjahr von 686 Tagen.
Zuerst zu den astronomischen Daten:
Das Marsjahr dauert 669 Marstage, also 687 Erdtage
(Marsbewohner würden ihren Kalender kaum nach Erdtagen
einrichten...  )
> Ein Marsianer gibt eine
> Party. Wieviele Leute muss er mindestens einlade, damit es
> sich für ihn lohn, darauf zu wetten, dass keine zwei am
> selben Tag Geburtstag haben?
Die Frage ist wohl verkehrt gestellt. Sie sollte entweder:
"Wieviele Leute muss er mindestens einladen, damit es
sich für ihn lohnt, darauf zu wetten, dass mindestens zwei am
selben Tag Geburtstag haben?"
oder aber:
"Wieviele Leute darf er höchstens einladen, damit es
sich für ihn lohnt, darauf zu wetten, dass keine zwei am
selben Tag Geburtstag haben?"
lauten.
> Wir haben:
> r= 686
> n=#Leute (gesucht)
>
> A:= Keine zwei haben am gleichen Tag Geburtstag
>
> P(A) [mm]\ge[/mm] 1/2 (damit es sich lohnt zu wetten)
>
> Jetzt kommt meine Frage:
> Warum ist
> P(A) = [mm]exp(-n^2/2r)[/mm]
>
> Kann mir bitte jemand erklären, wie das zustande kommt?
Die genaue Berechnung der Wahrscheinlichkeit, dass unter
n Personen keine zwei mit dem gleichen Geburtstag sind,
ist:
[mm] P(A)=\bruch{r}{r}*\bruch{r-1}{r}*\bruch{r-2}{r}*.......\bruch{r-n+1}{r}=\bruch{r!}{r^n*(r-n)!}
[/mm]
Um die Fakultäten loszuwerden, welche die Auflösung der
Gleichung nach n praktisch verunmöglichen, kann man
zur Stirling-Formel greifen, welche sagt:
[mm] n!\approx\wurzel{2*\pi*n}*\left(\bruch{n}{e}\right)^n
[/mm]
Wenn ich diese Näherung verwende, komme ich allerdings
zu einem wesentlich anderen Ergebnis als jenes, das du
angibst.
LG al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:25 Do 07.08.2008 | | Autor: | Fellfrosch |
Also, danke erstmal.
Die Frage ist wortwörtlich:
Wieviele muss er einladen (dass mind. war zuviel), damit es sich für ihn lohnt, darauf zu wetten, dass
a) keine zwei am selben Tag Geburtstag haben
b) mindestens einer am selben Tag Geburtstag hat wie er.
Aber Du hast die Frage ja richtig verstanden.
Die Wahrscheinlichkeit stammt aus meinen Unterlagen einer Uni-Vorlesung aber ich habe leider nur Bruchstücke dieser Aufgabe aufgeschrieben, so dass ich nich mehr weiß, wie man darauf kommt.
Stirling sagt mir was. Ich denke das ist es auch.
Was hast Du denn für ein Ergebnis (WS)?
Am Ende kommt bei mir raus, dass er max. 29 Leute einladen darf.
Danke
|
|
|
| |
|
Nach Einsetzen der Stirling-Formel für die Fakultäten und einigen
Vereinfachungen habe ich erhalten:
[mm]\ P(A)\approx e^{-n}*\left(\bruch{r}{r-n}\right)^{r-n+\bruch{1}{2}}[/mm]
Wie man davon ausgehend zum Ausdruck [mm]\ e^\big{{-\bruch{n^2}{2r}}}[/mm] kommen
kann (der natürlich nur eine weitere Approximation darstellt !)
sehe ich im Moment nicht. Ich habe nur einen numerischen Vergleich
angestellt und festgestellt, dass man damit (wenigstens im haupt-
sächlich interessierenden Bereich) nicht weit daneben liegt...
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:25 Do 07.08.2008 | | Autor: | abakus |
> Nach Einsetzen der Stirling-Formel für die Fakultäten und
> einigen
> Vereinfachungen habe ich erhalten:
>
> [mm]\ P(A)\approx e^{-n}*\left(\bruch{r}{r-n}\right)^{r-n+\bruch{1}{2}}[/mm]
>
> Wie man davon ausgehend zum Ausdruck [mm]\ e^\big{{-\bruch{n^2}{2r}}}[/mm]
> kommen
> kann (der natürlich nur eine weitere Approximation
> darstellt !)
> sehe ich im Moment nicht.
Hallo,
es gilt
[mm] \left(\bruch{r}{r-n}\right)^{r-n+\bruch{1}{2}}=\left(1+\bruch{n}{r-n}\right)^{r-n+\bruch{1}{2}}=\left(1+\bruch{n}{r-n}\right)^{\bruch{r-n}{n}*n+\bruch{1}{2}}
[/mm]
Wenn r-n wesentlich größer als n ist, nähert sich der Teilausdruck [mm] \left(1+\bruch{n}{r-n}\right)^{\bruch{r-n}{n}} [/mm] dem Wert e an.
Gruß Abakus
> Ich habe nur einen numerischen
> Vergleich
> angestellt und festgestellt, dass man damit (wenigstens im
> haupt-
> sächlich interessierenden Bereich) nicht weit daneben
> liegt...
>
> LG
|
|
|
| |
|
Hallo abakus,
genau diese Überlegungen hatte ich mir vorher auch schon
gemacht - aber ich sehe nicht, wie sie von dem Term, den
wir schon hatten, zum Term
[mm] e^\big{-\bruch{n^2}{2*r}}
[/mm]
führen könnten.
Ausserdem wird der Ausdruck [mm] \bruch{n}{r-n} [/mm] für die interes-
sierenden Werte von r und n nicht wirklich so klein,
dass die Näherung [mm] (1+\bruch{n}{r-n})^{\bruch{r-n}{n}}\approx [/mm] e tauglich
werden könnte.
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:57 Do 07.08.2008 | | Autor: | pelzig |
Hallo,
Habe vorhin auch über dieses Problem nachgedacht. Also diese Formel die dein Prof. verwendet hat ist auf jeden Fall nur eine Näherung, soviel steht fest.
Mein erster Ansatz war mit den Fakultäten, genau wie Al es auch gemacht hat, dann habe ich noch eine hübsche andere Idee gehabt:
Wir berechnen die Wahrscheinlichkeit des Gegenereignisses
B: "Zwei beliebige Teilnehmer haben nicht am selben Tag Geburtstag"
Dazu nehmen wir uns alle $l$ Paare, das sind genau [mm] $l:=\binom{n}{2}=\frac{n(n-1)}{2}$ [/mm] Stück. Die Wahrscheinlichkeit dass zwei verschiedene Typen nicht am gleichen Tag Geburtstag haben beträgt [mm] $p:=\frac{r-1}{r}=1-\frac{1}{r}$. [/mm] Irgendwie schien es mir plausibel, dass dann das Ergebnis B bedeutet, dass alle Paare gleichzeitig nicht gemeinsam Geburtstag haben, d.h. [mm] $P(B)=p^l$. [/mm] Es ist natürlich nicht die ekakte Wahrscheinlichkeit (auch wenn mir nicht ganz klar ist was daran nicht stimmt), da dann $P(B)>0$ auch noch für $n>r$ gelten würde, was nicht sein kann. Aber habs mal mit Mathematica ausplotten lassen und es haut "ziemlich genau" hin.
Jedenfalls kann man durch ein paar weitere wilde Abgeschätzungen auch in die gewünschte Form bringen:
[mm] $P(B)\approx p^l=p^{\frac{n^2-n}{2}}\stackrel{(\star)}{\approx}p^{\frac{n^2}{2}}=\exp\left(\frac{n^2}{2}\cdot\log p\right)$
[/mm]
(Der maximale absolute Fehler bei der Abschätzung [mm] $(\star)$ [/mm] liegt für $r=685$ bei etwa 1,6%)
Beachte die Reihendarstellung [mm] $\log(1+x)=\sum_{k\ge1}\frac{(-1)^{k+1}}{k!}x^k\approx [/mm] x$, d.h. [mm] $\log p\approx -\frac{1}{r}$, [/mm] da $p$ für große $r$ sehr nahe an 1 liegt. Da die Logartihmusreihe ja nix weiter als die Taylorreihenentwicklung an der Entwicklungsstelle 1 ist, lässt der Fehler sich hier auch noch sehr gut kontrollieren und liegt für $r=685$ bei etwa [mm] $7,3\cdot10^{-9}$...
[/mm]
Insgesamt erhalten wir damit also [mm] $P(B)\approx \exp(-n^2/2r)$ [/mm] - heureka ^^
Bis auf den noch unbekannten Fehler durch die bedingten (?) Wahrscheinlichkeiten liegt der Maximale absolute Fehler also bei ca 1,6%, Für große $r$ und $n$ dürfte er aber noch viel kleiner werden.
Was haltet ihr davon?
Gruß, Robert
|
|
|
| |
|
> diese Formel die dein Prof. verwendet hat ist auf jeden
> Fall nur eine Näherung, soviel steht fest.
das ist klar
> Wir berechnen die Wahrscheinlichkeit des Gegenereignisses
> B: "Zwei beliebige Teilnehmer haben nicht am selben Tag
> Geburtstag"
> Dazu nehmen wir uns alle [mm]l[/mm] Paare, das sind genau
> [mm]l:=\binom{n}{2}=\frac{n(n-1)}{2}[/mm] Stück. ![[ok]](/images/smileys/ok.gif "[ok]")
> Die Wahrscheinlichkeit dass zwei (bestimmte) verschiedene
> Typen nicht am gleichen Tag Geburtstag haben beträgt
> [mm]p:=\frac{r-1}{r}=1-\frac{1}{r}[/mm].
> Irgendwie schien es mir
> plausibel, dass dann das Ergebnis B bedeutet, dass alle
> Paare gleichzeitig nicht gemeinsam Geburtstag haben, d.h.
> [mm]P(B)=p^l[/mm]. Es ist natürlich nicht die ekakte
> Wahrscheinlichkeit (auch wenn mir nicht ganz klar ist was
> daran nicht stimmt),
es kann nicht genau stimmen, weil die einzelnen betrachteten
Ereignisse nicht unabhängig sind (da auch das Marsjahr nur
endlich viele Tage hat)
> da dann [mm]P(B)>0[/mm] auch noch für [mm]n>r[/mm]
> gelten würde, was nicht sein kann. Aber habs mal mit
> Mathematica ausplotten lassen und es haut "ziemlich genau"
> hin.
>
> Jedenfalls kann man durch ein paar weitere wilde
(das ist wohl wahr)
> Abschätzungen auch in die gewünschte Form bringen:
> [mm]P(B)\approx p^l=p^{\frac{n^2-n}{2}}\approx p^{\frac{n^2}{2}}=\exp\left(n^2/(2\red{\log p})\right)[/mm]
ich glaube da sollte log p nicht im Nenner, sondern im Zähler stehen
> Beachte die Reihendarstellung
> [mm]\log(1+x)=\sum_{k\ge1}\frac{(-1)^{k+1}}{k!}x^k\approx x[/mm],
> d.h. [mm]\log p\approx -\frac{1}{r}[/mm] und wir erhalten
> schließlich
> [mm]P(B)\approx \exp(-n^2/2r)[/mm] - heureka ^^
Gratulation !
> Kann die Fehler der Abschätzungen leider nicht genau
> quantifizieren, denke die relativen Fehler werden aber mit
> großen [mm]r[/mm] und [mm]n[/mm] beliebig klein. 
>
> Was haltet ihr davon?
nicht schlecht ! Du scheinst dich ganz gut in die Gedankengänge
eines "nicht sehr ordentlichen" Professors hineindenken zu können...
Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:49 Fr 08.08.2008 | | Autor: | pelzig |
> > Irgendwie schien es mir
> > plausibel, dass dann das Ergebnis B bedeutet, dass alle
> > Paare gleichzeitig nicht gemeinsam Geburtstag haben, d.h.
> > [mm]P(B)=p^l[/mm]. Es ist natürlich nicht die ekakte
> > Wahrscheinlichkeit (auch wenn mir nicht ganz klar ist was
> > daran nicht stimmt),
>
> es kann nicht genau stimmen, weil die einzelnen
> betrachteten Ereignisse nicht unabhängig sind
Ich erinnere mich dunkel an meine Schulzeit, da hatten wir ne bedingte Wahrscheinlichkeit, aber könntest du vielleicht genauer erklären welche Ereignisse hier nicht unabhängig sind? Wie kann man den Fehler der dadurch entsteht abschätzen? (Sorry hatte leider noch keine Stochastik bisher)
> > [...]
> > Jedenfalls kann man durch ein paar weitere wilde
> > Abschätzungen auch in die gewünschte Form bringen:
> > [mm]P(B)\approx p^l=p^{\frac{n^2-n}{2}}\approx p^{\frac{n^2}{2}}=\exp\left(n^2/(2\red{\log p})\right)[/mm]
>
> ich glaube da sollte log p nicht im Nenner, sondern im
> Zähler stehen
Jo... hab ich mich vertippt.
> Du scheinst dich ganz gut in die Gedankengänge eines
> "nicht sehr ordentlichen" Professors hineindenken zu können...
Na immerhin...
|
|
|
| |
|
> > > Irgendwie schien es mir
> > > plausibel, dass dann das Ergebnis B bedeutet, dass alle
> > > Paare gleichzeitig nicht gemeinsam Geburtstag haben, d.h.
> > > [mm]P(B)=p^l[/mm]. Es ist natürlich nicht die ekakte
> > > Wahrscheinlichkeit (auch wenn mir nicht ganz klar ist was
> > > daran nicht stimmt),
> >
> > es kann nicht genau stimmen, weil die einzelnen
> > betrachteten Ereignisse nicht unabhängig sind
>
> Ich erinnere mich dunkel an meine Schulzeit, da hatten wir
> ne bedingte Wahrscheinlichkeit, aber könntest du vielleicht
> genauer erklären welche Ereignisse hier nicht unabhängig
> sind? Wie kann man den Fehler der dadurch entsteht
> abschätzen?
Betrachten wir den einfachen Fall mit n=3, also mit drei
beliebigen Marsianern [mm] M_1, M_2, M_3.
[/mm]
Die Wahrscheinlichkeit, dass [mm] M_1 [/mm] und [mm] M_2 [/mm] an verschiedenen
Marstagen Geburtstag haben, ist [mm] p=\bruch{r-1}{r}=1-\bruch{1}{r},
[/mm]
ebenso für [mm] M_1 [/mm] und [mm] M_3 [/mm] oder für [mm] M_2 [/mm] und [mm] M_3. [/mm] Die
Anzahl der Paare ist [mm] l=\bruch{3*(3-1)}{2}=3, [/mm] also ergäbe
sich nach deinem Vorschlag [mm]P(B)=p^l=(1-\bruch{1}{r})^3=1-\bruch{3}{r}+\bruch{3}{r^2}-\bruch{1}{r^3}[/mm]
für die Wahrscheinlichkeit, dass alle 3 Geburtsdaten verschieden
sind. Effektiv ist diese Wahrscheinlichkeit aber:
[mm]P(B)=\bruch{r}{r}*\bruch{r-1}{r}*\bruch{r-2}{r}=1-\bruch{3}{r}+\bruch{2}{r^2}[/mm]
Dieses Ergebnis unterscheidet sich vom obigen um ein wenig;
die Differenz [mm] \bruch{1}{r^2}-\bruch{1}{r^3} [/mm] ist zwar klein, aber
eben nicht 0. Dies zeigt, dass die 3 Ereignisse " [mm] M_i [/mm] und [mm] M_j [/mm] haben
verschiedene Geburtstage" (<i,j> [mm] \in \{<1,2>,<1,3>,<2,3>\})
[/mm]
voneinander abhängig sind.
Eine einfache Abschätzung des Fehlers, den man bei dieser
Approximation (und den folgenden, die du in der weiteren
Rechnung vorgenommen hast) für beliebige Werte von r und n
macht, kann ich leider nicht anbieten.
LG
|
|
|
|
