Erwartungswert vom Maximum von Zufallsvariablen (Summe von Ereignissen)

26.11.2018, 13:58

LubTobi

Erwartungswert vom Maximum von Zufallsvariablen (Summe von Ereignissen)

Meine Frage:
Guten Tag!

Ich habe eine Frage zum Erwartungswert von folgendem Experiment:

Eine Münze mit den Werten 0 und 1 wird n mal geworfen. Die Zufallsvariable $\begin{eqnarray*} X_i \end{eqnarray*}$ , mit $\begin{eqnarray*} i\in\{1, ..., k\} \end{eqnarray*}$ , gibt die Summe der n geworfenen Werte an. Wir definieren eine neue Zufallsvariable $\begin{eqnarray*} Z := max(X_1, ..., X_k) \end{eqnarray*}$ .
Wie lautet der Erwartungswert von Z?

Meine Ideen:
Mein Ansatz bestimmt den Erwartungswert nur für $\begin{eqnarray*} n = 1 \end{eqnarray*}$ korrekt:
$\begin{eqnarray*} E(Z) = 0\cdot P(Z=0) + 1\cdot P(Z=1) = P(Z=1) \end{eqnarray*}$
$\begin{eqnarray*} = 1 - P(Z=0) = 1 - P(X_1=0, X_2=0, ..., X_k=0) \end{eqnarray*}$
$\begin{eqnarray*} = 1 - P(X_1=0)\cdot P(X_2=0)\cdot ... P(X_k=0) \end{eqnarray*}$
$\begin{eqnarray*} = 1 - P(X_1=0)^k = 1 - \frac{1}{2^k} \end{eqnarray*}$

Die letzte Zeile gilt, da die ZV identisch und unabhängig verteilt sind.

Dieses Verfahren kann leider nicht auf $\begin{eqnarray*} n>1 \end{eqnarray*}$ erweitert werden, da das Maximum der ZV für verschiedene Werte der Münze nicht immer gleich sein muss.

Hat jemand eine Idee, wie ich den Erwartungswert für allgemeines k berechnen kann?

26.11.2018, 14:10

HAL 9000

Auf diesen Beitrag antworten »

Es ist $\begin{eqnarray*} E(Z) = \sum_{j=1}^n j\cdot P(Z=j) = \sum_{j=1}^n \sum_{i=1}^j P(Z=j) = \sum_{i=1}^n \sum_{j=i}^n P(Z=j) = \sum_{i=1}^n P(Z\geq i) \end{eqnarray*}$ .

Nun ist $\begin{eqnarray*} P(Z\geq i) = 1-P(Z<i) = 1-(P(X_1<i))^k \end{eqnarray*}$ , insgesamt also

$\begin{eqnarray*} E(Z) = n - \frac{1}{2^{nk}}\sum_{i=1}^n \left( \sum_{j=0}^{i-1} \binom{n}{j} \right)^k \end{eqnarray*}$ .

Wäre schön, wenn man das noch etwas vereinfachen könnte, momentan sehe ich aber nicht ob und wie.

26.11.2018, 14:23

LubTobii

Auf diesen Beitrag antworten »

Danke HAL 9000!

Warum gilt denn:

Zitat:

Original von HAL 9000
$\begin{eqnarray*} \sum_{j=1}^n \sum_{i=1}^j P(Z=j) = \sum_{i=1}^n \sum_{j=i}^n P(Z=j) \end{eqnarray*}$ .

Ich benötige eine Abschätzung (untere Schranke) von $\begin{eqnarray*} E(Z) \end{eqnarray*}$ , wenn möglich nicht von n abhängig, sehe allerdings nicht, wie das klappen soll.

26.11.2018, 14:42

HAL 9000

Auf diesen Beitrag antworten »

Zur ersten Frage: Weil in beiden Doppelsummen über alle Tupel $\begin{eqnarray*} (i,j) \end{eqnarray*}$ mit $\begin{eqnarray*} 1\leq i\leq j\leq n \end{eqnarray*}$ summiert wird: Einmal mit $\begin{eqnarray*} i \end{eqnarray*}$ als äußerer Summationsvariable, das andere mal mit $\begin{eqnarray*} j \end{eqnarray*}$ als solcher. Augenzwinkern

Zur anderen Frage der Abschätzung muss ich noch etwas nachdenken. Man kann natürlich rabiat abschätzen

$\begin{eqnarray*} \sum_{j=0}^{i-1} \binom{n}{j} \leq \sum_{j=0}^{n-1} \binom{n}{j} = 2^n-1 \end{eqnarray*}$ für alle $\begin{eqnarray*} i=1,\ldots,n \end{eqnarray*}$ ,

und somit $\begin{eqnarray*} E(Z) \geq n - \frac{n}{2^{nk}} (2^n-1)^k = n\left(1 - \left(1-\frac{1}{2^n}\right)^k \right) \end{eqnarray*}$ . Für festes $\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ ist die praktisch nicht zu gebrauchen, wohl aber für festes $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k\to\infty \end{eqnarray*}$ , da sichert sie immerhin die Konvergenz $\begin{eqnarray*} E(Z)\nearrow n \end{eqnarray*}$ .

26.11.2018, 14:53

LubTobii

Auf diesen Beitrag antworten »

Danke für die Lösung und die Erklärung!

26.11.2018, 16:05

HAL 9000

Auf diesen Beitrag antworten »

Genügt die Abschätzung denn? Ich weiß ja nicht, was du damit vorhast.

Falls es aber um $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ bei festem $\begin{eqnarray*} k \end{eqnarray*}$ gehen sollte, da ist selbst die triviale Abschätzung $\begin{eqnarray*} E(Z)\geq \frac{n}{2} \end{eqnarray*}$ (Gleichheit für $\begin{eqnarray*} k=1 \end{eqnarray*}$ ) besser, die wächst für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ wenigstens unbeschränkt (was man von $\begin{eqnarray*} n\mapsto n\left(1 - \left(1-\frac{1}{2^n}\right)^k \right) \end{eqnarray*}$ nicht behaupten kann).

26.11.2018, 22:08

LubTobii

Auf diesen Beitrag antworten »

Leider genügt die Abschätzung noch nicht ganz.

Das Optimale Ziel wäre es, wenn
$\begin{eqnarray*} E(Z) = n - \frac{1}{2^{nk}}\sum_{i=1}^n \left( \sum_{j=0}^{i-1} \binom{n}{j} \right)^k = n - \epsilon \end{eqnarray*}$
mit $\begin{eqnarray*} \epsilon\to 0 \end{eqnarray*}$ , wenn k exponentiell in n liegt.

Mithilfe der obrigen Abschätzung bekomme ich nur
$\begin{eqnarray*} E(Z) = n \cdot (1 - \frac{1}{e}) \end{eqnarray*}$

Mir fällt leider kein Ansatz, wie man $\begin{eqnarray*} \epsilon \end{eqnarray*}$ abschätzen kann.

26.11.2018, 22:37

LubTobii

Auf diesen Beitrag antworten »

Korrektur
k kann exponentiell sein, jedoch nicht in n. Also $\begin{eqnarray*} 2^k \end{eqnarray*}$ ist in Ordnung, $\begin{eqnarray*} n^k \end{eqnarray*}$ jedoch nicht.

26.11.2018, 22:52

LubTobii

Auf diesen Beitrag antworten »

RE: Korrektur
DIESE KORREKTOR BITTE IGNORIEREN!!!

Zitat:

Original von LubTobii
k kann exponentiell sein, jedoch nicht in n. Also $\begin{eqnarray*} 2^k \end{eqnarray*}$ ist in Ordnung, $\begin{eqnarray*} n^k \end{eqnarray*}$ jedoch nicht.

Ich hatte leider Probleme mit meinem ersten Account, habe dann als Gast geschieben und konnte deswegen den Post nicht mehr Rückgängig machen... Sorry Hammer

Also was ich eigentlich meinte:
$\begin{eqnarray*} \epsilon\to 0 \end{eqnarray*}$ für k exponentiell (perfekt, falls k unabhängig von n, ist aber nicht notwendig).

26.11.2018, 23:28

HAL 9000

Auf diesen Beitrag antworten »

Nun, mit $\begin{eqnarray*} k=a\cdot 2^n \end{eqnarray*}$ folgt aus obiger Abschätzung $\begin{eqnarray*} E(Z)\geq n\left(1-e^{-a}\right) \end{eqnarray*}$ .

Zitat:

Original von LubTobii
k kann exponentiell sein, jedoch nicht in n. Also $\begin{eqnarray*} 2^k \end{eqnarray*}$ ist in Ordnung, $\begin{eqnarray*} n^k \end{eqnarray*}$ jedoch nicht.

Verstehe ich nicht: $\begin{eqnarray*} k \end{eqnarray*}$ wie $\begin{eqnarray*} 2^k \end{eqnarray*}$ oder $\begin{eqnarray*} n^k \end{eqnarray*}$ - was soll dieser "Selbstbezug" (k vs. k) bedeuten, macht für mich keinen Sinn. unglücklich

27.11.2018, 00:24

LubTobii

Auf diesen Beitrag antworten »

Danke schonmal dafür! Ich habe mich da mit den k's etwas verzettelt.. Sorry.

Wenn k nur polynomiell beschränkt ist, kann man dann ein $\begin{eqnarray*} \alpha \end{eqnarray*}$ finden, s.d.
$\begin{eqnarray*} E(Z) \geq n(1-\alpha) \end{eqnarray*}$

27.11.2018, 09:18

HAL 9000

Auf diesen Beitrag antworten »

Mir ist immer noch nicht ganz klar, in welche Richtung das gehen soll: Bezeichnen wir $\begin{eqnarray*} f(n,k) = n - \frac{1}{2^{nk}}\sum_{i=1}^n \left( \sum_{j=0}^{i-1} \binom{n}{j} \right)^k \end{eqnarray*}$ , dann ist Funktion $\begin{eqnarray*} f \end{eqnarray*}$ sowohl in $\begin{eqnarray*} n \end{eqnarray*}$ als auch $\begin{eqnarray*} k \end{eqnarray*}$ streng monoton wachsend. Das sieht man der Formel vielleicht nicht unmittelbar algebraisch an, aber ist aus ihrer inhaltlichen Bedeutung als $\begin{eqnarray*} E(Z) \end{eqnarray*}$ klar.

Wenn du nun eine Abschätzung für $\begin{eqnarray*} f(n,k) \end{eqnarray*}$ für festes $\begin{eqnarray*} n \end{eqnarray*}$ nach unten haben willst und dabei aber $\begin{eqnarray*} k \end{eqnarray*}$ nur nach oben beschränkt ist, dann ist doch zwangsläufig keine bessere Schranke möglich als

$\begin{eqnarray*} f(n,k)\geq f(n,1) = \frac{n}{2} \end{eqnarray*}$ .

Das entspricht natürlich deinem Wunsch $\begin{eqnarray*} n(1-\alpha) \end{eqnarray*}$ mit $\begin{eqnarray*} \alpha=\frac{1}{2} \end{eqnarray*}$ , ist aber völlig unabhängig vom Wachstum von $\begin{eqnarray*} k \end{eqnarray*}$ . Und mehr ist dann aber auch nicht drin! D.h., wenn du also etwa $\begin{eqnarray*} n(1-\alpha) \end{eqnarray*}$ mit vorgegebenen $\begin{eqnarray*} \alpha < \frac{1}{2} \end{eqnarray*}$ für "genügend große" $\begin{eqnarray*} n \end{eqnarray*}$ haben willst, dann brauchst du kein Höchst- sondern ein Mindestwachstum von $\begin{eqnarray*} k=k(n) \end{eqnarray*}$ . verwirrt

28.11.2018, 14:06

LubTobi

Auf diesen Beitrag antworten »

Ich hätte gerne, dass k durch eine polynomielle Funktion beschänkt ist und dass $\begin{eqnarray*} \alpha \end{eqnarray*}$ möglichst klein gewählt werden kann, s.d. $\begin{eqnarray*} E(Z)\geq n(1-\alpha) \end{eqnarray*}$ . Wenn dies nicht möglich ist, dann wäre auch sowas wie $\begin{eqnarray*} k=n^\alpha \end{eqnarray*}$ in Ordnung.

Warum soll es keine bessere Abschätzung geben?

Zitat:

Original von HAL 9000
Wenn du nun eine Abschätzung für $\begin{eqnarray*} f(n,k) \end{eqnarray*}$ für festes $\begin{eqnarray*} n \end{eqnarray*}$ nach unten haben willst und dabei aber $\begin{eqnarray*} k \end{eqnarray*}$ nur nach oben beschränkt ist, dann ist doch zwangsläufig keine bessere Schranke möglich als

$\begin{eqnarray*} f(n,k)\geq f(n,1) = \frac{n}{2} \end{eqnarray*}$ .

28.11.2018, 14:49

HAL 9000

Auf diesen Beitrag antworten »

"beschränkt" ohne nähere Erläuterung heißt für mich "nach oben beschränkt". Dies ohne Attribute als "von unten beschränkt" zu deuten wirkt auf mich reichlich merkwürdig...

Die Funktion $\begin{eqnarray*} k(n)=1 \end{eqnarray*}$ ist für mich in dem Sinne auf jeden Fall auch polynomial $\begin{eqnarray*} n^{\alpha} \end{eqnarray*}$ beschränkt, und es ist nun mal $\begin{eqnarray*} f(n,1)=\frac{n}{2} \end{eqnarray*}$ . Was ist daran denn nicht deutlich genug? verwirrt

Neue Frage »

Antworten »

Erwartungswert vom Maximum von Zufallsvariablen (Summe von Ereignissen)

Verwandte Themen