Randomness Extractors Learning Notes

Pseudorandomness Chapter $6$ learning notes.

IID-Bit Sources: A simple version of this question was already
considered by von Neumann. He looked at sources that consist of
boolean random variables X1,X2,…,Xn ∈ {0,1} that are independent
but biased. That is, for every i, Pr [Xi = 1] = δ for some unknown δ.
How can such a source be converted into a source of independent, unbiased bits? Von Neumann proposed the following extractor: Break all
the variables in pairs and for each pair output 0 if the outcome was
01, 1 if the outcome was 10, and skip the pair if the outcome was 00
or 11. This will yield an unbiased random bit after 1/(2δ(1 − δ)) pairs
on average.

Statistical Difference: For random variables $X$ and $Y$ taking values in $\mathcal U$, their statistical difference (a.k.a. variation distance) is $\Delta(X,Y ) \triangleq \max\limits_{T \subset \mathcal U} \left|\Pr[X ∈ T] − \Pr[Y ∈ T]\right|$. We say that $X$ and $Y$ are $ε$-close if $\Delta (X,Y ) ≤ ε$.

Deterministic Extractors: Let $\mathcal C$ be a class of sources on $\{0,1\}^n$. An $ε$-extractor for $\mathcal C$ is a function $\text{Ext} : \{0,1\}^n \to \{0,1\}^m$ such that for every $X ∈ \mathcal C$, $\text{Ext}(X)$ is $ε$-close to $U_m$.

Properties of Statistical Difference: Let $X,Y,Z,X_1,X_2,Y_1,Y_2$ be random variables taking values in a universe $\mathcal U$. Then,

(1) $\Delta (X,Y ) ≥ 0$, with equality iff $X$ and $Y$ are identically distributed,

(2) $\Delta (X,Y ) ≤ 1$, with equality iff $X$ and $Y$ have disjoint supports,

(3) $\Delta(X,Y ) = \Delta(Y,X)$,

(4) $\Delta(X,Z) ≤ \Delta(X,Y ) + \Delta(Y,Z)$,

(5) for every function $f$, we have $\Delta(f(X),f(Y )) ≤ \Delta(X,Y )$,

(6) $\Delta((X_1,X_2),(Y_1,Y_2)) ≤ \Delta(X_1,Y_1) + \Delta(X_2,Y_2)$ if $X_1$ and $X_2$, as well as $Y_1$ and $Y_2$, are independent, and

(7) $\Delta(X,Y ) = \dfrac 12 · |X − Y |_1$.

Proof: Properties $1\sim 4$ are obviously correct.

(5) For every function $f:\mathcal U \to\mathcal U'$, $\Delta(f(X),f(Y ))=\max\limits_{T'\subset \mathcal U'}|\Pr[f(X)\in T']-\Pr[f(Y)\in T']|=\max\limits_{T'\subset \mathcal U'}|\Pr[X\in f^{-1}(T')]-\Pr[Y\in f^{-1}(T')]|\le \max\limits_{T\subset \mathcal U}|\Pr[X\in T]-\Pr[Y\in T]|=\Delta(X,Y)$.

(6)

(7) $\Delta(X,Y )=\max\limits_{T \subset \mathcal U} \left|\Pr[X ∈ T] − \Pr[Y ∈ T]\right|=\sum_{t\in S} (\Pr[X=t]-\Pr[Y=t])$, where $S=\{t\in \mathcal U\mid \Pr[X=t]\ge \Pr[Y=t]\}$.

Due to the symmetry, we also have $\Delta(X,Y )=\sum_{t\in T} (\Pr[Y=t]-\Pr[X=t])$, where $T=\{t\in \mathcal U\mid \Pr[X=t]< \Pr[Y=t]\}$.

Thus:

$\Delta(X,Y )=\dfrac 12\cdot \left(\sum_{t\in S} (\Pr[X=t]-\Pr[Y=t])+\sum_{t\in T} (\Pr[Y=t]-\Pr[X=t])\right)=\dfrac 12\cdot |X-Y|_1$

as desired.

$\Box$

Proposition: Let $A(w;r)$ be a randomized algorithm such that $A(w;U_m)$ has error probability at most $γ$, and let $\text{Ext} : \{0,1\}^n \to \{0,1\}^m$ be an $ε$-extractor for a class $\mathcal C$ of sources on $\{0,1\}^n$. Define $A'(w;x) = A(w;\text{Ext}(x))$. Then for every source $X ∈ \mathcal C$, $A'(w;X)$ has error probability at most $\gamma+\epsilon$.

Proof: The error probability of $A'(w;X)$ is $\Pr[\text{Ext}(X)\in S]$, where $S\subset \{0,1\}^m$ is the set of coin tosses sequences which makes $A(w;U_m)$ error. Note that $\Pr[U_m\in S]\le \gamma$.

Thus, $\Pr[\text{Ext}(X)\in S]\le \Pr[U_m\in S]+\Delta(\text{Ext}(X),U_m)\le \gamma+\epsilon$.

$\Box$

Unpredictable-Bit Sources (a.k.a. Santha–Vazirani Sources): $\text{UnpredBits}_{n,δ}$ is the class of unpredictable-bit sources, i.e. for every $i$, every $x_1,\ldots,x_n ∈ \{0,1\}$ and some constant $δ > 0$, satisfy $δ ≤ \Pr[X_i = 1 \mid X_1 = x_1,X_2 = x_2,\ldots,X_{i−1} = x_{i−1}] ≤ 1 − δ$.

Problem 6.6 (Extracting from Unpredictable-Bit Sources):

(1) Let $X$ be a source taking values in $\{0,1\}^n$ such that for all $x,y$, $\Pr[X = x]/\Pr[X = y] ≤ (1 − δ)/δ$. Show that $X ∈ \text{UnpredBits}_{n,δ}$.

(2) Prove that for every function $\text{Ext}: \{0,1\}^n \to \{0,1\}$ and every $δ > 0$, there exists a source $X ∈ \text{UnpredBits}_{n,δ}$ with parameter $δ$ such that $\Pr[\text{Ext}(X) = 1] ≤ δ$ or $\Pr[\text{Ext}(X) = 0] ≥ 1 − δ$.

Proof:

$\Box$

Entropy Measures: Let $X$ be a random variable. Then

• the Shannon entropy of $X$ is:

  $\text{H}_{Sh}(X) =\mathop{\mathbb E}\limits_{x\mathop{\gets}\limits^{\text R} X}\left[ \log_2 \dfrac 1{\Pr[X=x]} \right]$

• the Rényi entropy of $X$ is:

  $\text{H}_2(X)=\log_2\left(\dfrac 1{\mathop{\mathbb E}\limits_{x\mathop{\gets}\limits^{\text{R}}X} [\Pr[X=x]] }\right)=\log_2\dfrac 1{\text{CP}(X)}$

• the min-entropy of $X$ is:

  $\text{H}_\infty(X)=\min_x\left\{\log_2 \dfrac 1{\Pr[X=x]} \right\}$