Monte-Carlo-Verfahren < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ein System besteht aus 20 unabh. Komponenten. Die i'te Komponente funktioniert mit Wahrscheinlichkeit (25+i)/50.
Sei X ... "Anzahl der funktionsfähigen Komponenten"
Entwickel ein MC-Verfahren, um die Wahrscheinlichkeit P[X [mm] \le [/mm] 5] effektiv abzuschätzen. |
Die einfachen Fälle kann man leicht angeben:
P[X=0] = [mm] \produkt_{i=1}^{20} \bruch{25-i}{50} [/mm] = [mm] \bruch{24!}{4!*50^20}
[/mm]
P[X=20] = [mm] \produkt_{i=1}^{20} \bruch{25+i}{50} [/mm] = [mm] \bruch{45!}{25!*50^20}
[/mm]
P[X=1] geht auch noch, da es nur 20 mögliche Konstellationen gibt. Aber für beliebige [mm] n\in[1,20] [/mm] besitzt P[X=n] genau [mm] \vektor{20 \\ n} [/mm] Konstellationen, das wird für P[X=5] schon ziemlich hässlich, also soll man das ganze abschätzen.
Sei [mm] S=\{(x_{1},x_{2},\cdots,x_{20}) | x_{k} \in \{0,1\} \forall k=1,\cdots,20\} [/mm] die Menge aller Konstellationen, wobei [mm] x_{k}=0 [/mm] bedeutet, dass Komponente [mm] x_{k} [/mm] nicht mehr funktionsfähig ist.
Das Ereignis für P[X=n] lautet dann:
[mm] A_{n}=\{x \in S | \summe_{i=1}^{20} x_{i} = n \}
[/mm]
Da wir P[X [mm] \le [/mm] 5] berechnen wollen, müssen wir also [mm] P[A_{0}]+\cdots+ P[A_{5}] [/mm] irgendwie abschätzen.
[mm] P[A_{n}] [/mm] schätzen wir wie folgt an:
[mm] P[A_{n}] [/mm] = [mm] E[I_{A_{n}}] [/mm] wobei I die Indikatorfunktion ist.
der j'te MC-Schätzer wäre dann:
[mm] P'[A_{n}]_{j} [/mm] = [mm] \bruch{1}{j} \summe_{i=1}^{j} I_{A_{n}}(X_{i}) [/mm] wobei [mm] X_{i} [/mm] unabhängig sind mit der gleichen Verteilung, wie in der Aufgabenstellung.
Soweit bin ich jetzt analog zu unserem Skript vorgegangen und ab hier ist im Skript auch schon Schluß.
Was genau soll denn jetzt einfacher sein?
Ich vermute mal, dass diese [mm] X_{i} [/mm] im Grunde konkrete gewichtete Stichproben seinen sollen: Sprich, wenn ich mir 1000 MC-Schätzer raussuchen will bezüglich [mm] A_{5}, [/mm] dann erzeuge ich mir 1000 mögliche Konstellationen (mit der obigen Verteilung), also eine erzeugte Konstellation wäre z.B. ein 20-Tupel, wobei die erste Komponente mit Wkt. [mm] \bruch{26}{50} [/mm] "1" ist, die zweite Komponente mit Wkt. [mm] \bruch{27}{50} [/mm] "1" ist usw.
Die Indikatorfunktion macht dann z.B. folgendes:
[mm] I_{A_{5}}(X_{i}) [/mm] = [mm] \begin{cases} 1 fuer X_{i} \in A_{5} \\ 0sonst \end{cases}
[/mm]
[mm] P'[A_{5}]_{j} [/mm] "zählt" dann alle j gewichteten Stichproben, die in [mm] A_{5} [/mm] liegen und teilt durch die Anzahl der Stichproben, also j. So bekommen wir anscheinend einen Wert, der für große j nah am Erwartungswert von [mm] I_{A_{n}}, [/mm] also [mm] P[A_{n}] [/mm] liegt.
Habe ich das ganze soweit richtig interpretiert?
Und: Ist das ganze jetzt effektiv und damit die Aufgabe gelöst?
Ich schätze mal, man soll jetzt noch angeben, wie viele gewichtete Stichproben man ungefähr erzeugen muss, um ein halbwegs sinnvolles Ergebnis zu erhalten.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:28 Di 31.05.2011 | | Autor: | Blech |
Hi,
> Was genau soll denn jetzt einfacher sein?
einfacher als was? Und wovon redest Du?
1. Das MC Verfahren ist wesentlich einfacher durchzuführen als die exakte Lösung, die für größere Systeme (und andere Werte) noch dazu exponentiell schlimmer wird.
In R sollte
sum( runif(20) > c(1:20 + 25)/50 )
Dir dagegen schnell und effektiv aus X ziehen. Und das unabhängig davon, ob Du [mm] $P(X\leq [/mm] 10)$ od. 200 Komponenten willst (ohne Mehrkosten fürs erste und mit linearem Wachstum fürs zweite).
2. Einfacher als Deine Lösung wäre es, nicht [mm] $P(A_n)$, $n=0,\ldots,5$, [/mm] zu betrachten, sondern direkt zu schauen, ob das gezogene X kleiner od. gleich 5 ist.
Nachdem [mm] $I_{X_j\leq 5}$ [/mm] eine Folge von i.i.d. Bernoulli-Variablen ist (d.h. Du schaust nur, ob jeder gezogene Wert [mm] $\leq$ [/mm] oder > 5 ist), ist Dein Schätzer für [mm] $P(X\leq [/mm] 5)$ binomial-verteilt, und dementsprechend läßt sich der zu erwartende Fehler leicht berechnen.
Sonst sieht alles, was Du schreibst richtig aus, aber ich hab nicht jedes Zeichen dreimal umgedreht. =)
ciao
Stefan
|
|
|
| |
|
Danke Stefan, habe deinen Tipp berücksichtigt!
Aber was genau meinst du im ersten Punkt und vorallem diesen "schnell und effektiv aus X ziehen"? Wäre super wenn du das erläutern könntest!
LG #
> Hi,
>
> > Was genau soll denn jetzt einfacher sein?
>
> einfacher als was? Und wovon redest Du?
>
> 1. Das MC Verfahren ist wesentlich einfacher durchzuführen
> als die exakte Lösung, die für größere Systeme (und
> andere Werte) noch dazu exponentiell schlimmer wird.
>
> In R sollte
>
> sum( runif(20) > c(1:20 + 25)/50 )
>
> Dir dagegen schnell und effektiv aus X ziehen. Und das
> unabhängig davon, ob Du [mm]P(X\leq 10)[/mm] od. 200 Komponenten
> willst (ohne Mehrkosten fürs erste und mit linearem
> Wachstum fürs zweite).
>
>
> 2. Einfacher als Deine Lösung wäre es, nicht [mm]P(A_n)[/mm],
> [mm]n=0,\ldots,5[/mm], zu betrachten, sondern direkt zu schauen, ob
> das gezogene X kleiner od. gleich 5 ist.
>
>
> Nachdem [mm]I_{X_j\leq 5}[/mm] eine Folge von i.i.d.
> Bernoulli-Variablen ist (d.h. Du schaust nur, ob jeder
> gezogene Wert [mm]\leq[/mm] oder > 5 ist), ist Dein Schätzer für
> [mm]P(X\leq 5)[/mm] binomial-verteilt, und dementsprechend läßt
> sich der zu erwartende Fehler leicht berechnen.
>
>
> Sonst sieht alles, was Du schreibst richtig aus, aber ich
> hab nicht jedes Zeichen dreimal umgedreht. =)
>
> ciao
> Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:43 Mi 01.06.2011 | | Autor: | Blech |
> Aber was genau meinst du im ersten Punkt und vorallem diesen "schnell und effektiv aus X ziehen"? Wäre super wenn du das erläutern könntest!
Ich meinte, daß
> sum( runif(20) > c(1:20 + 25)/50 )
Dir Zufallszahlen mit der gleichen Verteilung wie X generiert (das meint man, wenn man sagt, daß man aus einer Verteilung zieht) und das zu vernachlässigbaren Kosten in Sachen rechnerischem Aufwand (<100 flops).
Es gibt bei exakt 5 funktionsfähigen Komponenten [mm] ${20\choose 5}$ [/mm] Möglichkeiten, diese auszuwählen; und das wird rapide schlimmer für größere Werte wie [mm] ${20\choose 10}$ [/mm] od. [mm] ${30\choose 5}$.
[/mm]
ciao
Stefan
|
|
|
|
