Seien $X_1,\dots, X_k$ unabhängige Zufallsvariable. Sei $R_i \subseteq \R$ die Menge der Werte, die von $X$ mit positiver Wahrscheinlichkeit angenommen werden (der Träger oder Support von $X$). Nun gilt wegen Unabhängigkeit für jedes Element $(r_1,\dots,r_k) \in R_1 \times \dots \times R_k$, dass
\begin{align*} \Pr[X_i = r_i \forall i \in [k]] = \prod_{i=1}^k \Pr[X_i = r_i] \gt 0 \end{align*}positiv ist. Somit muss es für jedes $(r_1,\dots,r_k) \in R_1 \times \dots \times R_k$ ein Urbild $\omega \in \Omega$ geben, und somit gilt
\begin{align*} |\Omega| \geq |R_1| \cdots |R_k| \ . \end{align*}Wenn nun keines der $X_i$ konstant ist, jedes $X_i$ also mindestens zwei Werte im Träger hat, gilt $|\Omega| \geq 2^k$. In einer algorithmischen Problemstellung kann das problematisch sein, z.B. wenn man den ganzen Zufallsraum $\Omega$ durchsuchen will (z.B. beim Derandomisieren eines randomisierten Algorithmus) oder wenn man sich ein Zufallselement $\omega \in \Omega$ mit wenig Speicherplatz merken will. Oft reicht es, mit $l$-weise unabhängigen Zufallsvariablen zu arbeiten. Diese können wir über einem deutlich kleineren Wahrscheinlichkeitsraum konstruieren.
Definition Seien $X_1, \dots, X_k$ Zufallsvariable über einem gemeinsamen Wahrscheinlichkeitraum $\Omega$. Wir sagen, $X_1,\dots,X_k$ sind $l$-weise unabhängig, wenn jede Untermenge aus $l$ Variablen unabhängig ist. Wenn also
\begin{align} \Pr[X_i = z_i \ \forall i \in I] & = \prod_{i \in I} \Pr[X_i = z_i] \ . \label{eq-independence-random-var} \end{align}für alle $I \subseteq [k]$ mit $|I| \leq l$ gilt. Wenn $l=2$ ist, dann sprechen wir auch von paarweise unabhängigen Zufallsvariablen.
Lemma (Konstruktion von paarweise unabhängigen Zufallsvariablen) Sei $p$ eine Primzahl und $\F_p$ die Menge der Zahlen $\{0, \dots, p-1\}$ mit Addition und Multiplikation modulo $p$. Seien $a, b \in \F_p$ zufällig und unabhängig gewählt und sei
\begin{align*} \pi: \F_p & \rightarrow \F_p \\ x & \mapsto ax + b \ . \end{align*}Dann sind die Werte $\pi(0), \pi(1), \dots, \pi(p-1)$ paarweise unabhängige Zufallsvariable.
Beweis. Als erstes beobachten wir, dass für alle $x, z \in \F_p$ gilt:
\begin{align*} \Pr[\pi(x) = z] = \Pr[ax + b = z] = \Pr[b = z - ax] \ . \end{align*}Wobei Multiplikation, Addition und Subtraktion in $\F_p$ stattfinden. Egal, wie $a$ gewählt wurde, es gibt also genau ein $b \in F_p$, dass die Gleichung wahr macht. Somit ist $\Pr[\pi(x) = z] = 1/p$.
Als nächstes müssen beweisen, dass für $x_1, x_2 \in \F_p$ mit $x_1 \ne x_2$ die beiden Zufallsvariablen $\pi(x_1)$ und $\pi(x_2)$ unabhängig sind. Das heißt, dass für alle $z_1, z_2 \in \F_p$
\begin{align} \Pr[\pi(x_1) = z_1 \wedge \pi(x_2) = z_2] = \Pr[\pi(x_1) = z_1] \Pr[\pi(x_2) = z_2] = \frac{1}{p^2} \label{eq-pairwise} \end{align}gilt. Für welche Wahl von $(a,b) \in \Omega = \F_p \times \F_p$ gilt nun $\pi(x_1) = z_1 \wedge \pi(x_2) = z_2$? Genau dann, wenn
\begin{align} ax_1 + b & = z_1 \\ ax_2 + b & = z_2 \label{eq-linear-system-2} \end{align}gilt. Wie viele Lösungen hat dieses Gleichungssystem? Wir machen einen Gaussschen Schritt und ziehen die zweite Gleichung von der ersten ab und erhalten das äquivalente System
\begin{align*} ax_1 + b & = z_1 \\ a(x_1 - x_2) & = z_1 - z_2 \ . \end{align*}Da $x_1 - x_2 \ne 0$ ist und $\F_p$ ein Körper ist, gibt es genau ein $a$, welches die zweite Gleichung erfüllt, nämlich $a = (z_1-z_2) (x_1 - x_2)^{-1}$. Für dieses $a$ gibt es wiederum genau ein $b$, welches die erste Gleichung erfüllt und somit hat das Gleichungssystem genau eine Lösung $(a,b) \in \F_p \times \F_p$:
\begin{align*} (a,b) = \left( (z_1-z_2) (x_1 - x_2)^{-1}, z_1 - (z_1-z_2) (x_1 - x_2)^{-1} x_1 \right) \ . \end{align*}Die genaue Form ist uns egal. Wir wollen nur wissen, dass (\ref{eq-linear-system-2}) genau eine Lösung hat. \(\square\)
Der Vorteil ist nun, dass es nur $p^2$ Möglichkeiten gibt, wie man die FUnktion $\pi$ überhaupt bauen kann. Wir können uns somit $\pi$ mit $2 \log p$ Bits merken, indem wir uns einfach die Werte $a$ und $b$ speichern. In anderen Anwendungen können wir zum Beispiel mit Brute Force den gesamten Wahrscheinlichkeitsraum $\F_p \times F_p$ in $O(p^2)$ Schritten durchsuchen, um das gute $\pi$ deterministisch zu finden.
Übungsaufgabe Definieren Sie auf dem Wahrscheinlichkeitsraum $\F_p^l$ ein Ensemble von $p$ Zufallsvariablen, die $l$-weise unabhängig sein sollen. Also eine "Zufallsfunktion" $\pi: \F_p \rightarrow \F_p$, die sie sich mit $l \log p $ Bits speichern können, und die Ihnen garantiert, dass für jede Wahl von $l$ verschiedenen Urbildern $x_1, \dots, x_l$ die Bilder
\begin{align*} \pi(x_1) ,\dots, \pi(x_l) \end{align*}unabhängig sind.
Tipp: Verallgemeinern Sie die Konstruktion von $\pi(x) = ax + b$.