# Zettel 4
## Aufgabe 1

Betrachte die Folge an Ereignissen bis jeder Sender min. 1-mal erfolgreich war. Dabei sei eine Phase genau die Zeitspanne von der ersten erfolgreichen Transmission eines Senders zu der nächsten, d.h. die Zeitspanne ist in $n$ disjunkte Phasen unterteilt. Sei $x_i$ die Länge von Phase $i$. Dann gilt $T=\sum_{i=1}^n x_i$, wobei $T$ die Zeit, nach der jeder Sender min. 1-mal erfolgreich war, beschreibt.
$\forall j\in\{1,...,n\}: Pr[j\text{ sendet während alle anderen Sender nicht senden}]={1\over n}({n-1\over n})^{n-1}$.
Betrachte Phase $i$. $Pr[\text{ein Sender, der noch nicht erfolgreich gesendet hat, sendet als einziger}]=Pr[\bigcup_{j\in S} j\text{ sendet als Einziger}]$, wobei $S$ die Menge der Sender beschreibt, die noch nicht erfolgreich gesendet haben. Da die Ereignisse disjunkt sind und $|S|=n-(i-1)=n-i+1$ gilt: $Pr[\bigcup_{j\in S} j \text{ sendet als einziger}]=(n-i+1)\cdot{1\over n}\cdot({n-1\over n})^{n-1}$.
$x_i$ ist folglich eine geometrisch verteilte Zufallsvariable mit Parameter $p_i=(n-i+1)\cdot{1\over n}\cdot({n-1\over n})^{n-1}$.
\begin{align}\Rightarrow E[T]&=\sum_{i=1}^n E[x_i]=\sum_{i=1}^n {1\over p_i}=\sum_{i=1}^n ((n-i+1)\cdot{1\over n}\cdot({n-1\over n})^{n-1})^{-1}\\
&=\sum_{i=1}^n {n\over n-i+1}\cdot ({n\over n-1})^{n-1}=({n\over n-1})^{n-1}\cdot\sum_{i=1}^n {n\over n-i+1}\\
&=({n\over n-1})^{n-1}\cdot n\cdot\sum_{i=1}^n {1\over i}=({n\over n-1})^{n-1}\cdot n\cdot H_n\in\Theta(n\cdot \log(n))
\end{align}

## Aufgabe 2
### a)
Algorithmus: wähle eine beliebe Belegung $\alpha$

Sei Y der Wert der belegung Belegung $\alpha$

Seien Zufallsvariablen: $Y_i = \{1 \text{ falls } \alpha \text{ Klausel } C_j \text{ erfüllt }, 0 \text{ sonst }\}$

Es gilt $Y = Y_1 + ... + Y_m$

$E[Y] = E[\sum_{j=1}^{m}Y_j] = \sum_{j=i}^{m} = \sum_{j = 1}^{m}E[Y_i] = \sum_{j=1}^{m}Pr[\alpha \text{ erfüllt } C_j]$

$Pr[\alpha \text{ erfüllt } C_j] = 1 - Pr[\alpha \text{ erfüllt nicht} C_j] \geq 1 - (\frac{1}{2})^3 = 1 - \frac{1}{8} = \frac{7}{8}$
Da jede Klausel immer länge 3 ergibt sich eine Wahrscheinlichkeit $(\frac{1}{2})^3$ eine Klausel nicht zu erfüllen.

$E[Y] = \sum_{j=1}^{m}Pr[\alpha \text{ erfüllt } C_j] \geq \sum_{j=1}^{m}\frac{7}{8} = \frac{7}{8}\sum_{j=1}^{m}1 = \frac{7}{8} \cdot OPT$

Da im optimalen Fall alle Klauseln erfüllt sind ergibt sich aus der Summe die Optimale Lösung.

### b)



## Aufgabe 3


### b)
$E[Y | v \in B_1, ..., v_i\in B_i] = \sum_{e \ in E}Pr[e \text{ liegt auf dem Schnitt } | v \in B_1, ..., v_i\in B_i]$

Wahrscheinlichkeit das $e$ auf dem Schnitt liegt:
Falll 1: für $(x,y) = e$ gilt $x \in S, y \in V\backslash S$
$\implies$ 1 da die Kante auf jedenfall auf dem Schnitt liegt
Fall 2: für $(x,y) = e$ gilt $x \in S, y \in S$ oder $x \in V\backslash S, y \in V\backslash S$
$\implies$ 0 da diese Kante nicht auf dem Schnitt liegen kann
Fall 3: sonst
Es gilt die die Wahrscheinlichkeit $\frac{1}{2}$ wie in der Vorlesung, da für eine gegebene Kante für den ein Punkt in $V$ oder $V \backslash S$ liegt die Wahrscheinlichkeit $\frac{1}{2}$ ist das der andere Punkt in die andere Menge gelegt wird.

Somit können die Bedingten Wahrscheinlichkeiten effizient berechnet werden da für jede Kante geprüft werden kann ob diese Bereits auf dem Schnitt liegt, nicht auf dem Schnitt liegt oder ansonsten die Wahrscheinlichkeit $\frac{1}{2}$ auf dem Schnitt zu liegen.