Münzwurf < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:07 Sa 08.11.2008 | | Autor: | Sharadix |
| Aufgabe | Eine Münze wird 20.000 mal geworfen. Schätze die Wahrscheinlichkeit, dass die Anzahl,
wie oft Kopf erscheint, um mindestens 5% vom Erwartungswert abweicht, möglichst genau
ab, wobei
a) die Wahrscheinlichkeit für Kopf 0.5 ist;
b) die Wahrscheinlichkeit für Kopf 0.1 ist. |
Hallo,
meine Frage ist folgende. Dies ist eine Aufgabe aus einer Vorlesung die eigentlich nichts bzw. wenig mit Stochastik zu tun hat. (Informatik).
Allerdings hatten wir im Grundstudium Stochastik und unser Prof. verwöhnt uns gerne mit Aufgaben die auf Altwissen aufbauen.
Mir würde es schon mal reichen nach was für schlagwörtern ich z.B. bei Wikipedia schaun müsste um solch eine Aufgabe zu lösen.
Abweichung vom Erwartungswert, das war doch die Varianz, oder?
Also ich bin über jede Hilfe die diese Aufgabe betrifft dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:05 So 09.11.2008 | | Autor: | Infinit |
Hallo Sharadix,
Dein Experiment besteht ja darin, dass Du n-mal unabhängig voneinander ein Einzelexperiment durchführst, wobei Du weisst, wie häufig ein Ergebnis (in diesem Fall das Auftreten des Ergebnisses "Kopf") beim Einzelexperiment eintritt. Für die Gesamtbetrachtung hilft Dir die Binomialverteilung weiter.
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:42 So 16.11.2008 | | Autor: | Sharadix |
also ich hätte jetzt nochmal eine Frage.
Und zwar...Also ich denke man muss die Aufgabe mit den Chernoff Schranken bearbeiten. Das ist bisher zumindest das einzig sinnvolle was mir hierzu eingefallen ist.
Auf Wikipedia findet man ganz unten ein ähnliches Beispiel zum Münzwurf.
http://de.wikipedia.org/wiki/Chernoff-Ungleichung
Ich verstehe beim Beispiel auf wikipedia nicht ganz, wie man dieses [mm] "\delta" [/mm] berechnet und worum sichs dabei überhaupt handelt?
Mein Ansatz für die Aufgabe wäre jetzt folgender Gewesen:
a) Dafür ist der Erwartungswert 20000*0,5= 10000
5% davon sind dann 500.
Das heisst wenn ich die obere und untere Schranke will,
dann sind das 10500 und 9500
Jo und dann halt noch irgendwie in die Chernoff Schranken einsetzen, aber wie gesagt, dass ist mir noch nicht ganz klar. Vorallem:
In der Aufgabe wird ja gefordert 5% abweichung, also nach oben UND nach unten. Aber Chernoff Schranken geben ja nur eine mindest Abschätzung. Also eine obere Schranke : /.
Würde mich sehr über Hilfe freuen, komme hier leider grad nicht weiter.
|
|
|
| |
|
> also ich hätte jetzt nochmal eine Frage.
> Und zwar...Also ich denke man muss die Aufgabe mit den
> Chernoff Schranken bearbeiten. Das ist bisher zumindest das
> einzig sinnvolle was mir hierzu eingefallen ist.
> Auf Wikipedia findet man ganz unten ein ähnliches Beispiel
> zum Münzwurf.
> http://de.wikipedia.org/wiki/Chernoff-Ungleichung
> Ich verstehe beim Beispiel auf wikipedia nicht ganz, wie
> man dieses [mm]"\delta"[/mm] berechnet und worum sichs dabei
> überhaupt handelt?
>
> Mein Ansatz für die Aufgabe wäre jetzt folgender Gewesen:
> a) Dafür ist der Erwartungswert 20000*0,5= 10000
> 5% davon sind dann 500.
> Das heisst wenn ich die obere und untere Schranke will,
> dann sind das 10500 und 9500
>
> Jo und dann halt noch irgendwie in die Chernoff Schranken
> einsetzen, aber wie gesagt, dass ist mir noch nicht ganz
> klar. Vorallem:
> In der Aufgabe wird ja gefordert 5% abweichung, also nach
> oben UND nach unten. Aber Chernoff Schranken geben ja nur
> eine mindest Abschätzung. Also eine obere Schranke : /.
> Würde mich sehr über Hilfe freuen, komme hier leider grad
> nicht weiter.
Hallo Sharadix,
der Begriff Chernoff-Schranken ist mir zwar absolut
neu, aber schauen wir mal. Ich hätte, da n=20000
doch recht gross ist, eine Abschätzung durch eine
Approximation der Binomial- mit der Normalverteilung
versucht. Da aber eine möglichst genaue Abschätzung
gefragt ist, ist vielleicht Chernoff besser.
EDIT: Genau daran (dass Chernoff ev. besser wäre),
habe ich inzwischen aber grosse Zweifel. Siehe meine
weiteren Beiträge in diesem thread !
Nehmen wir gerade den Fall b) mit p=0.1.
Dann ist E=p*n=2000, und gesucht ist
$\ [mm] P\left(|k-E|\ge 100\right)=P\left(|k-2000|\ge 100\right)=P\left(k\ge 2100\right)+P\left(k\le 1900\right)$
[/mm]
Nach der ersten Formel aus dem Wikipedia-Text gilt:
$\ [mm] P(k\ge(1+\delta)*p*n)\le exp\left(-\bruch{min\{\delta,\delta^2\}}{3}*p*n\right)$
[/mm]
Jetzt müssen wir [mm] \delta [/mm] so bestimmen, dass [mm] (1+\delta)*p*n=2100 [/mm] ,
also [mm] (1+\delta)*2000=2100, [/mm] d.h. [mm] \delta=0.05
[/mm]
(aha, das sind ja einfach die 5 Prozent !)
[mm] \delta^2 [/mm] ist natürlich viel kleiner als [mm] \delta [/mm] , und so
erhalten wir:
$\ [mm] P(k\ge 2100)\le exp\left(-\bruch{0.0025}{3}*2000\right)\approx [/mm] 0.189$
Für die Abschätzung von [mm] P(k\le [/mm] 1900) kommt die zweite Chernoff-Ungleichung zum Zug, mit dem Ergebnis
$\ [mm] P(k\le 1900)\le exp\left(-\bruch{0.0025}{2}*2000\right)\approx [/mm] 0.082$
Zusammen hätten wir also dann:
$\ [mm] P\left(|k-2000|\ge 100\right)=P\left(k\ge 2100\right)+P\left(k\le 1900\right)\le [/mm] 0.271$
Ich habe nun noch die andere Rechnung (mit der
Normalverteilung) gemacht und komme dabei auf
eine viel kleinere Wahrscheinlichkeit. Irgendetwas
scheint also schief gelaufen zu sein. Aber was ?
Gruß al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:21 So 16.11.2008 | | Autor: | Sharadix |
Ahh,
tausend Dank. Klar, das [mm] \delta [/mm] sind genau die 5%.
Damit erklären sich auch die 4/10 im wikipedia Beispiel => 4/10*5=7.
Wo nun der Fehler liegen könnte weis ich allerdings auch nicht.
Eventuell darf man nicht einfach von 1900 bzw. 2100 ausgehen sondern muss von 2000 ausgehen. Aber keine Ahnung. Sieht für mich zumindest alles ziemlich richtig aus.
Chernoff ist ja angeblich die "beste" Abschätzung von den drei Abschätzungsmöglichkeiten die ich gefunden hatte, besser z.B. als Tschebycheff.
|
|
|
| |
|
> Ahh,
> tausend Dank. Klar, das [mm]\delta[/mm] sind genau die 5%.
> Damit erklären sich auch die 4/10 im wikipedia Beispiel =>
> 4/10*5=7.
du meinst 5+4/10*5=7
> Wo nun der Fehler liegen könnte weis ich allerdings auch
> nicht.
> Eventuell darf man nicht einfach von 1900 bzw. 2100
> ausgehen sondern muss von 2000 ausgehen.
die 2100 entsprechen einfach der 7 im wiki-Beispiel,
die 2000 der 5
> Sieht für mich zumindest alles ziemlich richtig aus.
> Chernoff ist ja angeblich die "beste" Abschätzung von den
> drei Abschätzungsmöglichkeiten die ich gefunden hatte,
> besser z.B. als Tschebycheff.
ich habe die Beispiele aus dem Artikel exakt
(nach Binomialverteilung) nachgerechnet und
folgende Resultate erhalten:
n=10 $\ [mm] P(k\ge [/mm] 7)= 0.172$ (nach Chernoff: 0.766)
n=100 $\ [mm] P(k\ge [/mm] 70)=0.0000393$ (nach Chernoff: 0.0695)
Im Artikel wird gepriesen, dass die Chernoff-Schranke
für n=100 schon "deutlich stärker" sei.
Wenn ich aber den Vergleich mit dem wirklichen
Resultat betrachte, kommen mir doch erhebliche
Zweifel an den Formeln aus dem Wiki-Artikel !
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:30 So 16.11.2008 | | Autor: | Sharadix |
Also ich bin mir jetzt gerade ein wenig unsicher wegen der unteren Schranke.
Also laut:http://www.reiter1.com/Glossar/Glossar.htm?Glossar_detailliert_Inhalt.html
bekommt man durch Chernoff nur eine obere Schranke. Auf Chernoff bin ich gekommen, weil es die einzige Formel war, die in unserem script kurz vorgestellt wurde. Allerdings ohne wirkliche Anwendung. Die Formel aus unserem script und aus wikipedia stimmt in etwa überein.
|
|
|
| |
|
> Also ich bin mir jetzt gerade ein wenig unsicher wegen der
> unteren Schranke.
> Also
> laut:http://www.reiter1.com/Glossar/Glossar.htm?Glossar_detailliert_Inhalt.html
> bekommt man durch Chernoff nur eine obere Schranke. Auf
> Chernoff bin ich gekommen, weil es die einzige Formel war,
> die in unserem script kurz vorgestellt wurde. Allerdings
> ohne wirkliche Anwendung. Die Formel aus unserem script und
> aus wikipedia stimmt in etwa überein.
Ich habe ja auch nur je eine obere Schranke für
Wahrscheinlichkeiten bestimmt, nämlich:
1.) $\ [mm] P(k\ge [/mm] 2100)\ [mm] \red{\le 0.189}$
[/mm]
2.) $\ P(k\ [mm] \blue{\le}\ [/mm] 1900)\ [mm] \red{\le 0.082}$ [/mm]
Auch in dem Text mit der obigen url findet
man Rechenbeispiele (ganz analog wie meine),
an denen man sieht, wie schlecht oder
extrem schlecht die Chernoff-Schranken
im Vergleich mit den exakten Werten sind.
Ein Zitat von dort:
"Wie man aus den obigen Beispielen erkennen kann,
ist die Chernoff Ungleichung sehr konservativ."
Eine Analogie zur Illustration:
Was würdest du denken und fühlen, wenn dir
der Chirurg vor einer Operation auf Grund einer
"konservativen Schätzung" versichern würde,
dass deine Überlebenschancen garantiert grösser
als 4 Prozent seien (obwohl, wie du erst nachher
erfährst, effektiv 99.7 % der so operierten
Patienten die Operation überleben) ?
LG
|
|
|
|
