Erwartungswert einer Summe < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:52 Mi 22.03.2006 | | Autor: | lebes |
Hallo,
habe folgendes Problem:
Seien [mm] X_1,...,X_n [/mm] diskrete Zufallsvariablen. ZB mit Werten in {1,..,k}.
Bekanntermaßen ist der Erwartungswert der Summe dieser ZVen, gerade die Summe der einzelnen Erwartungswerte:
[mm] E(X_1+...+X_n) [/mm] = [mm] E(X_1)+....+E(X_n)
[/mm]
Damit läßt sich dieser Erwartungswert mit n*k vielen Operationen berechnen. Ist also linear in der Anzahl der ZVen.
Nun will ich aber nicht den Erwartungswer der Summe, sondern den Erwartungswert der "gekappten" Summe berechnen, dh:
E( min( C, [mm] X_1+....+X_n))
[/mm]
Dieser Erwartungswert kann natürlich naiv mit [mm] o(k^n) [/mm] vielen Operationen berechnet werden. Das ist natürlich bei großem n sehr langsam. Komme aber irgendwie auf keinen effizienten Algorithmus. Effizient heißt in dem Fall mindestens erstmal polynomiell.
Oder ist diese Funktion am Ende NP-hart?
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
www.mathboard.de
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:54 Mi 22.03.2006 | | Autor: | Astrid |
Hallo,
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
> www.mathboard.de
kannst du in Zukunft bitte den genauen Link angeben:
http://www.matheboard.de/thread.php?threadid=31698
Danke.
Viele Grüße
Astrid
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:42 Mi 22.03.2006 | | Autor: | felixf |
Hallo!
> habe folgendes Problem:
> Seien [mm]X_1,...,X_n[/mm] diskrete Zufallsvariablen. ZB mit Werten
> in {1,..,k}.
> Bekanntermaßen ist der Erwartungswert der Summe dieser
> ZVen, gerade die Summe der einzelnen Erwartungswerte:
> [mm]E(X_1+...+X_n)[/mm] = [mm]E(X_1)+....+E(X_n)[/mm]
>
> Damit läßt sich dieser Erwartungswert mit n*k vielen
> Operationen berechnen. Ist also linear in der Anzahl der
> ZVen.
>
> Nun will ich aber nicht den Erwartungswer der Summe,
> sondern den Erwartungswert der "gekappten" Summe berechnen,
> dh:
> E( min( C, [mm]X_1+....+X_n))[/mm]
>
> Dieser Erwartungswert kann natürlich naiv mit [mm]o(k^n)[/mm] vielen
> Operationen berechnet werden. Das ist natürlich bei großem
> n sehr langsam. Komme aber irgendwie auf keinen effizienten
> Algorithmus. Effizient heißt in dem Fall mindestens erstmal
> polynomiell.
Warum berechnest du nicht zuerst die Verteilung von [mm] $X_1 [/mm] + [mm] \dots [/mm] + [mm] X_k$, [/mm] das geht polynomiell in $n k$, und damit dann den gekappten Erwartungswert (was dann linear in $n k$ geht)? (Der benoetigte Speicher ist von der Ordnung $n k$.)
Die einfachste Moeglichkeit, die Verteilung von [mm] $X_1 [/mm] + [mm] \dots [/mm] + [mm] X_k$ [/mm] zu berechnen, ist dies induktiv zu machen: Zuerst berechnest du die Verteilung von [mm] $X_1 [/mm] + [mm] X_2$, [/mm] dann die von [mm] $(X_1 [/mm] + [mm] X_2) [/mm] + [mm] X_3$, [/mm] etc.
Weiterhin kannst du auch mittels diskreter Fourier-Transformation die Verteilung von [mm] $X_1 [/mm] + [mm] \dots [/mm] + [mm] X_k$ [/mm] ausrechnen. Das ist natuerlich noch etwas komplizierter (soviel aber auch wieder nicht), zur Komplexitaet kann ich allerdings nicht sagen...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:35 Do 23.03.2006 | | Autor: | lebes |
Hm, wieso kann man die Verteilung der Summe in n*k Schritten ausrechnen? Wie geht das?
Nehmen wir doch mal folgende Wertebereiche für die Diskreten Variablen [mm] X_1,...,X_n [/mm] an:
[mm] X_1: [/mm] {1,2,...,9}
[mm] X_2: [/mm] {10, 20, ...., 90}
...
[mm] X_n: {10^{n-1}, 2 * 10^{n-1},..., 9 * 10^{n-1}}
[/mm]
Damit ist die Mächtigkeit des Wertebereiches der Summe [mm] 10^n. [/mm] Allein um jeden Wert des Wertebereiches eine Wahrscheinlichkeit zuzuweisen bräuchte ich doch schon [mm] 10^n [/mm] Operationen. Der Erwartungswert geht natürlich weiterhin in O(n) vielen Operationen.
Diese Geschichte mit der Fouriertransformierten. Meinst du in dem Fall die Laplacetransformierte? Wie sieht die nochmal aus? So weit ich mich entsinne stehen da die Wertausprägungen im Exponenten. Wenn ich die Dinger dann multipliziere, werde ich vermutlich auf das gleiche Problem stoßen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:21 Do 23.03.2006 | | Autor: | felixf |
> Hm, wieso kann man die Verteilung der Summe in n*k
> Schritten ausrechnen? Wie geht das?
Ich sagte polynomiell in $n k$ Schritten 
Unter der Voraussetzung das der Wertebereich [mm] $\{ 1, \dots, k \}$ [/mm] ist
> Nehmen wir doch mal folgende Wertebereiche für die
> Diskreten Variablen [mm]X_1,...,X_n[/mm] an:
> [mm]X_1:[/mm] {1,2,...,9}
> [mm]X_2:[/mm] {10, 20, ...., 90}
> ...
> [mm]X_n: {10^{n-1}, 2 * 10^{n-1},..., 9 * 10^{n-1}}[/mm]
Also $k = 9 [mm] \cdot 10^{n-1} \approx 10^n$.
[/mm]
> Damit ist die Mächtigkeit des Wertebereiches der Summe
> [mm]10^n.[/mm] Allein um jeden Wert des Wertebereiches eine
> Wahrscheinlichkeit zuzuweisen bräuchte ich doch schon [mm]10^n[/mm]
> Operationen. Der Erwartungswert geht natürlich weiterhin in
> O(n) vielen Operationen.
Du meinst in [mm] $O(10^n)$ [/mm] Operationen?
> Diese Geschichte mit der Fouriertransformierten. Meinst du
> in dem Fall die Laplacetransformierte? Wie sieht die
> nochmal aus? So weit ich mich entsinne stehen da die
> Wertausprägungen im Exponenten. Wenn ich die Dinger dann
> multipliziere, werde ich vermutlich auf das gleiche Problem
> stoßen.
Ist $f : [mm] \IN \to \IR$ [/mm] eine reellwertige Folge, so ist deren Fouriertransformierte [mm] $\hat{f} [/mm] : [mm] \IR \to \IC$ [/mm] gegeben durch $t [mm] \mapsto \sum_{k=0}^\infty [/mm] f(k) [mm] e^{-ikt}$. [/mm] Und fuer zwei Folgen $f, g$ gilt [mm] $\widehat{f \ast g} [/mm] = [mm] \hat{f} \hat{g}$. [/mm] Und wenn du weisst, dass [mm] $\hat{f}$ [/mm] die Fouriertransformierte einer Folge $f$ ist mit $f(k) = 0$ fuer $k [mm] \ge [/mm] M$, dann ist $f(k) = [mm] \sum_{j=0}^{M-1} \hat{f}\left( \frac{2 \pi j}{M} \right) e^{\frac{2 \pi i j k}{M}}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:28 Do 23.03.2006 | | Autor: | lebes |
Ok, dann sind wir uns zunächst mal einig, dass die Verteilung in gewissen Fällen nur in [mm] O(c^n) [/mm] berechnet werden kann (wobei n die Anzahl der Zufallsvariablen ist. Das ist also schon bei n>10 kaum noch praktikabel.
Weiterhin kann der Erwartungswert der Summe leicht berechnet werden. Weiterhin ist für mich offen, ob auch der Erwartungswert der gekappten Summe effizient berechnet werden kann. Falls jemand ne Idee hat wie auch dieser effizient berechnet werden kann, freue ich mich auf Antworten zu meiner Ausgangsfrage.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Fr 24.03.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
