Wie Beweise ich das E[ |summe(e_i)| ] <= sqrt(m) ist, wobei e_1,...,e_m iid. mit P(e_i=-1)=1/2=P(e_i=1)?

Um die Ungleichung E[ |∑(e_i)| ] ≤ √m zu beweisen, wobei e_1, ..., e_m unabhängige und identisch verteilte Zufallsvariablen mit P(e_i = -1) = 1/2 = P(e_i = 1) sind, kannst du die Ungleichung von Markov verwenden.

Die Markov-Ungleichung besagt:

P(|X| ≥ a) ≤ E[|X|] / a

In diesem Fall ist X die Zufallsvariable ∑(e_i), und a ist √m. Jetzt kannst du die Markov-Ungleichung auf die gegebene Ungleichung anwenden:

P(|∑(e_i)| ≥ √m) ≤ E[|∑(e_i)|] / √m

Da |∑(e_i)| immer positiv ist, kannst du es sicher durch E[|∑(e_i)|] / √m ersetzen:

P(∑(e_i) ≥ √m) ≤ E[|∑(e_i)|] / √m

Da e_1, ..., e_m unabhängig und identisch verteilt sind, ist E[∑(e_i)] = m * E[e_i]. Da E[e_i] = 1/2 * (-1) + 1/2 * 1 = 0, ergibt sich E[∑(e_i)] = 0.

Jetzt kannst du die Ungleichung weiter vereinfachen:

P(∑(e_i) ≥ √m) ≤ 0 / √m

Da der Erwartungswert von ∑(e_i) 0 ist, ist die Wahrscheinlichkeit, dass ∑(e_i) größer oder gleich √m ist, gleich Null. Das bedeutet, dass E[|∑(e_i)|] ≤ √m bewiesen ist.