vorlesung01.tex

\part{Einführung / Organisatorisches}
\label{sec:EinführungOrganisatorisches}

\par Die Klausur wird am \textbf{01.02.2010 von 9:15 - 10:45} stattfinden, es wird wöchentliche Haus- und Stundenübungen geben.\\
Die abgegebenen Hausübungen werden korrigiert und in den Übungsgruppen zurückgegeben werden, es gibt allerdings keine Bonuspunkteregelung.
Übungsgruppen wird es folgende geben:
\begin{itemize}
	\item Mo, 12:15 - 13:00 Uhr (F309)
	\item Mo, 14:15 - 15:00 Uhr (G123) [max. 20 Teilnehmer]
	\item Di, 10:15 - 11:00 Uhr (F428)
	\item Di, 12:15 - 13:00 (F442)
	\item Mi, 12:15 - 13:00 (B305)
\end{itemize}

\section{Literatur}

\par Der Dozent empfiehlt das Buch ``Stochastik für Einsteiger'' von Herrn N. Henze (Vieweg Verlag)

\par Leider richtet sich das oben genannte Buch primär an Mathematiker. Im selben Verlag ist ein Buch für Informatiker erschienen.

\subsection{Referenzen}

Im Folgenden werden ich, wenn möglich, beide Quellen referenzieren.

\newpage

\part{Grundlegende Wahrscheinlichkeitstheorie}
\label{sec:Wahrscheinlichkeitstheorie}

"`Was ist das richtige Modell, um ein Experiment zu beschreiben?"' ist die wichtigste Frage, die die mathematische Statistik zu beantworten hat, und diese Modelle an die Wirklichkeit anzupassen, ist die hauptsächliche Aufgabe der Stochastik. Der letzte Teil wird vor allem in der Vorlesung \textbf{Stochastik B} behandelt.

\section{Wahrscheinlichkeitsräume}
\label{sec:Wahrscheinlichkeitsräume}

Zufallsexperimente werden beschrieben durch \href{http://de.wikipedia.org/wiki/Wahrscheinlichkeitsraum}{\textbf{Wahrscheinlichkeitsäume}}. Ein Wahrscheinlichkeitsraum ist ein Tripel $(\Omega,\mathfrak{A},P)$ und setzt sich wie folgt zusammen.

\subsection{Die Ergebnismenge $\Omega$}
Die Menge der möglichen Ergebnisse heißt $\Omega$ (\cite[S. 12]{Huebner09}).\\
Im \textbf{Würfelwurf} sei beispielsweise $\Omega := \{1,2,3,4,5,6\}$

\subsection{Der Ereignisraum $\mathfrak{A}$}

die Menge $\mathfrak{A}$ $\subset \mathfrak{P}(\Omega) \footnote{Potenzmenge} :=\{A; A\subset\Omega\}$ als Menge der interessierenden Ergebnisse (\cite[S. 14]{Huebner09}).\\
	$\mathfrak{A}$ ist eine so genannte \href{http://de.wikipedia.org/wiki/Sigma-Algebra}{$\sigma$-Algebra} auf $\Omega$, d.h. 
	\begin{enumerate}
	\item 
	\begin{equation}
	\Omega \in \mathfrak{A}
	\end{equation}
	(Die Grundmenge $\Omega$ ist in $\mathfrak{A}$ enthalten)
	\item 
	\begin{equation}
		A \in \mathfrak{A} \iff A^c \in \mathfrak{A}
	\end{equation}
	(Wenn $\mathfrak{A}$ eine Teilmenge $A\in\Omega$ als mögliches Ergebnis enthält, dann auch deren Komplement $A^c=\Omega \setminus A$)
	\item 
	\begin{equation}
		A_1,A_2,\dots\in \mathfrak{A} \Rightarrow \bigcup_{n=1}^{\infty}A_n\in \mathfrak{A}
	\end{equation}
	(Wenn für jede natürliche Zahl $n$ die Menge $A_n \in \mathfrak{A}$ ist, so ist auch die abzählbare Vereinigung aller $A_n\in\mathfrak{A}$)
\end{enumerate}

\par\noindent	Im \textbf{Würfelwurf} seien beispielsweise gültige Ereignisse:
	\begin{itemize}
	\item $A := \{2,4,6\}$ das Ereignis "`Es fällt eine gerade Zahl"', und
	\item $A := \{5,6\}$ das Ereignis "`Es fällt eine Zahl grö\ss er gleich 5"'.
\end{itemize}

\subsubsection{Rechnen mit Ereignissen}

\par\noindent Wenn nun $A,B \in \mathfrak{A}$, dann gilt (\cite[S. 15]{Huebner09})
\begin{itemize}
	\item \[A\cup B = A\cup B \cup \emptyset \cup \emptyset \cup \dots \in \mathfrak{A}\]
	(Die Vereinigung von $A,B$ ist auch ein interessierendes Ereignis und steht f\"ur ``das Ereignis $A$ oder $B$ treten ein'')
	\item \[A\cap B = A\cap B \cap \Omega \cap \Omega \cap \dots \in \mathfrak{A}\]
	(Die Schnittmenge von $A,B$ ist auch ein interessierendes Ereignis und steht f\"ur ``das Ereignis $A$ \textbf{und} $B$ treten ein'')
	\item \[A \Delta B = (A\cap B^c) \cup (B\cap A^c)\]
	(Die ``symmetrische Differenz'' beschreibt das Ereignis ``Entweder A oder B'')
	\item $A \subseteq B$ hei{\ss}t: ``Das Ereignis A hat das Ereignis B zur Folge''.\\
	(Kurz erkl\"art: Wenn $A$ eintritt, folgt $\omega \in A\ \wedge\ A \subseteq B \Rightarrow \omega \in B$)
\end{itemize}

\subsection{Das Wahrscheinlichkeitsmaß $P$}

durch ein \href{http://de.wikipedia.org/wiki/Wahrscheinlichkeitsmass}{Wahrscheinlichkeitsma\ss}\ $P$ (lat: "`\textbf{P}robabilitas"'=Glaubwürdigkeit) mit \linebreak[4] $P:\mathfrak{A} \rightarrow [0,1]$, also eine Mengenfunktion auf $\mathfrak{A}$ mit den Eigenschaften
	\begin{enumerate}
	\item \begin{equation}
		P(\Omega)=1
	\end{equation}
	\textit{(Die so genannte ``Normiertheit'').}
	\item Für jede Folge von \textbf{paarweise disjunkten} $A_1,A_2,\dots\in \mathfrak{A}$ gilt:
	\begin{equation}
		P\left(\bigcup_{n=1}^{\infty}A_n\right)=\sum_{n=1}^{\infty}{P(A_n)}
	\end{equation}
	\[\sigma\text{-Additivität von }P\]
	\noindent Für $A\in \mathfrak{A}$ ist $P(A)$ die Wahrscheinlichkeitsfunktion (für das Eintreten) des Ereignisses $A$.
\end{enumerate}

\subsubsection{Eigenschaften von Wahrscheinlichkeits-Ma{\ss}en}

\begin{itemize}
	\item Aus $P(\emptyset)=P(\emptyset\cup\emptyset\cup\dots)=\sum_{n=1}^{\infty}{P(\emptyset)}$ folgt $P(\emptyset)=0$.
	\item Für $A,B\in \mathfrak{A}$ mit $A\subseteq B$ ist 
	\begin{equation}
P(B)=P(A \cup B \cap A^c)=P(A \cup B \cap A^c \cup \emptyset \cup \dots)=P(A)+P(B \cap A^c) \geq P(A)
\end{equation}
	Also gelten folgende Eigenschaften / Gesetzm\"a{\ss}igkeiten:
	\begin{itemize}
	\item \begin{equation}
		P(A)\leq P(B)
	\end{equation}
	(Isotonie)
	\item \begin{equation}
		P(B \cap A^c)=P(B)-P(A)
	\end{equation}
	(Subtraktivität)
\end{itemize}
\end{itemize}

\subsection{Ergebnisse von Zufallsexperimenten}

\par\noindent $\omega\in\Omega$ nennen wir das Ergebnis des Zufallsexperimentes. Das Ereignis $A\in \mathfrak{A}$ tritt genau dann ein, wenn $\omega\in A$.
\begin{equation}
\label{ }
\omega\in\bigcup_{n=1}^{\infty}A_n \iff \exists n\in \mathbb{N} \wedge \omega\in A_n
\end{equation}
Das durch $\bigcup_{n=1}^{\infty}A_n$ beschriebene Ereignis tritt genau dann ein, wenn mindestens eines der Ereignisse $A_n,\ n\in \mathbb{N}$ eintritt.

\noindent Auf die Frage, ob auch $\emptyset$ eine gültige Menge ist, sei gesagt, dass \[\emptyset =\Omega^c \in \mathfrak{A}\] das "`unmögliche Ereignis"' genannt wird (Die Antwort ist also ``ja'').\\

\noindent Seien $A_1,A_2,\ldots \in \mathfrak{A}$. Dann 
\begin{equation}
\bigcap_{n=1}^{\infty}{A_n}=\left(\bigcup_{n=1}^{\infty}A_n^c\right)^c\in \mathfrak{A}
\end{equation}
Anmerkung: $\bigcap_{n=1}^{\infty}A_n$ tritt genau dann ein, wenn alle $A_n,n\in \mathbb{N}$ eintreten.\\

\subsection{Beispiel}

$\emptyset \neq \Omega$ sei endlich, $|\Omega|$ Anzahl der Elemente von $\Omega$ und $\mathfrak{A}=\mathfrak{P}(\Omega)$.\\
Sei $P$ definiert durch 
\begin{equation}
P(A)=\frac{|A|}{|\Omega|},\ A \subset \Omega
\end{equation}
$P$ hei\ss t "`diskretes Laplace'sches W-Ma\ss "` auf $\Omega$.\\
Es ist 
\begin{equation}
P(\{\omega\})=\frac{1}{|\Omega|},\ \omega\in\Omega
\end{equation}
also folgert man: "`Alle möglichen Ergebnisse sind \textbf{gleich wahrscheinlich}."'

\newpage

\section{Grundformeln der Kombinatorik}
\label{sec:Grundformeln der Kombinatorik}

$n,r\in \mathbb{N}$, $M_n$ ist eine $n$-elementige Menge, o.B.d.A. $M_n=\{1,\ldots,n\}$.
\begin{itemize}
	\item 
	\begin{equation}
P_n^{r}=\{(x_1,\dots,x_r);\ x_i \in M_n, 1 \leq i \leq r\}
\end{equation}
	das sind die $r$-\href{http://de.wikipedia.org/wiki/Permutation}{Permutationen} aus $M_n$ mit Wiederholung.
	\item 
	\begin{equation}
	P_n^{(r)}=\{(x_1,\dots,x_r);\ x_i \in M_n, 1 \leq i \leq r, \text{paarweise\ verschieden}\}\ (r \leq n)
\end{equation}
	das sind die $r$-Permutationen aus $M_n$ ohne Wiederholung.
	\item 
	\begin{equation}K_n^{(r)}=\{(x_1,\dots,x_r);\ x_i \in M_n, 1 \leq i \leq r,\ x_1 < x_2 < \dots < x_n\}\ (r \leq n)
\end{equation}
	das sind die $r$-Kombinationen aus $M_n$ ohne Wiederholung.
	\item 
	\begin{equation}K_n^{r}=\{(x_1,\dots,x_r);\ x_i \in M_n, 1 \leq i \leq r,\ x_1 \leq x_2 \leq \dots \leq x_n\}\ (r \leq n)
\end{equation}
	das sind die $r$-Kombinationen aus $M_n$ mit Wiederholung.
\end{itemize}

\subsection{Zur Erkl\"arung}
\begin{enumerate}
	\item Tupel in Permutationen sind nicht angeordnet, hier ist die Reihenfolge wichtig!
  \item Tupel in Kombinationen sind o.B.d.A. angeordnet, wir k\"onnen sie also ``vergleichen''.
  \item Bei Varianten \textbf{mit Wiederholung}, d\"urfen also zwei Elemente ``nebeneinander'' auch gleich sein, bei Varianten \textbf{ohne Wiederholung} ist das nicht der Fall, hier m\"ussen die Elemente also echt unterschiedlich sein.
  \item Bei einer $r$-Kombination haben wir eine $r$-elementige Teilmenge (die also kleiner oder gleich gro{\ss} der ``gro{\ss}en'' Menge $M_n$ ist).
  \item ``mit Wiederholung'' nennt man auch ``mit Zur\"ucklegen''
\end{enumerate}

\subsection{Anschauliche Beispiele}
\begin{itemize}
	\item Bei Kombinationen interessiert uns ausschließlich, welche Elemente wir aus $M_n$ bekommen, ein gutes Beispiel für eine Kombination
	\begin{description}
	\item[ohne Wiederholung] ist also das übliche Lotto-Spiel ``6 aus 49''. Hier ist es uns egal, ob die Reihenfolge $(1,2,3,4,5,6)$ ist oder $(6,5,4,3,2,1)$.
	\item[mit Wiederholung] ist die Frage, ob wir mindestens zwei Mal in fünf Versuchen eine Zahl $\geq 5$ würfeln %% TODO Urnenmodell
\end{description}
	\item Bei Permutationen interessiert uns neben der Auswahl auch die Anordnung (man sagt: die Elemente sind ``unterscheidbar''). Eine Permutation
	\begin{description}
	\item[ohne Wiederholung] ist z.B. ein Kinobesuch. Ob Tim zwischen Tina und Claudia sitzt, ist für ihn nicht gleichwertig mit der Variante, zwischen Klaus und Jochen zu sitzen.\\
	Anders ausgedrückt gilt in Permutationen \[(Claudia,Tim,Tina,Klaus,Jochen) \neq (Claudia,Tina,Klaus,Tim,Jochen)\]
	\item[mit Wiederholung] ist die Frage, ob ich beim Roulette einen aufsteigenden Run habe, also erst eine $0$ fällt, dann eine $1$, dann eine $2$, usw. Das Standardbeispiel hierbei ist eine Urne, wo ich Kugeln oder Zettel heraushole und wieder hereinlege.\\
	Eine Permutation mit Wiederholung ist also eine ``Auswahl mit Wiederholungen unter Beachtung der Reihenfolge''.
\end{description}
\end{itemize}

%\subsection{Rechnen mit Permutationen und Kombinationen}
\subsection{Rechenbeispiele}
Es gilt
\begin{itemize}
	\item 
	\begin{equation}
		|P_n^r|=n^r
	\end{equation}
	\textit{(Erklärung: Man greift $r$ Mal in die Urne, schaut sich einen der $n$ Zettel an und legt ihn wieder herein, es gibt also danach genauso viele Möglichkeiten zu ziehen (also $n$))}
	\item
	\begin{equation}
		|P_n^{(r)}|=
		\begin{cases}
		r\leq n\ 	& n\cdot(n-1)\cdot\ldots\cdot(n-r+1) \\[0.5em]
		r=n\ 			& r!
		\end{cases}
	\end{equation}
	\textit{(Erklärung: Lege ich meine Zettel nicht wieder in die Urne zurück, habe ich beim nächsten Versuch natürlich eine Möglichkeit weniger, welche Zettel ich ziehen könnte)}
	\item 
	\begin{align}
		r!\cdot|K_n^{(r)}|	&=|P_n^{(r)}| \label{lab2.3.1}\\
												& \Updownarrow \nonumber \\
		|K_n^{(r)}|					&=\frac{n(n-1)\dots(n-r+1)}{r!}	&=\binom{n}{r} \label{lab2.3.2}\\
												& \Downarrow \nonumber \\
		&|\{A; A\subset M_n, |A|=r\}|&=\binom{n}{r} \label{lab2.3.3} \\
												& \Downarrow \nonumber \\
		|\mathfrak{P}(M_n)|	&=\sum_{r=0}^{r}{\binom{n}{r}1^r1^{n-r}}=(1+1)^n &=2^n \label{lab2.3.4}
	\end{align}
	\eqref{lab2.3.3} Gilt auch noch für $r=0$.\\
	\textit{Erklärungen:\\
	\eqref{lab2.3.1} und äquivalent \eqref{lab2.3.2} kann man sich so vorstellen, dass man sich seine $r$-elementige Teilmenge (ohne Zurücklegen) zusammensuchen kann, aber die verschiedenen Möglichkeiten, sie zu permutieren (``die Kinobesucher umzusetzen''), interessieren den Betrachter hier nicht, also müssen wir die aus der Rechnung rausnehmen.\\
	\eqref{lab2.3.3} ist die Anzahl aller $r$-elementigen Teilmengen von $M_n$ hoch $r$, und wegen \eqref{lab2.3.2} ebenfalls $\binom{n}{r}$.\\
	\eqref{lab2.3.4} ist die Länge der Potenzmenge, also aller möglichen Teilmengen von Elementen aus $M_n$}
	\item $K_n^r \rightarrow (x_1,\dots,x_r) \underbrace{\longrightarrow}_{ist\ bijektiv} (x_1,x_1+1,\dots,x_r+r-1)\in K_{n+r-1}^{(r)}$\\
	$\Rightarrow |K_n^r| = |K_{n+r-1}^{(r)}| = \binom{n+r-1}{r}$\\
	Identifiziere $(x_1,\dots,x_r) \in K_n^r$ mit dem Besetzungszahlvektor $(k_1,\dots,k_n)$,
	wobei $k_i=|\{j\in \{ 1,\dots,r \}; x_j=i\}|,\ 1 \leq i \leq n$. Dann ist $k_1+\ldots+k_n=r$.\\
	Dann ist $|\{(k_1,\dots,k_n)\in \mathbb{N}_0^n; k_1+\dots+k_n=r\}|=\binom{n+r-1}{r}$\\
	Folgerung: $|\{(k_1,\dots,k_n)\in \mathbb{N}^n; k_1+\dots+k_n=r\}|=\binom{n+(r-n)-1}{r-n}=\binom{r-1}{r-n}=\binom{r-1}{n-1}, r \geq n$\\
\end{itemize}