\documentclass[a4paper,10pt]{scrartcl} \usepackage{ngerman} \usepackage[utf8]{inputenc} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{graphicx} \usepackage{simplemargins} \setallmargins{0.5cm} \begin{document} \section{Mathematische Grundlagen} \begin{itemize} \item Exponentialfunktion, Euler-Zahl: $e^x = \sum\limits^\infty_{n=0} \frac{x^n}{n!} \qquad e = \lim\limits_{n\rightarrow\infty} (1+\frac{1}{n})^n$ \item Binomische Formel: $(a+b)^n = \sum\limits^n_{k=0}\binom n k a^k b^{n-k} \qquad \binom n k = \frac{n!}{(n-k)!k!} = \binom{n}{n-k}$ \item Gauß: $\sum\limits^n_{i=1} i = \frac{n(n+1)}{2} \qquad \sum\limits^n_{i=1} i^2 = \frac{n(n+1)(2n+1)}{6}$ \item Partielle Integration: $\int_a^b f(x)\cdot g'(x)\,\mathrm{d}x = [f(x)\cdot g(x)]_{a}^{b} - \int_a^b f'(x)\cdot g(x)\,\mathrm{d}x$ \item Geometrische Reihe: $\sum\limits_{k=0}^n q^k = \frac{1-q^{n+1}}{1-q} = \frac{q^{n+1}-1}{q-1} \qquad \sum\limits^\infty_{i=0}q^i = \frac{1}{1-q}$ \item Stirling Formel für Fakultäten: $n! \approx \sqrt{2 \pi n} \; \left(\frac{n}{\mathrm e}\right)^{n}$ \item Ableitungen: $\sin^\prime(x) = \cos(x) \qquad \cos^\prime(x) = -\sin(x)$ \newline $\frac{\mathrm d}{\mathrm dx} \arcsin(ax+b) = \frac{a}{\sqrt{1-(ax+b)^2}} \qquad \frac{\mathrm d}{\mathrm dx} \arccos(ax+b) = - \frac{a}{\sqrt{1 - (ax+b)^2}}$ \item Ableitung der Umkehrfunktion: $(f^{-1})^\prime(x) = \frac{1}{f^\prime(f^{-1}(x))}$ \item Integrationen: $\int\sin(\alpha)\,{\rm d}\alpha=-\cos(\alpha)+C \qquad \int\sin(\alpha)\,{\rm d}\alpha=-\cos(\alpha)+C $ \item \begin{center} \begin{tabular}{lll} & ohne Wiederholung & mit Wiederholung \\ Permutation & $n!$ & $ \frac{n!}{k_1!\dots k_n!} $ \\ Variation & $n(n-1)\dots(n-k+1)$ & $n^k$ \\ Kombination & $\binom n k$ & $ \binom{n+k-1}{k}$ \end{tabular} \end{center} \end{itemize} \section{Wahrscheinlichkeitsrechnung Allgemein} \begin{itemize} \item Kolmogorow: $0 \leq P(A) \leq 1 \quad P(\Omega) = 1 \quad A_i \cap A_j = \emptyset: P(\bigcup\limits^\infty_{i=1} A_i) = \sum\limits_{i=0}^\infty P(A_i)$ \item Siebformel: $P\left(\bigcup\limits_{i=1}^n A_i\right) = \sum\limits_{k=1}^n (-1)^{k+1}\,\sum\limits_{I\subseteq\{1,\dots,n\},|I|=k} P\left(\bigcap\limits_{i\in I}A_i\right)$ \begin{itemize} \item $n = 2: \mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2)$ \item $n = 3: \mathbb{P}(A_1\cup A_2\cup A_3) =\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)\\ -\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)+\mathbb{P}(A_1\cap A_2\cap A_3)$ \end{itemize} \item Bedingte Wahrscheinlichkeit: $P(A|B) = \frac{P(A \cap B)}{P(B)}$ \item unabh. Ereignisse: $P(A\cap B) = P(A)\cdot P(B) \Leftrightarrow P(A|B) = P(A) \Leftrightarrow P(A | \overline{B}) \qquad \forall A, B$ \item Satz der totalen Wahrscheinlichkeit: $P(B) = \sum\limits^\infty_{i=1} P(B|A_i)P(A_i) \quad A_n \hbox{ sind ausschöpfend und disjunkt}$ \item Satz von Bayes: $P(A|B) \; = \; \frac {P(B|A) \cdot P(A)} {P(B)} \qquad P(A_i | B) \; = \; \frac{P(B | A_i) \cdot P(A_i)}{\sum_{j=1} ^{N} P(B | A_j) \cdot P(A_j)} = \; \frac{P(B | A_i) \cdot P(A_i)}{P(B)} \;$ \end{itemize} \section{Zufallsvariablen} \subsection{Allgemeines} \begin{itemize} \item \textbf{Dichtefunktion}, falls $\forall x \in R: f(x) \geq 0$ und $\int\limits_R f(x)dx = 1$ \item bei diskreten ZV heißt $f(x_i) = p_i$ auch \emph{Wahrscheinlichkeitsfunktion} \item \textbf{Verteilungsfunktion} $F_X(x) := P(X < x)$ \item Stetig, wenn Dichtefunktion existiert mit: $F_X(x) = P(X < x) = \int\limits_{-\infty}^x f(x)dx$ \item \textbf{Erwartungswert}: $E(X) = \sum\limits_{i=1}^\infty p_i x_i$ bzw. $E(X) = \int\limits_{-\infty}^{\infty} f(x)\cdot x dx$ \\ der Erwartungswert ist wie ein normaler linearer Operator, $E(c) = c$ \\ $E(g(X)) = \int\limits_{-\infty}^\infty g(x)f(x)dx$ bzw. $\sum\limits_{i=0}^{\infty} g(x_i)p_i$ (Regel des faulen Statistikers, gilt nur für Erwartungswerte) \\ $E(X\cdot Y) = \sum\limits_x \sum\limits_y x\cdot y\cdot P(X=x, Y=y)$ \item p-tes Moment: $E(X^p)$ und p-tes zentrales Moment: $E((X-E(X))^p)$ \item \textbf{Varianz}: $Var(X) = E((X-E(X))^2) = E(X^2)-(E(X))^2$ \\ $Var(X+c) = Var(X), Var(a\cdot X) = a^2\cdot Var(X), Var(X + Y) = Var(X)+Var(Y)+2\cdot cov(X,Y)$ \item \textbf{Covarianz}: $cov(X,Y) = E((X-E(X))(Y-E(Y))) = E(X\cdot Y) - E(X)E(Y)$ \\ Wenn $X$ und $Y$ unabhängig sind, dann ist $cov(X,Y) = 0$. (gilt nicht andersrum!) \item \textbf{Korrelationkoeffizient}: $\rho(X,Y) = \frac{cov(X,Y)}{\sqrt{Var(X)}\cdot\sqrt{Var(Y}}$ (unterstellt lin. ZH!) \item \textbf{Median}: $\inf\{x\in R : F(x) \geq \frac{1}{2}\}$ \item \textbf{Standardisierte ZV}: $E(X) = 0$, $Var(X) = 1$ \end{itemize} \subsection{Diskrete Verteilungen} \begin{itemize} \item Binomial: Anzahl der $i$ Erfolge bei $n$ Versuchen. $X \sim B(p,n)$ \\ $P(X = i) = \binom n k p^k (1-p)^{n-k} \quad F_X(k) = P(X < k)$, $E(X) = n\cdot p \qquad Var(X) = np(1-p)$ \item Geometrisch: Schritte zum 1. Erfolg $X \sim Geo(p) \quad P(X = i) = p(1-p)^{i-1}$ \\ $E(X) = \frac{1}{p} \qquad Var(X) = \frac{1}{p^2} - \frac{1}{p}$ \\ Sie ist \emph{gedächtnislos}: $P(Y > s+t| Y>t) = P(Y > s)$ \item Hypergeom.: N Stück mit n schlechten, Stichprobe von m Stück. \\ Wkeit, dass in Stichprobe x Stück schlecht sind: \\ $P(X = x) = \frac{\binom n x \cdot \binom{N-n}{m-x}}{\binom N m}$, kann für große $N$ als Ziehung ohne Zurücklegen als Binomial modelliert werden. \item Poisson: eingetroffene Kunden, zerfallene Teilchen $X \sim Poi(\lambda) \quad P(X = n) = \frac{\lambda^n}{n!}\cdot e^{-\lambda}$ \\ $E(X) = \lambda$ (mittl. Ankunftsrate) $Var(X) = \lambda$ \\ Die Summe von zwei Poisson ZV = Poisson verteilt mit dem Parameter $\lambda_1 + \lambda_2$ \end{itemize} \subsection{stetige Zufallsvariablen} \begin{itemize} \item 0,1-gleichverteilt: $X \sim R(0,1) \quad F(x) = \{x < 0: 0, 0\leq x < 1: x, x \geq 1: 1 \} \quad f(x) = \{0, 1, 0\}$ \item a,b-gleichverteilt: $X \sim R(a,b) \quad f(x) = \{x < a: 0, a\leq x < b: \frac{1}{b-a}, x > b: 0\}$ \\ $E(X) = \frac{a+b}{2}$ $Var(X) = \frac{(b-a)^2}{12}$ \item Exponentialverteilt: $X \sim Exp(\lambda) \quad F(x) = \{x \geq 0: 1-e^{-\lambda x}, x < 0: 0\} \quad f(x) = \{x \geq 0: \lambda\cdot e^{-\lambda x}, x < 0: 0\}$ \\ $E(X) = \frac{1}{\lambda}$ $Var(X) = \frac{1}{\lambda^2}$ sie ist gedächtnislos \item Normalverteilt: $X \sim N(\mu, \sigma^2) \quad F(x) = \frac{1}{\sqrt{2\pi}\sigma} \int\limits^x_{-\infty}e^{-\frac{1}{2}\left(\frac{t-\mu}{\sigma}\right)^2} dt \quad f(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2}$ \\ $E(X) = \mu$ $Var(X) = \sigma^2$ \item Standardnormal: $\mu = 0, \sigma^2 = 1$ Dichte: $\phi(x) = \frac{1}{\sqrt{2\pi}}\cdot e^{-\frac{x^2}{2}}$ Vert.: $\Phi(x) = \frac{1}{\sqrt{2\pi}}\cdot \int\limits_{-\infty}^{x} e^{-\frac{t^2}{2}} dt$ \\ Werte sind tabellliert, dabei gilt: $\phi(x) = \phi(-x)$ und $\Phi(x) = 1 - \Phi(-x)$ \\ $\alpha$-Quantil: für welches $x$ gilt $\Phi(x) = \alpha$, außerdem $P(a < X < b) = \Phi(b)- \Phi(a)$. \\ Transformation von Normal zu Standard: $\frac{X-\mu}{\sigma}: X \sim N(10,4): P(X < 11) = \Phi(\frac{11-10}{2}$ \end{itemize} \subsection{Besonderes} \begin{itemize} \item Reihensystem: $X = \min X_i$, $Rel = P(X \geq t) = \prod\limits_{i=1}^n P(X_i \geq t) = \prod\limits_{i=1}^n e^{-\lambda_i t}$ \\ $E(X) = \frac{1}{\sum\limits_{i=1}^n \lambda_i}$ \item Parallelsystem: $X = \max X_i$, $Rel = P(X \geq t) = 1 - P(X < t) = 1 - \prod\limits_{i=1}^n P(X_i < t) = 1-(1-e^{-\lambda t})^n$ \\ $E(X) = \frac{1}{\lambda}\sum\limits_{i=1}^n \frac{1}{i}$ \item k-aus-n System: $E(T) = \frac{1}{\lambda}\sum\limits_{i=1}^k \frac{1}{n-i+1}$ \item Transformationsformel: $h(y)= f(g^{-1}(y))\cdot \left| \frac{d}{dy}g^{-1}(y)\right|$ \\ Beispiel: $U \sim R(0,1), X=g(U)=-\frac{1}{\lambda}\ln U$; $g^{-1}$ und $\frac{d}{dx}g^{-1}$ bilden; dann einsetzen; geht auch rückwärts \item Randverteilung: $X=(X_1, X_2) \quad F_{X_1} = \lim\limits_{y\rightarrow\infty} F(x,y) = P(X_1 < x)$ \item unabhängige Variablen erlauben bei der Randdichte die Multiplikation, daher gilt auch: $p_{ij} = p_{i.} \cdot p_{.j}$, ganz unten rechts eine 1, Spalten und Zeilen Summen! \end{itemize} \section{Ungleichungen} \begin{itemize} \item $\min\limits_{c \in R} E(X-c)^2 = Var(X)$ \item Jensen Ungleichung: $g(x)$ konvex: $E(g(X)) \geq g(E(X)) \qquad g(x) = x^2$ ist konvex, $ln(x)$ ist konkav \item Markov Ungleichung: $c > 0: P(|X| > c) \leq \frac{E(|X|)}{c}$ \item Tschebychev Ungleichung: $P(|Y-E(Y)| > \epsilon) \leq \frac{Var(Y)}{\epsilon^2}$ \end{itemize} \section{Grenzwertsätze} \begin{itemize} \item Schwaches Gesetz d. g. Z.: \emph{unkorrelierte ZV}: $\lim\limits_{n\rightarrow\infty} P(|\overline{X_n} - \mu| > \epsilon) = 0$ \item Gesetz der großen Zahlen: ZV id. verteilt und unabhängig: $P(\omega : \lim\limits_{n\rightarrow\infty} \overline{X_n} = \mu) = 1$ \\ Zum Schätzen von Integralen: $E(g(X)) \approx \frac{1}{n}\sum\limits_{i=1}^n g(x_i)$ \item \textbf{Glivenko-Cantelli} $X_i$ unabh. ZV: $P(\lim\limits_{n\rightarrow\infty} \sup\limits_{x \in R} |F_n(x) - F(x) = 0) = 1$ \item \textbf{Zentraler Grenzwertsatz}: $X_i$, unabh. ident. verteilt ($EX_i = \mu, Var(X_i)=\sigma^2$): $\overline{Z_n} = \frac{1}{n}\sum\limits_{i=1}^n X_i$ \\ $Y_n = \sqrt{n}\cdot \frac{\overline{Z_n} - \mu}{\sigma}: \quad \lim\limits_{n\rightarrow\infty} P(Y_n < x) = \Phi(x)$ \item \textbf{Moivre-Laplace}: für großes n kann Binomial durch Normal ersetzt werden (Regel: $np\geq 10$ und $n(1-p) \geq 10$) \\ $X_i \sim Bi(1,p) \quad Z_n = \sum X_i: \lim Z_n \sim N(np, np(1-p)) \qquad P(Z_n < y) \approx \Phi(\frac{y - np}{\sqrt{np(1-p)}})$ \end{itemize} \section{Markoffsche Ketten} \begin{itemize} \item Def: $\{X_t\}_{t\in T}$ ist Familie von ZV, $\forall t: P(X_t \in S) = 1$ heißt \emph{Markov Kette} falls: $P(X_{t+1} = j | X_{t} = i) =: p_{ij}^{(t)}$ \item Anfangsverteilung: $p_i^{(0)} = P(X_0 = i)$ \item Eine Markov-Kette heißt \emph{homogen}, wenn $p_{ij}$ unabh. von $t$ sind! \item Übergangsmatrix: $\begin{pmatrix} p_{11} & p_{12} & p_{13}\\ p_{21} & p_{22} & p_{23} \end{pmatrix}$, Bedingungen: $p_{ij} \geq 0 \qquad \sum\limits_{j} p_{ij} = 1 \forall i \in S$ \item Erreichbarkeit in n-Schritten: $p_{ij}(n) = P(X_{m+n} = j | X_m = i) = P(X_n = j |X_0 = i)$ \item Rekursion nach Chapman Kolmogorov: $M_n = M^n \quad p_{ij}(n) = \sum\limits_{k \in S} p_{ik}(n-m)\cdot p_{kj}(m) = \sum\limits_{k \in S} p_{ik}(n-1)\cdot p_{kj}$ \\ $\Rightarrow P(X_n = j) = \sum\limits_{k} p_{kj}(n)\cdot p_{k}^0$ \item Berechnung der Wahrscheinlichkeiten: $p_j = P(X_n = j), p^T=(p_1, p_2, p_3, \dots): \Rightarrow p = M^{n^T}\cdot p^0, p^T = p^{0^T} \cdot M^n$ \item $j$ ist von $i$ \textbf{erreichbar}, falls $\exists n: p_{ij}(n) > 0$. Bez: $i \rightarrow j$ \item $i$ und $j$ kommunizieren, wenn $i \rightarrow j$ und $j \rightarrow i$. Bez: $i \leftrightarrow j$ (Äq. Rel!) \item \textbf{Unwesentlicher Zustand}: Gibt es für einen Zustand $i$ einen Zustand $j$ und eine Zahl $n$, \\ so dass $p_{ij}(n) > 0$, aber $p_{ji}(m) = 0 (\forall m)$, so heißt $i$ unwesentlich \item \textbf{absorbierender Zustand}: wenn Äquivalenzklasse nur aus einem Zustand besteht \item Eine MK heißt \textbf{irreduzibel}, wenn der Zustandsraum aus genau 1 Klasse wesentlicher Zustände besteht! \item $f_i(n)$ ist die Wahrscheinlichkeit, nach n Schritten erstmalig wieder den Zustand $i$ zu erreichen \\ ($f_i(0) = 0, f_i(1) = p_{ii}$) \item $F_i := \sum\limits_{j=1}^\infty f_i(j)$ (Wkeit i-wann in den Zustand i zurückzukehren). \\ Ein Zustand heißt \textbf{rekurrent}, wenn $F_i = 1$. Ist $F_i < 1$ so heißt er \textbf{transient}. \item Zustand rekurrent: er wird unendlich oft mit Wkeit 1 erreicht. \item Zustand transient: er kann höchstens endlich oft erreicht werden \item Ein Zustand ist g.d. rekurrent, wenn $\sum\limits_{n=0}^\infty p_{ii}(n) = \infty$. Er ist transient, wenn $< \infty$ \item Ist ein Zustand i rekurrent (transient) und kommuniziert er mit einem Zustand j, so ist auch j rekurrent (transient). \item Eine irreduz. MK mit endlich vielen Zuständen, hat nur rekurrente Zustände. \item Ein Zustand heißt \textbf{periodisch} mit Periode $d$, falls $d$ ggT aller $n$ ist, für die $p_{ii}(n) > 0$. ($d=1$ aperiodisch). \\ Falls $\forall n: p_{ii}(n)=0$, so setzen wir $d = \infty$ \item $i$ periodischer Zstd. mit Periode $d$ und kommuniziert mit $j$, so hat $j$ auch Periode $d$. \item $\mu_i$ = erwartete Rückkehrzeit. $\mu_i < \infty \rightarrow$ positiv rekurrent, $\mu_i = \infty \rightarrow$ null-rekurrent \item MK heißt \textbf{ergodisch}, falls nur pos. rekurrente und aperiodische Zustände \item Anzahl der EW der Übergangsmatrix = Anzahl der rek. Äq.-Klassen \end{itemize} \section{Zufallszahlen} \begin{itemize} \item Manuell: Dezimalstellen würfeln, Binärdarstellung per Münzwurf, 10er Würfel für Dezimalstellen, Rauschen \item Kongruenzmethoden: $z_{i+1} := (a \cdot z_i + r) mod m$, Normierung: $u_i = \frac{z_i}{m}$. \item Die lin. Kongruenzmethode besitzt genau dann die volle Periodenlänge, wenn: \begin{enumerate} \item $ggT(r,m) = 1, (ggT(0,m):= m)$ \item $a mod p = 1$ für alle Primfaktoren p von m \item $a mod 4 = 1$, falls m ein Vielfaches von 4 ist \end{enumerate} \end{itemize} \section{Aufgaben} \begin{itemize} \item Qualitätskontrolle: Ausgangspunkt ist $P(X < x)$, dabei ist X die Anzahl schlechter Chips und x die Grenze. Für Binomialverteilungen kann man daraus $\sum\limits_{i=0}^{x-1} P(X = i)$ machen. \item Schrauben: $0.1 = P(X < 70mm) = P(\frac{X-\mu}{\sigma} < \frac{70mm - \mu}{\sigma}) = \Phi(\frac{70mm - \mu}{\sigma}) = 0.1$ \\ $\Phi(x) = 1-\Phi(-x)$, also $0.9 = \Phi(-\frac{70mm - \mu}{\sigma})$. \item Maximal: $F_X(x) = P(X < x) = P(\max\{T_1, ..., T_n\} < x) = P(T_i < y | \forall i) = P(T_1