Erwartungswert einer Summe von Zufallsvariablen |
| 22.03.2006, 17:29 | lebes | Auf diesen Beitrag antworten » | ||
| Erwartungswert einer Summe von Zufallsvariablen habe folgendes Problem: Seien X_1,...,X_n diskrete Zufallsvariablen. ZB mit Werten in {1,..,k}. Bekanntermaßen ist der Erwartungswert der Summe dieser ZVen, gerade die Summe der einzelnen Erwartungswerte: E(X_1+...+X_n) = E(X_1)+....+E(X_n) 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, X_1+....+X_n)) Dieser Erwartungswert kann natürlich naiv mit o(k^n) 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? |
||||
| 04.04.2006, 15:29 | Dual Space | Auf diesen Beitrag antworten » | ||
RE: Erwartungswert einer Summe von Zufallsvariablen
Auch hier mal *push*. Nun zur Sache: Sicher meinst du, dass der Aufwand ist, also mit großem "O". So dann zu dem "polynomiell": Auch ein Rechenaufwand von kann polynomiell sein, oder täusche ich mich da 
? Also was ist dein eigentliches Ziel?Und "NP-hart" ist für mich neues Vokabular, so dass ich eine Erklärung benötige. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
