Mageninfektion < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:03 Mi 23.10.2013 | | Autor: | Lonpos |
| Aufgabe | | Wir haben m Restaurants und wissen das eine Mageninfektion den Urpsrung in genau einem der m Restaurants hat. Die Wahrscheinlichkeit, dass es vom j-ten Resurant kommt ist [mm] p_j. [/mm] Ein Gesundheitsinspektor hat nun Proben von allen m Restaurants und führt Stichproben aus (Die Menge der Stichproben nennen wir S). Danach weiß er ob die Infektion von einem Restaurant aus der Menge S kommt oder dem Komplement. Nun sei [mm] N(p_1,...,p_m) [/mm] die kleinste erwartete Anzahl an Stichprobentests die es braucht um die Infektion zu lokalisieren. Zeige [mm] H(p_1,...,p_m)\le N(p_1,...,p_m)\le H(p_1,...,p_m)+1 [/mm] |
H bezeichnet hier die Entropie, das ist die durchschnittliche Menge an Information die wir erhalten wenn wir [mm] p_1,...,p_m [/mm] wissen und ist definiert als
[mm] H(p_1,...,p_m)=-\summe_{i=1}^{m}p_i\log_2 p_i
[/mm]
Ich habe mir zunächst überlegt genauere Aussagen zu [mm] N(p_1,...,p_m) [/mm] zu machen. Wenn ich richtig liege brauchen wir mindestens [mm] \lceil \bruch{m}{2} \rceil-1 [/mm] Stichprobentests um die Infektion genau zu lokalisieren. Ich kann aber nicht erkennen wie ich den Wert in die Ungleichung einbauen kann und damit die Ungleichung beweisen kann.
|
|
| |
|
> Wir haben m Restaurants und wissen dass eine Mageninfektion
> den Urpsrung in genau einem der m Restaurants hat. Die
> Wahrscheinlichkeit, dass es vom j-ten Resurant kommt ist
> [mm]p_j.[/mm] Ein Gesundheitsinspektor hat nun Proben von allen m
> Restaurants und führt Stichproben aus (Die Menge der
> Stichproben nennen wir S). Danach weiß er ob die Infektion
> von einem Restaurant aus der Menge S kommt oder dem
> Komplement. Nun sei [mm]N(p_1,...,p_m)[/mm] die kleinste erwartete
> Anzahl an Stichprobentests die es braucht um die Infektion
> zu lokalisieren. Zeige [mm]H(p_1,...,p_m)\le N(p_1,...,p_m)\le H(p_1,...,p_m)+1[/mm]
>
> H bezeichnet hier die Entropie, das ist die
> durchschnittliche Menge an Information die wir erhalten
> wenn wir [mm]p_1,...,p_m[/mm] wissen und ist definiert als
>
> [mm]H(p_1,...,p_m)=-\summe_{i=1}^{m}p_i\log_2 p_i[/mm]
>
> Ich habe mir zunächst überlegt genauere Aussagen zu
> [mm]N(p_1,...,p_m)[/mm] zu machen. Wenn ich richtig liege brauchen
> wir mindestens [mm]\lceil \bruch{m}{2} \rceil-1[/mm]
> Stichprobentests um die Infektion genau zu lokalisieren.
> Ich kann aber nicht erkennen wie ich den Wert in die
> Ungleichung einbauen kann und damit die Ungleichung
> beweisen kann.
Hallo Lonpos,
ich habe eine Reihe von Kritikpunkten, die die Aufgaben-
stellung betreffen:
1.) Die Aufgabe kommt meiner Meinung nach
(insbesondere mit dem Entropiebegriff)
irgendwie zu hochgestochen daher.
2.) Die Formulierung "die kleinste erwartete Anzahl an
Stichprobentests die es braucht ... " ist zu schwammig.
3.) Es wird nicht klar, ob der Inspektor die (angeblichen)
Wahrscheinlichkeiten [mm] p_j [/mm] kennt (falls ja, könnte er
sein Testprogramm entsprechend einrichten)
4.) Wenn da von Wahrscheinlichkeiten [mm] p_j [/mm] die Rede ist,
wissen wir auch gar nicht genau, was damit gemeint ist.
Mit dem Vorwissen (woher soll dies eigentlich kommen ?),
dass die Infektionsquelle in genau einem Restaurant liegt,
können wir natürlich (vom theoretischen Standpunkt aus)
sagen, dass genau ein [mm] p_j [/mm] den Wert 1 und alle anderen
den Wert 0 haben müssen. Doch vom pragmatischen
Standpunkt aus gesehen haben wir im Voraus keine
speziellen Kenntnisse, sollten also fairerweise [mm] p_j=\frac{1}{m}
[/mm]
für alle j voraussetzen. Vielleicht ist aber auch gemeint,
dass aufgrund gewisser vorgängiger Erfahrungen davon
ausgegangen wird, dass bei den verschiedenen Lokalen
die Wahrscheinlichkeit solcher unerwünschten Ereignisse
im Vornherein nicht gleich groß ist. Sollen die [mm] p_j [/mm] diese
Wahrscheinlichkeiten ausdrücken ?
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:37 Do 24.10.2013 | | Autor: | Lonpos |
Danke für deine Antwort, ich entschuldige meine schwammige Formulierung.
Nun zu den einzelnen Punkten:
1) Da dies ein Beispiel aus der Kodierungstheorie ist, kommt der Begriff "Entropie" vor, ich würde diesen Begriff gerne im Beispiel lassen, auch wenn er ein wenig zu hochgestochen für diese Aufgabe klingt.
2)Ich habe disen Term aus dem Englischen [mm] "N(p_1,...,p_m) [/mm] denotes the minimum expected number of tests needed to locate the infection"
3)Ja, der Gesundsheitsinspektor weiß über alle Wahrscheinlichkeiten bereits im vornherein Bescheid.
4)Hier trifft deine letzte Vermutung zu, die Wsl [mm] p_j [/mm] müssen nicht unbedingt alle gleich. Aufgrund vergangener (im Beispiel nicht erwähnter) Untersuchungen sind die Wsl von Lokal zu Lokal verschieden.
|
|
|
| |
|
> 1) Da dies ein Beispiel aus der Kodierungstheorie ist,
> kommt der Begriff "Entropie" vor, ich würde diesen Begriff
> gerne im Beispiel lassen, auch wenn er ein wenig zu
> hochgestochen für diese Aufgabe klingt.
Vielleicht macht er (angesichts (3)) sogar mehr Sinn,
als ich zuerst gedacht hatte ...
> 2)Ich habe disen Term aus dem Englischen [mm]"N(p_1,...,p_m)[/mm]
> denotes the minimum expected number of tests needed to
> locate the infection"
>
> 3)Ja, der Gesundsheitsinspektor weiß über alle
> Wahrscheinlichkeiten bereits im vornherein Bescheid.
Das ist wichtig zu wissen.
> 4)Hier trifft deine letzte Vermutung zu, die Wsl [mm]p_j[/mm]
> müssen nicht unbedingt alle gleich. Aufgrund vergangener
> (im Beispiel nicht erwähnter) Untersuchungen sind die Wsl
> von Lokal zu Lokal verschieden.
Diese weiteren Informationen bringen mich zu einer
Idee, wie die Teststrategie wohl aussehen sollte, die
mit möglichst wenigen Schritten zum Ziel führt.
Für jeden einzelnen Testschritt teilt man die noch
vorhandenen "Kandidaten" für die Infektionsquelle
in zwei Gruppen ein, deren Wahrscheinlichkeiten
sich möglichst exakt zur gleichen Summe aufaddieren.
Sind die anfänglichen Wahrscheinlichkeiten, in Prozenten
ausgedrückt, z.B.
1,1,1,1,1,2,2,2,3,3,4,5,5,6,7,9,10,10,12,15
so könnte man sie so aufteilen:
1,1,1,2,3,5,5,7,10,15
1,1,2,2,3,4,6,9,10,12
Die Vorgehensweise erinnert natürlich (und zu Recht)
an die vielen Wäge-Aufgaben, bei denen man aus
einer vorgegebenen Menge äußerlich gleich aussehender
Kugeln z.B. diejenige (einzige) herausfinden soll, die
z.B. ein bisschen leichter ist als alle anderen (unterein-
ander gleich schweren). Bei dieser Aufgabe würde
die erforderliche Anzahl Wägungen ebenfalls durch
einen Binärlogarithmus ausgedrückt.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:54 Do 24.10.2013 | | Autor: | Lonpos |
Mich erinnert deine Vorgehsnweise sehr an die Vorgehensweise die beim Huffmann Algorithmus durchgeführt wird.
http://de.wikipedia.org/wiki/Huffman-Kodierung#Beispiel
[mm] N(p_1,..,p_m) [/mm] wäre dann die erwartete Länge des Codeworts
Gleichheit herrscht wenn der Algorithmus perfekt ist.
|
|
|
| |
|
> Mich erinnert deine Vorgehensweise sehr an die,
> die beim Huffmann Algorithmus durchgeführt wird.
>
> http://de.wikipedia.org/wiki/Huffman-Kodierung#Beispiel
Ja, auch diese Analogie ist kein Zufall.
Al-Chw.
|
|
|
|
