Tschebyscheff- Ungleichung, Hoeffding-Schranke

Question

 Moin moin, zerbreche mir gerade mein Kopf mit dieser Aufgabe:

Es beschreibe \( \left(X_{n}\right) \) die Folge identisch unabhängig verteilter Zufallsvariablen des fairen sechsseitigen Würfelns. Bestimmen Sie
(1) mit Hilfe der Tschebyscheff- Ungleichung
(2) mit Hilfe der Hoeffding-Schranke
eine Abschätzung für die Anzahl der Würfe \( N \in \mathbb{N} \), die mindestens benötigt werden, damit die Wahrscheinlichkeit für das Ereignis \( \left\{N^{-1} \sum \limits_{k=1}^{N} X_{k}<4,6\right\} \) größer als 0,95 ist.

Weiß jemand, wie das geht?

Answer 1

Hallo,

wir verwenden \( E(X_i) = 3.5 \) und \( V(X_i) = \frac{35}{12} \) (siehe https://de.wikipedia.org/wiki/Diskrete_Gleichverteilung).

Die Tschebyscheff-Ungleichung schätzt die Wahrscheinlichkeit zur Abweichung vom Mittelwert ab,

\( P(|X - \mu| \geq c) \leq \frac{\sigma^2}{c^2} \).

Für \( X = \frac{1}{N} \sum_{i=1}^{N} X_i \) ist \( \mu = E(X) = E(X_i) \) und \( V(X) = \frac{V(X_i)}{N} \).

Wir erhalten

\( P(X \geq 4.6) = \frac{1}{2} P(|X - 3.5| \geq 4.6 - 3.5 = 1.1) \)
\( \leq \frac{V(X)}{2 \cdot (1.1)^2} \)
\(= \frac{V(X_i)}{2N \cdot (1.1)^2} \)
\(= \frac{35}{2N \cdot 12 \cdot (1.1)^2} \stackrel{!}{\leq} 0.05 \).

Daraus folgt \( N \geq \frac{35}{2 \cdot 12 \cdot (1.1)^2 \cdot 0.05} \approx 24.1 \).

Die Hoeffding-Ungleichung schätzt die Abweichung einer Summe \( S_N = \sum_{i=1}^N X_i \) von Zufallsvariablen \( X_i \) mit \( a_i \leq X_i \leq b_i \) vom Erwartungswert \( E(S_N) \) dieser Summe ab (vergleiche Abschnitt 3 auf Seite 2 in  http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/03_hoeffding.pdf ),

\( P\left( S_N - E(S_N) \geq t \right) \leq \exp\left( - \frac{2t^2}{\sum_i (b_i - a_i)^2} \right) \).

Für unseren Fall mit \( a_i = 1 \) und \( b_i = 6 \) berechnen wir

\( P( \frac{1}{N}\sum_i X_i \geq 4.6) = P( (\frac{1}{N}\sum_i X_i) - E(\frac{1}{N}\sum_i X_i) \geq 1.1) \)
\( = P( (\sum_i X_i) - E(\sum_i X_i) \geq 1.1N) \)
\( \leq \exp\left( - \frac{2(1.1N)^2}{25 N} \right) \)
\( = \exp\left( - \frac{2N \cdot (1.1)^2}{25} \right) \stackrel{!}{\leq} 0.05 \)

und erhalten

\(  N \geq - \frac{25 \log( 0.05)}{2 \cdot (1.1)^2} \approx 30.95 \).

Grüße

Mister

Comments

Danke dir für deine Hilfe!!!!

---

Vielen Dank!!!

---

Bitteschön! ~~~