Varianz und Erwartungswert < math. Statistik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:20 Mo 05.01.2009 | | Autor: | Nataliee |
| Aufgabe | Hiermit wurden die Erwartungswerte gebildet:
Für $ [mm] X_1: [/mm] $
Sei X die Laufzeit eines Algorithmus,
der nach $ [mm] k_1 [/mm] $ Schritten mit Wahrscheinlichkeit p und mit
W-keit 1-p nach $ [mm] k_2 [/mm] $ Schritten terminiert (k1 < k2).
> =>$ [mm] E(X_1)=pk_1+(1-p)k_2 [/mm] $
Für $ [mm] X_2 [/mm] $ wird der 1. Algorithmus abgeändert:
Bei nicht erfolgter Ausgabe nach k1 Schritten wird der
Algorithmus jeweils stets neu gestartet (dabei ist das
Ergebnis des nächsten Durchlaufs "unabhängig" von der
Vorgeschichte).
=>$ [mm] E(X_2)=\bruch{k_1}{p} [/mm] $
Zur Aufgabe
Es bezeichne $ [mm] X_{1} [/mm] $ die Laufzeit des ursprünglichen Algorithmus und $ [mm] X_{2} [/mm] $ die Laufzeit eines neuen Algorithmus.
Die Lösung ergibt $ [mm] E(X_2) \le E(X_1) [/mm] $ (oder $ [mm] \ge) [/mm] $ genau dann, wenn $ [mm] \bruch{1+p}{p}\le\bruch{k_1}{k_2} [/mm] $ (oder $ [mm] \ge) [/mm] $ gilt.
(a) Berechnen Sie $ [mm] Var(X_1) [/mm] $ und $ [mm] Var(X_2). [/mm] $
(b) Wann ist $ [mm] Var(X_2) [/mm] $ < $ [mm] Var(X_1)? [/mm] $
(c) Zeigen Sie: Ist $ [mm] E(X_1) [/mm] $ = $ [mm] E(X_2), [/mm] $ so gilt $ [mm] Var(X_1) [/mm] $ < $ [mm] Var(X_2). [/mm] $
Damit ist der ursprüngliche Algorithmus vorzuziehen, wenn extrem lange Laufzeiten überproportionale Kosten verursachen.
(Hinweis: Die Betrachtung des Parameters $ [mm] \bruch{k_2}{k_1} [/mm] $ ist nützlich.) |
"Diese Aufgabe wurde schon mal erstellt, diese wurde leider durch meine Wenigkeit :) unübersichtlich und deshalb möchte ich gerne mein Problem genauer darstellen."
zu a)
[mm] Var(X_1)=E(X_1^2)-E(X_1)^2= pk_1^2+(1-p)k_2 ^2-(pk_1+(1-p)k_2)^2
[/mm]
[mm] Var(X_2)=E(X_2^2)-E(X_2)^2=\bruch{k_1^2}{p} -\bruch{k_1^2}{p^2} [/mm]
zu b)
[mm] Var(X_2) [/mm] $ < $ [mm] Var(X_1)
[/mm]
[mm] \bruch{k_1^2}{p} -\bruch{k_1^2}{p^2}
[mm] \bruch{k_1^2(p-1)}{p^3}
[mm] -\bruch{pk_1^2(1-p)}{p^2} >-pk_1^2-(1-p)k_2 ^2+(pk_1+(1-p)k_2)^2, |+pk_1^2
[/mm]
[mm] -\bruch{pk_1^2(1-p)}{p^2}+pk_1^2>-(1-p)k_2 ^2+(pk_1+(1-p)k_2)^2 [/mm] ,| aulösen von [mm] (pk_1+(1-p)k_2)^2 [/mm]
[mm] -\bruch{pk_1^2(1-p)}{p^2}+pk_1^2>-(1-p)k_2 ^2+pk_1^2 +2pk_1k_2(1-p)+k_2^2+p^2k_2^2 [/mm] , | [mm] -pk_1^2
[/mm]
[mm] -\bruch{pk_1^2(1-p)}{p^2}>-(1-p)k_2 ^2+2pk_1k_2(1-p)+k_2^2+p^2k_2^2 [/mm] , | rechts zusammenfassen
[mm] -\bruch{pk_1^2(1-p)}{p^2}>(-1+p+1+p^2)k_2 ^2+2pk_1k_2(1-p)| [/mm] rechts zusammenfassen
[mm] -\bruch{pk_1^2(1-p)}{p^2}>(p+p^2)k_2 ^2+2pk_1k_2(1-p)| [/mm] rechts zusammenfassen
[mm] -\bruch{pk_1^2(1-p)}{p^2}>(1+p)pk_2^2+2pk_1k_2(1-p), [/mm] jetzt weiß ich nicht wie ich nach [mm] \bruch{k_2}{k_1} [/mm] auflösen soll.
Vielleicht könnt ihr mir helfen.
Schönen Gruß euch allen!
|
|
| |
|
Hallo Nataliee,
ohne Gewähr auf Richtigkeit. Deine Ungleichung lautet:
[mm] \bruch{k_1^2}{p} [/mm] - [mm] \bruch{k_1^2}{p^{2}} [/mm] < [mm] pk_1^2+(1-p)k_2 ^2-(pk_1+(1-p)k_2)^2
[/mm]
Ich forme erstmal nur die rechte Seite um:
[mm] pk_1^2+(1-p)k_2 ^2-(pk_1+(1-p)k_2)^2 [/mm] =
[mm] pk_1^2+(1-p)k_2 ^2-(p^2k_1^2 [/mm] + [mm] 2p(1-p)k_1 k_2 [/mm] + [mm] (1-p)^2k_2^2 [/mm] =
[mm] (p-p^2)k_1^2 [/mm] + ( (1-p) - [mm] (1-p)^2)k_2^2 [/mm] - [mm] 2p(1-p)k_1 k_2=
[/mm]
[mm] p(1-p)k_1^2 [/mm] + [mm] p(1-p)k_2^2 [/mm] - [mm] 2p(1-p)k_1 k_2 [/mm] =
[mm] p(1-p)(k_1^2 [/mm] - [mm] 2k_1k_2 [/mm] + [mm] k_2^2) [/mm] = [mm] p(1-p)(k_1-k_2)^2 [/mm]
Daraus sollte sich doch jetzt was machen lassen, oder?
Hoffe das hilft, Steffen
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:09 Mi 07.01.2009 | | Autor: | Nataliee |
Hallo steffenhst,
ja super bin einverstanden :) mit der Lösung.Demnach
$ [mm] \bruch{k_1^2}{p} [/mm] $ - $ [mm] \bruch{k_1^2}{p^{2}} [/mm] $ < $ [mm] pk_1^2+(1-p)k_2 ^2-(pk_1+(1-p)k_2)^2 [/mm] $
<=>$ [mm] \bruch{k_1^2}{p} [/mm] $ - $ [mm] \bruch{k_1^2}{p^{2}} [/mm] $<$ [mm] p(1-p)(k_1-k_2)^2 [/mm] $
der Linke Teil läßt sich so umformen:
[mm] \bruch{k_1^2}{p}- \bruch{k_1^2}{p^2}
[/mm]
= [mm] \bruch{p^2k_1^2-pk^2}{p^3} [/mm]
= [mm] \bruch{pk_1^2(p-1)}{p^3}
[/mm]
Demnach
$ [mm] \bruch{pk_1^2(p-1)}{p^3} [/mm] $<$ [mm] p(1-p)(k_1-k_2)^2 [/mm] $, wenn ich nun *(-1) vertauscht sich das < zu > also
$ [mm] \bruch{pk_1^2(1-p)}{p^3} [/mm] $>$ [mm] -p(1-p)(k_1-k_2)^2 [/mm] $, jetzt kann ich durch p(1-p) teilen also
$ [mm] \bruch{k_1^2}{p^3} [/mm] $>$ [mm] -(k_1-k_2)^2 [/mm] $
Jetzt kann ich nicht geschickt umformen, der Rechte Teil ist
$ [mm] -(k_1-k_2)^2 $=-k_1^2+2k_1k_2-k_2^2
[/mm]
Gruß Nataliee
|
|
|
| |
|
Hallo,
ich komme auch nur auf die folgende Ungleichung:
[mm] \bruch{k_1^2}{(k_1 - k_2)^2} [/mm] > - [mm] p^3.
[/mm]
Weiter vereinfachen kann man das m.E. nicht, auf jeden Fall nicht auf einen Ausdruck [mm] \bruch{k_1}{k_2}.
[/mm]
Kannst du denn diese Ungleichung nicht schon inhaltlich interpretieren?
Grüße, Steffen
|
|
|
| |
|
(b) Wann ist $ [mm] Var(X_2) [/mm] $ < $ [mm] Var(X_1)? [/mm] $
(c) Zeigen Sie: Ist $ [mm] E(X_1) [/mm] $ = $ [mm] E(X_2), [/mm] $ so gilt $ [mm] Var(X_1) [/mm] $ < $ [mm] Var(X_2). [/mm] $
Ja wenns wohl nicht weitergeht...
$ [mm] \bruch{k_1^2}{(k_1 - k_2)^2} [/mm] $ > - $ [mm] p^3 [/mm] $
Um jetzt b) zu beantworten soll man wohl noch die Werte nennen:
Also Grundsätzlich gilt nach Aufgabenstellung [mm] k_1,k_2 \in [/mm] 1,2,3,... und 0<p<1.
Wieterhin muß gelten [mm] k_1 [/mm] ungleich [mm] k_2. [/mm] und p [mm] \in [/mm] (0,1) Für diese Fälle gilt [mm] Var(X_2) [/mm] $ < $ [mm] Var(X_1).
[/mm]
c)Wann ist [mm] E(X_1)=pk_1+(1-p)k_2 =\bruch{k_1}{p} [/mm] = [mm] E(X_2)?
[/mm]
[mm] pk_1+(1-p)k_2=\bruch{k_1}{p} [/mm]
Vielleicht hast du ja hier noch eine Idee.
Stelle es nach (Hinweis: Die Betrachtung des Parameters $ [mm] \bruch{k_2}{k_1} [/mm] $ ist nützlich.)
[mm] pk_1+(1-p)k_2 =\bruch{k_1}{p} [/mm] , durch [mm] k_1
[/mm]
[mm] p+(1-p)\bruch{k_2}{k_1}=\bruch{1}{p}
[/mm]
...
[mm] \bruch{k_2}{k_1}=\bruch{1-p^2}{p(1-p)}
[/mm]
um, bringt mich aber leider nicht weiter.
|
|
|
| |
|
Ist das so schwer oder stelle ich mich dumm an?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Sa 10.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Fr 09.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
