Anki Deck Changes

(Linearität)

Gilt auch wenn \(X_1,\ldots,X_n\) nicht unabhängig sind.

Proof:
Mit Lemma 2.29 (\(\mathbb{E}[X]=\sum_\omega X(\omega)\Pr[\omega]\)):
\[ \mathbb{E}[X]=\sum_\omega(a_1X_1(\omega)+\cdots+a_nX_n(\omega)+b)\Pr[\omega] =a_1\underbrace{\sum_\omega X_1(\omega)\Pr[\omega]}_{=\mathbb{E}[X_1]}+\cdots+b\underbrace{\sum_\omega\Pr[\omega]}_{=1}.\quad\square \]
Der Schlüssel ist, dass die äussere Summe \(\sum_\omega\) sich über die Linearkombination verteilt.

(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.)

Beweisskizze (⇒):
Induktion über die Anzahl Nullen in \((s_1,\ldots,s_n)\).
Basisfall (\(s_i=1\) für alle \(i\)): direkt aus der Definition.
Induktionsschritt (z.B. \(s_1=0\)):
\(\Pr[\bar{A}_1\cap A_2^{s_2}\cap\cdots] = \Pr[A_2^{s_2}\cap\cdots]-\Pr[A_1\cap A_2^{s_2}\cap\cdots]\)
\(= \Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}]-\Pr[A_1]\Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}]\)
\(= (1-\Pr[A_1])\Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}] = \Pr[\bar{A}_1]\Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}]\). \(\square\)

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.

(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:
Gewichteter Durchschnitt aller möglichen Werte.

1. Parallel recursive calls only: Work \(O(n \log n)\), Span \(O(n)\), Parallelism \(O(\log n)\)
2. + parallel partition (pack): Work \(O(n \log n)\), Span \(O(\log^2 n)\), Parallelism \(O(n/\log n)\)

Parallelizing the partition reduces span from \(O(n)\) to \(O(\log^2 n)\), dramatically increasing parallelism.