\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\noindent §66: ABSCHÄTZUNGEN FÜR ABWEICHUNG VOM ERWARTUNGSWERT \\[0.8cm]
66.1 Motivation: \\
Mit der Varianz bzw. Standardabweichung  kennen wir bereits ein Maß f+r die Fluktuation einer Zufallsvariablen um ihren Erwartungswert. \\
Gibt es weitere nützliche Maßzahlen hierfür? \\
Ist es möglich, Abschätzungen zu finden, die wahrscheinlichkeitstheoretische Aussagen darüber liefern, wie häufig eine Zufallsvariable außerhalb eines Intervalls um den Erwartungswert liegt. \\[0.5cm]
66.2 Def.: \\
Sei $X$ eine Zufallsvariable mit Erwartungswert $\mu = E(X)$. Dann bezeichnen wir mit $E(X^k), k \in \SetN$ das $k$-te Moment von $X$. Ferner definiert man das $k$-te zentrale Moment von $X$ als $E((X-\mu)^k)$. \\[0.5cm]
66.3 Bemerkungen:
\begin{enumerate}[(a)]
	\item Der Erwartungswert $\mu = E(X)$ ist das erste Moment.
	\item Die Varianz $\sigma^2=E((X-\mu)^2)$ ist das zweite zentrale Moment.
	\item Mit dem 3. und 4. zentralen Moment lassen sich Aussagen über die Schiefe bzw. Flachheit der Verteilung einer Zufallsvariablen gewinnen
	\item Höhere Momente sind anschaulich schwieriger zu interpretieren, liefern jedoch ebenfalls wichtige Aussagen.
	\item Momente haben eine große Bedeutung in der Mustererkennung bei der Analyse von Texturen und der Erkennung von Objekten unter Rotationen und Skalierungen.
\end{enumerate}
Ähnlich wie wir die Menge aller $k$-Permutationen und $k$-Kombinationen einer $n$-elementigen Menge durch den Begriff der erzeugenden Funktion kompakt beschreiben konnten, gibt es eine Funktion die sämtliche Momente einer Zufallsvariablen beinhaltet: \\[0.5cm]
66.4 Def.: \\
Sei $X$ eine Zufallsvariable. Falls $M_X(\Theta) := E(e^{\Theta X})$ existiert, nennen wir $M_X(\Theta)$ die Momenten erzeugende Funktion von $X$. \\[0.5cm]
66.5 Satz: (Eigenschaften Momenten erzeugender Funktionen) \\
Die Momenten erzeugende Funktion $M_X(\Theta) = E(e^{\Theta X})$ einer Zufallsvariablen $X$ hat folgende Eigenschaften:
\begin{enumerate}[(a)]
	\item Die $n$-te Abteilung in $\Theta=0$ liefert das $n$-te Moment:
		$$M_X^n(0) = E(X^n)$$
	\item Skalierungsverhalten: \\
		Sei $Y=aX+b$. Dann ist
		$$M_Y(\Theta) = e^{b \Theta} M_X(a\Theta)$$
	\item $M_{X+Y}(\Theta) = M_X(\Theta) \cdot M_Y(\Theta)$, falls $X$ und $Y$ unabhängige Zufallsvariablen sind.
\end{enumerate}
Beweis von (a): \\
Mit der Potenzreihenentwicklung der Exponentialfunktion und der Linearität des Erwartungswerts gilt:
$$M_X(\Theta) = E(e^{\Theta X}) = E\left(\sum_{k=0}^\infty \frac{\Theta^k X^k}{k!}\right) = \sum_{k=0}^\infty \frac{\Theta^k}{k!} E(X^k)$$
Gliedweise Differentiation liefert:
\begin{eqnarray*}
	M_X'(\Theta) & = & \sum_{k=1}^\infty \frac{\Theta^{k-1}}{(k-1)!} E(X^k) = \sum_{k=0}^\infty \frac{\Theta^k}{k!} E(X^{k+1}) \\
	\vdots & & \\
	M_X^{(n)}(\Theta) & = & \sum_{k=0}^\infty \frac{\Theta^k}{k!} E(X^{k+n})
\end{eqnarray*}
und somit
$$M_X^{(n)} (0) = E(X^n)$$ \QED \\
Wir kommen nun zu den Abschätzungen für Fluktuationen jenseits eines vorgegebenen Abstands um den Erwartungswert einer Zufallsvariablen. Grundlegend ist der folgende Satz: \\[0.5cm]
66.6 Satz: (Markow'sche Ungleichung) \\
Sei $X$ eine Zufallsvariable und $h: \SetR \to \SetR$ eine nicht negative und nichtfallende Funktion mit $h(t) > 0$ für ein $t$.
$$P(X \ge t) \le \frac{E(h(X))}{h(t)}$$
Beweis: (für eine diskrete Zufallsvariable) \\
Nach Def. 65.7 gilt:
\begin{eqnarray*}
	E(h(X)) & = & \sum_{z \in X(\Omega)} \underbrace{h(z)}_{\ge 0} \underbrace{P_X(z)}_{\ge 0} \\
	& \stackrel{\text{Nichtnegativität}}{\ge} & \sum_{z \in X(\Omega), z \ge t} h(z) P_X(z) \\
	& \stackrel{\text{Nichtfallend}}{\ge} & \underbrace{h(t)}_{>0} \underbrace{\sum_{z \in X(\Omega), z \ge t} P_X(z)}_{P(X \ge t)}
\end{eqnarray*}
$$\Rightarrow P(X \ge t) \le \frac{E(h(X))}{h(t)}$$ \QED \\[0.5cm]
66.7 Folgerungen
\begin{enumerate}[(a)]
	\item Setzt man $h(x) = \left\{\begin{array}{cl}X & (x>0) \\ 0 & (\text{sonst})\end{array}\right.$ folgt die einfache Markow-Ungleichung
		$$P(X \ge t) = \frac{E(X)}{t} \quad (t>0)$$
	\item Mit $Y:=(X-E(X))^2$ und $h(x) = x$ für $x>0$ kann man die Tschebyschew-Ungleichung für den Erwartungswert $\mu$ und die Standardabweichung $\sigma$ von $X$ beweisen:
		$$P(|X-\mu| \ge t) \le \frac{\sigma^2}{t^2}$$
		Alternativschreibweise:
		$$P(|X-\mu| \ge c \cdot \sigma) \le \frac{1}{c^2}$$
	\item Mit $h(x) = e^{\Theta x}$ für $\Theta \ge 0$ ergibt sich:
		$$P(X \ge t) \le e^{-\Theta t} M_X(\Theta)$$
		Da $\Theta \ge 0$ beliebig war, führt dies zur Chernoff-Schranke
		$$P(X \ge t) \le \inf_{\Theta \ge 0} e^{-\Theta t} M_X(\Theta)$$
\end{enumerate}
Bemerkung: \\
Für die einfache Markow-Ungleichung benötigt man das erste Moment ($\mu$), für die Tschebyschew-Ungleichung die ersten beide Momente ($\mu$, $\sigma^2$) und für die Chernoff-Ungleichung alle Momente (die Momenten erzeugende Funktion). Je mehr Momente man kennt, desto mehr weiß man über die Verteilung von $X$ und desto schärfere Abschätzungen kann man erwarten. \\[0.5cm]
66.8 Beispiel: \\
Eine faire Münze werde $n$ Mal geworfen. Tritt beim $k$-ten Wurf Kopf auf, setzt man $Y_k:=1$, sonst $Y_k:=0$. Wir interessieren uns für die \glqq Kopfhäufigkeit \grqq\ nach $n$ Würfen:
$$X_n := Y_1 + ... + Y_n$$
$Y_1,...,Y_n$ sind unabhängige Zufallsvariablen. Es gilt:
\begin{eqnarray*}
	\mu & = & E(X_n) = \frac{n}{2} \\
	\sigma^2 & = & E((X_n - \mu)^2) \\
	& = & \sum_{k=1}^n \left[\left(0-\frac{1}{2}\right)^2 \cdot \frac{1}{2} + \left(1-\frac{1}{2}\right)^2 \cdot \frac{1}{2}\right] \\
	& = & \frac{n}{4}
\end{eqnarray*}
und wegen
$$M_{Y_k}(\Theta) = E\left(e^{\Theta Y_k}\right) = e^{\Theta \cdot 0} \cdot \frac{1}{2} + e^{\Theta \cdot 1} \cdot \frac{1}{2} = \frac{1+e^\Theta}{2}$$
folgt mit 66.5 (c):
$$M_{X_n}(\Theta) = M_{Y_1 + ... + Y_n}(\Theta) = \left(\frac{1+e^\Theta}{2}\right)^n$$
Wie groß ist die Wahrscheinlichkeit, nach $n=100$ Würfen $X_n \ge 80$ zu erhalten? \\
Wir vergleichen die 3 Ungleichungen aus 66.7:
\begin{enumerate}[(a)]
	\item Einfache Markow-Ungleichung \\
		Mit $\mu = 0.5 \cdot 100 = 50$ und $t=80$ ergibt sich
		$$P(X_{100} \ge 80) \le \frac{\mu}{t} = \frac{50}{80} = 0.625$$
	\item Tschebyschew-Ungleichung \\
		Mit $\mu = 50$, $t=30$ und $\sigma^2 = \frac{100}{4} = 25$ ergibt sich
		$$P(X_{100} \ge 80) \le P(|X_{100}-50| \ge 30) \le \frac{\sigma^2}{t^2} = \frac{25}{30^2} \approx 0.028$$
		Obwohl Abweichungen nach beiden Seiten berücksichtigt werden, ist die Abschätzung schärfer als bei der einfachen Markow-Ungleichung.
	\item Chernoff-Schranke \\
		$$P(X_{100} \ge 80) \le \inf_{\Theta \ge 0} \underbrace{e^{-80 \cdot \Theta} \left(\frac{1+e^\Theta}{2}\right)^{100}}_{=: f(\Theta)}$$
		Ableiten ergibt: $f(\Theta)$ wird minimiert für $\Theta = \ln(4)$. Daraus folgt:
		$$P(X_{100} \ge 80) \le 4^{-80} \cdot \left(\frac{1+4}{2}\right)^{100} \approx 4.26 \cdot 10^{-9}$$
		Erwartungsgemäß ist dies eine wesentlich schärfere Schranke als (a) und (b).
\end{enumerate}

\end{document}
