Anki Deck Changes

Satz von der totalen Wahrscheinlichkeit

Beispiel: Ziegenproblem

Sie ist null ausserhalb von \(W_X\). Die Dichtefunktion bestimmt die Verteilung der Zufallsvariablen eindeutig.

Beide Bedingungen zusammen sind nötig - daher fordert Unabhängigkeit die Produktregel für alle nichtleeren Teilmengen.

Paarweise \(\not \implies\) vollen Schnitt: Zwei faire Münzen, \(A=\)„\(M_1\) Kopf", \(B=\)„\(M_2\) Kopf", \(C=\)„Ergebnisse verschieden": je zwei Ereignisse sind unabhängig, aber \(\Pr[A\cap B\cap C]=0\neq\tfrac{1}{8}=\Pr[A]\Pr[B]\Pr[C]\).

Voller Schnitt \(\not \implies\) paarweise: Zufallszahl in \(\{1,\ldots,8\}\), \(A=\{1,2,3,4\}\), \(B=\{1,5,6,7\}\), \(C=B\): \(\Pr[A\cap B\cap C]=\tfrac{1}{8}=\Pr[A]\Pr[B]\Pr[C]\), aber \(\Pr[A\cap B]=\tfrac{1}{8}\neq\tfrac{1}{4}=\Pr[A]\Pr[B]\).

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

(Gesetz der totalen Erwartung, nicht im Skript!) 

Proof:
\[\begin{align} \mathbb{E}[X] &=\sum_{x}x\cdot\Pr[X=x] \\ &\overset{\text{totale W'keit}}{=}\sum_x x\sum_i\Pr[X=x|A_i]\Pr[A_i] \\ &=\sum_i\Pr[A_i]\underbrace{\sum_x x\Pr[X=x|A_i]}_{=\mathbb{E}[X|A_i]} \end{align}\]
(Verwendet das Gesetz der totalen Wahrscheinlichkeit um \(\Pr[X=x]\) zu expandieren, dann wird die Summationsreihenfolge vertauscht.)

(Definition 2.22) 

Die Definition verlangt die Produktregel für jede nicht-leere Teil-Durchschnittsmenge - nicht nur paarweise Durchschnitte und nicht nur den vollen \(n\)-fachen Durchschnitt. Beide Bedingungen allein sind unzureichend:

• Paarweise \(\not \implies\) voller Durchschnitt: zwei faire Münzen, \(A=\)"\(M_1\) Kopf", \(B=\)"\(M_2\) Kopf", \(C=\)"Ergebnisse unterscheiden sich" sind paarweise unabhängig, aber \(\Pr[A\cap B\cap C]=0\neq\Pr[A]\Pr[B]\Pr[C]\).
• Voller Durchschnitt \(\not \implies\) paarweise: \(A=\{1,2,3,4\}\), \(B=\{1,5,6,7\}\), \(C=B\) in \(\{1,\ldots,8\}\): \(\Pr[A\cap B\cap C]=\Pr[A]\Pr[B]\Pr[C]\), aber \(A,B\) sind nicht unabhängig.

Die Gesamtzahl der zu prüfenden Bedingungen für \(n\) Ereignisse ist \(2^n-1\) (alle nicht-leeren Teilmengen von \(\{1,\ldots,n\}\)).

(Satz von Bayes)

Proof:
Nach Definition gilt \(\Pr[A_i|B]=\Pr[A_i\cap B]/\Pr[B]\).
Zähler: \(\Pr[A_i\cap B]=\Pr[B|A_i]\cdot\Pr[A_i]\).
Nenner: \(\Pr[B]=\sum_j\Pr[B|A_j]\Pr[A_j]\) (totale Wahrscheinlichkeit). \(\square\)

Zentrale Anwendung:
Die Konditionierungsrichtung "umkehren" - von \(\Pr[B|A_i]\) (leicht zu messen) zu \(\Pr[A_i|B]\) (was wir wissen wollen).

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

(Geburtstagsproblem) 

Modell:
Werfe \(m\) Bälle gleichverteilt in \(n\) Urnen.
Sei \(A_j\) = "Ball \(j\) landet in einer leeren Urne."

Mit dem Multiplikationssatz:\[ \Pr\!\left[\bigcap_{j=1}^m A_j\right] = \prod_{j=2}^{m} \frac{n-(j-1)}{n} = \prod_{j=2}^{m}\!\left(1-\frac{j-1}{n}\right). \]Obere Schranke mit \(1-x \le e^{-x}\):\[ \Pr[\text{alle verschieden}] \le \prod_{j=2}^{m} e^{-(j-1)/n} = e^{-m(m-1)/(2n)}. \]Also ist die Wahrscheinlichkeit für mindestens eine Kollision \(\ge 1 - e^{-m(m-1)/(2n)}\). \(\square\)

(Erwartungswert)

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

(Lemma 2.2)

Beweis:
\(\Omega = A \cup \bar{A}\) ist eine disjunkte Zerlegung, also \(\Pr[\Omega]=\Pr[A]+\Pr[\bar{A}]\).
Mit \(\Pr[\Omega]=1\) folgt \(\Pr[\bar{A}]=1-\Pr[A]\). \(\square\)

Wähle eine Zahl gleichverteilt aus \(\{1,\ldots,8\}\). Sei:
\(A = \{1,2,3,4\}\), also \(\Pr[A]=1/2\)
\(B = \{1,5,6,7\}\), also \(\Pr[B]=1/2\)
\(C = B\) (gleiches Ereignis)

Dann gilt \(\Pr[A\cap B\cap C]=\Pr[A\cap B]=1/8=\Pr[A]\Pr[B]\Pr[C]\) ✓

Aber \(\Pr[A\cap B]=1/8 \neq 1/4 = \Pr[A]\Pr[B]\) ✗ - also sind \(A\) und \(B\) nicht unabhängig.

Lektion:
Die Produktbedingung für den vollen Durchschnitt allein reicht nicht aus; alle Teil-Durchschnitte müssen die Produktregel erfüllen.

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\)

Man "zoomt" in den Wahrscheinlichkeitsraum hinein und beschränkt sich auf die Ergebnisse in \(B\).

Alle Ergebnisse ausserhalb von \(B\) erhalten Wahrscheinlichkeit 0, und die verbleibenden Wahrscheinlichkeiten werden mit \(1/\Pr[B]\) reskaliert, damit sie sich wieder zu 1 summieren.

Sie ist monoton wachsend, rechtsstetig, mit \(F_X\to 0\) für \(x\to-\infty\) und \(F_X\to 1\) für \(x\to+\infty\).

Eine Reihe ist ein Symbol für \(\lim_{n\to\infty} S_n\) - keine gewöhnliche Summe.

Keine allgemeine Aussage - kommt auf den Einzelfall an:

• \(\sum \frac{x^n}{n}\): divergiert für \(x = 1\), konvergiert für \(x = -1\) (Leibniz)
• \(\sum \frac{x^n}{n^2}\): konvergiert für alle \(|x| = 1\) (absolut)
• \(\sum x^n\): divergiert für alle \(|x| = 1\)

(\(0\) und \(\infty\) sind hier Kurzschreibweisen für das Verhalten im Grenzwert: \(0\) steht für „geht gegen \(0\)" und \(\infty\) für „geht gegen \(\infty\)".)

Für alle \(x, y \in \mathbb{R}^n\) gilt:\[|x \cdot y| \leq \|x\| \cdot \|y\|\]

Das Wurzelkriterium. Liefert der Quotient ein Ergebnis, so auch die Wurzel - aber nicht umgekehrt.

In der Praxis ist das Quotientenkriterium oft bequemer, besonders bei \(n!\) oder Potenzen.

Beide versagen bei \(\rho = 1\), z.B. bei \(p\)-Reihen.

(Wurzelkriterium)

Wenn Quotientenkriterium versagt (\(\rho=1\)), versagt auch das Wurzelkriterium — aber nicht umgekehrt.

\[\text{Wenn }\forall \varepsilon > 0 \; \exists N > 0 \text{, so dass } \forall n > N : |a_n - L| < \varepsilon\]

\(x^3\) (ungerade Potenzen) sind zum Beispiel ungerade, oder \(\sin(x)\)

(Weierstrass)

Falls die Folge monoton wachsend ist, gilt: \[ \lim_{n \rightarrow \infty} a_n = \sup \{a_n \mid n \in \mathbb{N}_0\} \]Falls die Folge monoton fallend ist, gilt:\[\lim_{n \rightarrow \infty} a_n = \inf \{ a_n \mid n \in \mathbb{N}_0\}\]

\(f\) ist die innere und \(g\) die äussere Funktion.

Wenn \(\exists B \geq 0\) so dass für alle \(m \in \mathbb{N}\) gilt:
\[\sum_{i=0}^m \sum_{j=0}^m |a_{ij}| \leq B\]dann konvergieren Zeilen- und Spaltensummen absolut und sind gleich:
\[\sum_i S_i = \sum_j U_j = S\]Auch jede linear geordnete Summe konvergiert absolut gegen \(S\).

Spezialfall \(a = 0\):
\(\sum c_k x^k\) - Entwicklungspunkt im Ursprung.

Genauso kann die Folge auch gegen \(-\infty\) divergieren.

In diesem Fall gilt \(\sum_{k=1}^\infty (b_k - b_{k-1}) = \lim_{n\to\infty} b_n - b_0\).

(D.h. nicht absolut konvergiert..)

Beispiel: 
\(\sum \frac{(-1)^n}{n}\) ist bedingt konvergent.

Für \(a_n \geq 0\) gibt es nur zwei Fälle: konvergiert oder divergiert gegen \(+\infty\)

Für alternierende Reihen ist es nicht direkt anwendbar, erst Absolutkonvergenz mit \(\sum |a_n|\) zeigen, dann folgt Konvergenz.

Häufiger Fehler: Vergleich von \((-1)^n/n\) mit \(1/n\) über Majorante. Das scheitert, da \((-1)^n/n \not\geq 0\).

(Die Wurzel dämpft diese vollständig ab.)

Oft als Referenzreihe im Vergleichssatz nützlich (wenn Wurzel/Quotient versagen).

• Work: \(O(n \log n)\) - same as sequential
• Span: \(O(\log^2 n)\) - recursive calls parallelized (\(O(\log n)\) depth) but merge step takes \(O(\log n)\) span via parallel merge
• Parallelism: \(O(n/\log n)\)

Bottleneck: The merge step.
A sequential merge gives \(O(n)\) span, limiting parallelism to \(O(\log n)\).

Faster than synchronized for simple counters.

Implemented via hardware CAS (compare-and-swap).

Part of java.util.concurrent.atomic.

Example:
For a finite run, effective throughput was 0.7 while the infinite-stream bound was 1. As N → ∞, effective throughput approaches 1/max(stage_time).

\(T_1\) is the total work (sum of all node costs in the DAG).
With \(p\) processors, at most \(p\) units of work can be done per time step.
Therefore the minimum time to do \(T_1\) units of work is \(T_1/p\).

This is a counting argument, independent of the scheduler's strategy.

ILP happens on a single thread - no concurrency. It is hardware-dependent (requires superscalar execution units).

The up-sweep computes partial sums in a tree structure, but each node only knows the sum of its subtree - not the sum of all elements to its left.

The down-sweep propagates these missing left-side contributions back down the tree, so that every position ends up with the correct prefix sum.

The first element pays the full pipeline latency \(L(1) = \sum_i \text{stage time}_i\). Each subsequent element is delayed by the slowest stage (bottleneck).

Lead-in: The initial phase where the pipeline is filling up - not all stages are busy yet.

Lead-out: The final phase where the pipeline is draining - no new elements enter, and stages finish one by one.

Only during the steady state between them is the pipeline fully utilized.

Use awaitTermination(timeout, unit) after shutdown() to block until all tasks complete or the timeout expires.

Use volatile for simple flags (e.g. volatile boolean running). For compound operations, use synchronized or AtomicInteger.

Yes, it can happen in practice. Common causes:

• Cache effects: With more processors, each works on a smaller portion of data that fits into cache, reducing memory access time.
• Search/pruning: Parallel threads may explore different branches and find a solution (or prune the search space) earlier than a single thread would.

It does not violate Amdahl's law, which assumes a fixed algorithm - superlinear speedup arises when parallelism changes the effective amount of work.

This is because synchronized is structured (unlike ReentrantLock which requires explicit finally). The JVM guarantees lock release on any exit from the block, including exceptions.

A technique that splits instruction execution into independent stages (e.g. fetch, decode, execute, write-back).

Multiple instructions overlap in different stages simultaneously - like an assembly line.
This increases throughput (instructions per cycle) without reducing the latency of a single instruction.

This does not contradict Amdahl - Gustafson scales the problem size with \(P\) (fixed wall time), so the serial fraction \(f\) is a fixed fraction of the larger workload, not a fixed amount of work.

(Equality, doesn't necessarily hold, usually we have \(>\) due to some performance loss.)

\(T_1\) denotes sequential execution time.