Anki Deck Changes

Jede der \(k\) Positionen hat \(n\) Möglichkeiten.

Beispiel:
Wie viele 4-stellige PINs aus 0–9 (mit Wiederholung)?
\(10^4 = 10{,}000\).

Satz von Brooks

Intuition:
Fixiere Element \(x\).

• \(x\) dabei → noch \(k-1\) aus \(n-1\) wählen
• \(x\) nicht dabei → alle \(k\) aus \(n-1\) wählen

Pascalsches Dreieck (Eintrag in Zeile \(n\), Position \(k\) ist \(\binom{n}{k}\)):
\[\begin{array}{ccccccccc} & & & & 1 \\ & & & 1 & & 1 \\ & & 1 & & 2 & & 1 \\ & 1 & & 3 & & 3 & & 1 \\ 1 & & 4 & & 6 & & 4 & & 1 \end{array}\]Jeder Eintrag = Summe der zwei Einträge schräg darüber.
Z.B.: \(\binom{4}{2} = 6 = \underbrace{\binom{3}{1}}_{3} + \underbrace{\binom{3}{2}}_{3}\)

(Kein perfektes Matching)

Counterexample:

Zufallsvariablen abstrahieren Ergebnisse zu numerischen Werten.

Beispiel:
Bei 2 Würfelwürfen ist \(X =\) "Summe der Augenzahlen" eine Zufallsvariable.

Definiere \(K_1\) = "erster Wurf ist Kopf." Wende totale Erwartung bedingt auf \(K_1\) an:

• \(\mathbb{E}[X \mid K_1] = 1\) (sofort fertig)
• \(\mathbb{E}[X \mid \overline{K}_1] = 1 + \mathbb{E}[X]\) (gedächtnislos: nach Zahl startet der Prozess identisch neu, plus der eine verbrauchte Wurf)

Einsetzen in \(\mathbb{E}[X] = 1 \cdot p + (1 + \mathbb{E}[X])(1-p)\) und Auflösen ergibt \(\mathbb{E}[X] = 1/p\). Vermeidet die direkte Berechnung von \(\sum k \cdot (1-p)^{k-1} p\).

(Boolsche Ungleichung)

Beweis:
\(\operatorname{Var}[X + b] = \mathbb{E}[(X + b - \mathbb{E}[X + b])^2]\) \(= \mathbb{E}[(X - \mathbb{E}[X])^2]\) \(= \operatorname{Var}[X]\) 
Mit Hilfe von \(\text{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2\) erhalten wir \(\operatorname{Var}[a \cdot X] = \mathbb{E}[(aX)^2] - \mathbb{E}[aX]^2\) \(= a^2 \mathbb{E}[X^2] - (a\mathbb{E}[X])^2 = a^2 \cdot \operatorname{Var}[X]\)

(Satz von Bayes)

Es folgt direkt: \(\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]} = \frac{\Pr[B\mid A]\cdot\Pr[A]}{\Pr[B]}\).
Verallgemeinerung (Partition \(A_1,\ldots,A_n\)):

\(\Pr[A_i\mid B] = \frac{\Pr[B\mid A_i]\Pr[A_i]}{\sum_j \Pr[B\mid A_j]\Pr[A_j]}\).

Beweis:
Setze 1. in \(\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}\) ein, dann kürzt sich \(\Pr[B]\) weg.

Intuition:
Das Eintreten von \(B\) beeinflusst die Wahrscheinlichkeit von \(A\) nicht.

(Mycielski-Konstruktion)

Konstruktion:
Aus \(G_k = (V_k, E_k)\) mit \(V_k = \{v_1,\ldots,v_n\}\) bilde \(G_{k+1}\):
Füge Knoten \(w_1,\ldots,w_n, z\) hinzu. \(w_i\) ist mit allen Nachbarn von \(v_i\) verbunden (aber nicht mit \(v_i\) selbst). \(z\) ist mit allen \(w_i\) verbunden.
Der neue Graph ist dreiecksfrei und braucht eine Farbe mehr als \(G_k\).

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!

(Erwartungswert als Summe)

Proof:
\[\begin{align} \mathbb{E}[X] &= \sum_{x\in W_X}x\cdot\Pr[X=x] \\ &=\sum_{x\in W_X}x\cdot\sum_{\omega: X(\omega)=x}\Pr[\omega] \\&=\sum_{\omega\in\Omega}X(\omega)\cdot\Pr[\omega].\quad \end{align}\]
(Summationsreihenfolge vertauschen: nach \(\omega\) gruppieren statt nach Wert \(x\).)

Proof:\[ \mathbb{E}[X]=\sum_{i=0}^{\infty}i\cdot\Pr[X=i]=\sum_{i=0}^{\infty}\sum_{j=1}^{i}\Pr[X=i]=\sum_{j=1}^{\infty}\sum_{i=j}^{\infty}\Pr[X=i]=\sum_{j=1}^{\infty}\Pr[X\ge j].\quad\square \](Der Schlüsselschritt ist das Vertauschen der Summationsreihenfolge: Statt über \(i\) zu summieren und für jedes \(j\le i\) eine 1 zu zählen, wird über \(j\) summiert und alle \(i\ge j\) gezählt.)

Wirf zwei faire Münzen \(M_1, M_2\).

Definiere:
\(A\) = "\(M_1\) zeigt Kopf"
\(B\) = "\(M_2\) zeigt Kopf"
\(C\) = "die Ergebnisse unterscheiden sich" = \(\{(K,Z),(Z,K)\}\)

Dann sind \(A\) und \(B\), \(B\) und \(C\), \(A\) und \(C\) paarweise unabhängig (jedes Paar: \(\Pr[X\cap Y]=1/4=1/2\cdot1/2\)).

Aber:\[\Pr[A\cap B\cap C] = 0 \neq \tfrac{1}{8} = \Pr[A]\Pr[B]\Pr[C].\]Denn falls sowohl \(A\) als auch \(B\) eintreten (beide Kopf), kann \(C\) (Ergebnisse unterscheiden sich) nicht eintreten.

Falls die Summe nicht absolut konvergiert (z.B. positiver und negativer Anteil beide divergieren).

Der Erwartungswert ist nur definiert, wenn die Summe absolut konvergiert, d.h. \(\sum_{x\in W_X}|x|\cdot\Pr[X=x]<\infty\).

In endlichen Wahrscheinlichkeitsräumen ist dies immer erfüllt (endlich viele Terme). Bei unendlichen Räumen muss man aufpassen.

Man passt die Wahrscheinlichkeit einer Hypothese an, indem man die Prior-Wahrscheinlichkeit mit der Likelihood der beobachteten Evidenz kombiniert, um eine Posterior-Wahrscheinlichkeit zu erhalten.

Vor der Beobachtung: Wir haben einen Prior \(\Pr[H]\), unsere anfängliche Überzeugung in Hypothese \(H\).

Nach Beobachtung der Evidenz \(E\): Wir berechnen den Posterior \(\Pr[H|E]\propto\Pr[E|H]\cdot\Pr[H]\).

Falls \(\Pr[E|H]\gg\Pr[E|\bar{H}]\): Die Evidenz unterstützt \(H\) stark, Posterior \(\gg\) Prior.
Falls \(\Pr[E|H]\approx\Pr[E|\bar{H}]\): Die Evidenz ist neutral, Posterior \(\approx\) Prior.

Das Likelihood-Verhältnis \(\Pr[E|H]/\Pr[E|\bar{H}]\) quantifiziert die Stärke der Evidenz für \(H\).

\(\Pr[\text{first heads at flip }k] = (1/2)^k\).

Die Summe gemäss Definition 2.27:\[\sum_{k=1}^{\infty}(-1)^{k-1}\cdot 2^k\cdot (1/2)^k = \sum_{k=1}^{\infty}(-1)^{k-1} = +1-1+1-1+\cdots\]Diese Reihe konvergiert nicht (sie oszilliert), also ist \(\mathbb{E}[G]\) undefiniert.

Analog: Falls die Bank immer \(2^k\) zahlt, ist jeder Term gleich 1 und die Summe divergiert gegen \(+\infty\).

(Multiplikationssatz, Satz 2.10)

Beweis: Jede bedingte Wahrscheinlichkeit gemäss Definition einsetzen:
\[\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}]}.\]
Alle Zwischenterme kürzen sich (Teleskopprodukt), es bleibt \(\Pr[A_1\cap\cdots\cap A_n]\). \(\square\)

Bemerkung: Alle bedingten Wahrscheinlichkeiten sind wohldefiniert, da \(\Pr[A_1]\ge\Pr[A_1\cap A_2]\ge\cdots>0\).

Ansatz: "KKK" kann an Positionen \(i=1,\ldots,m-2\) beginnen. Definiere:\[X_i = \begin{cases}1 & \text{Würfe } i,i+1,i+2 \text{ sind alle Kopf}\\ 0 & \text{sonst}\end{cases}.\]Dann ist \(X=X_1+\cdots+X_{m-2}\).

Jeder Term: \(\mathbb{E}[X_i]=\Pr[X_i=1]=(1/2)^3=1/8\).

Ergebnis: \(\mathbb{E}[X]=(m-2)\cdot\tfrac{1}{8}=\dfrac{m-2}{8}\).

(Die Überlappungen spielen keine Rolle, Linearität des Erwartungswerts erledigt das automatisch.)

Zu zeigen: \(\Pr[\bar{A}\cap B]=\Pr[\bar{A}]\cdot\Pr[B]\).\[\begin{gathered}\Pr[\bar{A}\cap B] = \Pr[B] - \Pr[A\cap B] \\ = \Pr[B] - \Pr[A]\Pr[B] \\ = (1-\Pr[A])\Pr[B] = \Pr[\bar{A}]\Pr[B]. \quad\square\end{gathered}\]Folgerung: Falls \(A_1,\ldots,A_n\) gemeinsam unabhängig sind, so auch jede Familie, die durch Ersetzen einiger \(A_i\) durch \(\bar{A}_i\) entsteht (Lemma 2.23).

Muster:
Schreibe \(X = X_{A_1}+\cdots+X_{A_n}\) als Summe von Indikatorvariablen, eine pro möglichem Vorkommen.
Per Linearität: \(\mathbb{E}[X]=\sum_i\mathbb{E}[X_{A_i}]=\sum_i\Pr[A_i]\).
Berechne jedes \(\Pr[A_i]\) einzeln (oft einfach).

Warum das funktioniert: Unabhängigkeit ist nicht nötig; auch bei Überlappungen oder Korrelationen gilt die Linearität.

Wann verwenden: "Erwartete Anzahl von [Ereignissen] mit [Eigenschaft]" - in Indikatorvariablen zerlegen.

(Additionssatz)

Warum das aus Definition 2.1 folgt:
\(\Pr[\bigcup A_i] = \sum_{\omega \in \bigcup A_i}\Pr[\omega]\). Da die \(A_i\) disjunkt sind, kommt jedes \(\omega\) in genau einem \(A_i\) vor, also ist dies gleich \(\sum_i\sum_{\omega\in A_i}\Pr[\omega]=\sum_i\Pr[A_i]\).

Gegenbeispiel ohne Disjunktheit: Würfel, \(A=\{1,3,5\}\), \(B=\{5,6\}\). \(\Pr[A\cup B]=4/6 \ne 5/6 = \Pr[A]+\Pr[B]\).

(Lemma 2.2)

Beweis: Schreibe \(B = A \cup (B \setminus A)\) als disjunkte Vereinigung. Per Additionssatz: \(\Pr[B]=\Pr[A]+\Pr[B\setminus A]\ge\Pr[A]\), da \(\Pr[B\setminus A]\ge 0\). \(\square\)

(Satz von der totalen Wahrscheinlichkeit) 

Proof:
Zerlege: \(B = (B\cap A_1)\cup\cdots\cup(B\cap A_n)\) (disjunkte Teile).
Additionssatz: \(\Pr[B] = \sum_i \Pr[B\cap A_i]\) (da disjunkt).
Mit \(\Pr[B\cap A_i] = \Pr[B|A_i]\cdot\Pr[A_i]\) (Definition der bedingten Wahrscheinlichkeit). \(\square\)

Nutzen: Ein komplexes Ereignis in einfachere Fälle zerlegen (die \(A_i\) bilden eine Partition des relevanten Universums).

Der Beweis verwendet nur:

1. Die Darstellung \(\mathbb{E}[X]=\sum_\omega X(\omega)\Pr[\omega]\) (Summe über Ergebnisse, nicht über Werte).
2. Linearität der Summation (Verteilen der Summe).

An keiner Stelle wird Unabhängigkeit von \(X_1,\ldots,X_n\) verwendet oder vorausgesetzt.

Das macht die Linearität des Erwartungswerts so mächtig: sie gilt bedingungslos.

Das Wissen, dass \(B\) eingetreten ist, liefert keine Information darüber, ob \(A\) eingetreten ist (und umgekehrt). D.h. \(\Pr[A|B]=\Pr[A]\).

Beispiele wo Unabhängigkeit natürlich ist:
Zwei separate Würfelwürfe.
Zwei separate Münzwürfe.

Beispiele wo Unabhängigkeit nicht offensichtlich ist:
In Beispiel 2.17: "erster Wurf ist gerade" und "Summe ist 7" sind unabhängig, obwohl beide Würfe involviert sind.

Die formale Definition \(\Pr[A\cap B]=\Pr[A]\Pr[B]\) funktioniert auch wenn \(\Pr[B]=0\) (vermeidet das Division-durch-Null-Problem der bedingten Form).

Zu zeigen: \(\sum_{\omega\in\Omega}\Pr[\omega|B]=1\):
\[ \sum_{\omega\in\Omega}\Pr[\omega|B] = \sum_{\omega\in\Omega}\frac{\Pr[\omega\cap B]}{\Pr[B]} = \sum_{\omega\in B}\frac{\Pr[\omega]}{\Pr[B]} = \frac{\Pr[B]}{\Pr[B]} = 1. \]Intuition: Bedingen setzt \(\Pr[\omega|B]=0\) für alle \(\omega\notin B\) und reskaliert die verbleibenden Wahrscheinlichkeiten mit \(1/\Pr[B]\), damit sie sich zu 1 summieren.

Konsequenz: Alle Wahrscheinlichkeitsregeln (Komplement, Vereinigung, Additionssatz, etc.) gelten auch für \(\Pr[\cdot|B]\).

(Beobachtung 2.35) 

(Produktregel des Erwartungswertes)

Proof:\[ \mathbb{E}[XY] = \sum_{x,y} xy\cdot\Pr[X=x, Y=y] \overset{\text{indep.}}{=} \sum_{x,y} xy\cdot\Pr[X=x]\Pr[Y=y] = \left(\sum_x x\Pr[X=x]\right)\!\left(\sum_y y\Pr[Y=y]\right) = \mathbb{E}[X]\mathbb{E}[Y]. \quad\square \]Der Schlüsselschritt nutzt Unabhängigkeit: \(\Pr[X=x, Y=y]=\Pr[X=x]\cdot\Pr[Y=y]\), wodurch sich die Doppelsumme faktorisieren lässt.

Kontrast zur Linearität: \(\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]\) gilt immer (keine Unabhängigkeit nötig). \(\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]\) braucht Unabhängigkeit.

Gegenbeispiel (ohne Unabhängigkeit): Sei \(X=Y\sim\text{Bernoulli}(1/2)\). Dann \(\mathbb{E}[XY]=\mathbb{E}[X^2]=1/2\), aber \(\mathbb{E}[X]\mathbb{E}[Y]=(1/2)^2=1/4\neq 1/2\).

Proof: \(\mathbb{E}[X_A]=1\cdot\Pr[X_A=1]+0\cdot\Pr[X_A=0]=\Pr[A].\quad\square\)

Das ist die Brücke zwischen Ereignissen (Wahrscheinlichkeit) und Zufallsvariablen (Erwartungswert): Die Wahrscheinlichkeit eines Ereignisses entspricht dem Erwartungswert seiner Indikatorvariable.

Intuition:
Das Eintreten von \(B\) beeinflusst die Wahrscheinlichkeit von \(A\) nicht.

Sei \(\mu := \mathbb{E}[X]\).

• Nach Definition gilt \(\operatorname{Var}[X] = \mathbb{E}[(X - \mu)^2] = \mathbb{E}[X^2 - 2\mu \cdot X + \mu^2]\) 
• Aus der Linearität des Erwartungswertes (Satz 2.33) folgt \[\mathbb{E}[X^2 - 2\mu \cdot X + \mu^2] = \mathbb{E}[X^2] - 2\mu \cdot \mathbb{E}[X] + \mu^2\]
• Damit erhalten wir \[\operatorname{Var}[X] = \mathbb{E}[X^2] - 2\mu \cdot \mathbb{E}[X] + \mu^2 = \mathbb{E}[X^2] - \mathbb{E}[X]^2\]
  

Das ist der Blossom-Algorithmus.

Dies wird im Christofides-Algorithmus für das metrische TSP benötigt.

(Riemannscher Umordnungssatz)

Merke: Bedingt konvergente Reihen können durch Umordnung jeden Grenzwert annehmen!

Nützlich zur numerischen Approximation alternierender Reihen.

Man beachte, dass \(f\) und \(f\mid_{D'}\) a priori zwei verschiedene Funktionen sind.

Beispiel \(\overline{f} : \mathbb{R}^+_0 \rightarrow \mathbb{R}^+_0\) \(f(x) = x^2\) ist bijektiv.