Anki Deck Changes

Speziell:
\((1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k\)
\((1-1)^n = 0 = \sum_{k=0}^n (-1)^k \binom{n}{k}\) (genutzt im Siebformel-Beweis!)

Speziell für \(r=2\): \(\frac{n!}{k!\,(n-k)!} = \binom{n}{k}\).
Beispiel: Anordnungen von „MISSISSIPPI“: \(\frac{11!}{1!\cdot 4!\cdot 4!\cdot 2!} = 34{,}650\).

Jede der \(k\) Positionen hat \(n\) Möglichkeiten.
Beispiel: Wie viele 4-stellige PINs aus 0–9 (mit Wiederholung)? \(10^4 = 10{,}000\).

Auch bekannt als „Sterne und Striche“ (Stars and Bars).
Beispiel: Wie viele Möglichkeiten, 3 Kugeln aus {rot, blau, grün} mit Zurüclegen zu ziehen?
\(\binom{3+3-1}{3} = \binom{5}{3} = 10\).

\[= \sum_{i=1}^{n} \Pr[A_i] - \sum_{1 \leq i_1 < i_2 \leq n} \Pr[A_{i_1} \cap A_{i_2}] + \ldots - \ldots + \ldots + (-1)^{n+1} \cdot \Pr[A_1 \cap \cdots \cap A_n].\]

Eselsbrücke: geordnet ohne = Permutation, ungeordnet ohne = Kombination,
geordnet mit = Wort über Alphabet, ungeordnet mit = Multiset (Sterne & Striche).

Unabhängigkeit nicht nötig!
Beispiel: Erwartete Anzahl Fixpunkte einer zufälligen Permutation von \([n]\)?
\(X_i = [i \text{ ist Fixpunkt}]\), \(\Pr[X_i = 1] = \frac{1}{n}\), also \(\mathbb{E}[X] = n \cdot \frac{1}{n} = 1\).

Beispiel: Wie viele 3-stellige PINs aus den Ziffern 0–9 ohne Wiederholung?
\(P(10,3) = 10 \cdot 9 \cdot 8 = 720\).

\(\Pr[H \mid E] \propto \Pr[E \mid H] \cdot \Pr[H]\).

Das \(\propto\) (proportional zu) bedeutet: durch \(\Pr[E]\) normieren.
Intuition: Der Prior ist die Ausgangsmeinung; die Likelihood gewichtet, wie stark die
Evidenz diese Meinung in Richtung \(H\) verschiebt.

Zufallsvariablen abstrahieren Ergebnisse zu numerischen Werten.
Beispiel: Bei 2 Würfelwürfen ist \(X =\) "Summe der Augenzahlen" eine Zufallsvariable.

Beweis: Setze \(x = y = 1\) im Binomialsatz: \((1+1)^n = \sum_{k=0}^n \binom{n}{k}\).
Interpretation: Anzahl aller Teilmengen einer \(n\)-elementigen Menge ist \(2^n\).

Beide Seiten sind gleich, weil \(\Pr[A \cap B]\) symmetrisch in \(A\) und \(B\) ist.

Proof: Expand each conditional probability by definition:
\[ \Pr[A_1]\cdot\frac{\Pr[A_1\cap A_2]}{\Pr[A_1]}\cdot\frac{\Pr[A_1\cap A_2\cap A_3]}{\Pr[A_1\cap A_2]}\cdots\frac{\Pr[A_1\cap\cdots\cap A_n]}{\Pr[A_1\cap\cdots\cap A_{n-1}]}. \]
All intermediate terms cancel (telescoping product), leaving \(\Pr[A_1\cap\cdots\cap A_n]\). \(\square\)

Note: All conditional probabilities are well-defined because \(\Pr[A_1]\ge\Pr[A_1\cap A_2]\ge\cdots>0\). Multiplikationssatz

Beispiel: Geburtstagsproblem
Betrachte einen Raum mit \(m\) Personen.
Was ist die Wahrscheinlichkeit, dass zwei Personen am gleichen Tag Geburtstag haben?

Achtung: Paarweise Unabhängigkeit (\(\Pr[A_i \cap A_j] = \Pr[A_i]\Pr[A_j]\) für alle \(i \neq j\)) impliziert NICHT stochastische Unabhängigkeit!

Beweis:

\(\Pr[\emptyset]=\sum_{\omega\in\emptyset}\Pr[\omega]=0\) (leere Summe).

  \(\Pr[\Omega]=\sum_{\omega\in\Omega}\Pr[\omega]=1\) per Definition (Normierungsbedingung). 

Intuition: Das Eintreten von \(B\) gibt keine Information über \(A\).

Anwendung: Um \(|A|\) zu zählen, zähle separat „\(A\) und \(B\) tritt ein“ und
„\(A\) und \(B\) tritt nicht ein“.
Analogon: Satz der totalen Wahrscheinlichkeit \(\Pr[A] = \Pr[A|B]\Pr[B] + \Pr[A|B^c]\Pr[B^c]\).

Nützlich wenn „\(A\) tritt nicht ein“ einfacher zu zählen ist.
Beispiel: Wie viele Hände (5 aus 52) enthalten mindestens ein Ass?
Komplement: keine Asse = \(\binom{48}{5}\). Antwort: \(\binom{52}{5} - \binom{48}{5}\).

Intuition: Gewichteter Durchschnitt aller möglichen Werte.

Beziehung zu geordneter Auswahl: \(\binom{n}{k} = \frac{P(n,k)}{k!}\)
(durch \(k!\) teilen, weil Reihenfolge egal).

Definiert für \(0 \leq k \leq n\), sonst \(0\).