Pairwise Independent Bits

Problem

Given $n \in \mathbb{N}_+$, generate $n$ pairwise independent binary bits with as few randomness as possible.

Solution

WLOG, assume that $n = 2^k - 1$ for some $k \ge 2$.

Theorem. We can generate $n$ pairwise independent bits with $k$ independent unbiased random bits.

Proof. Let $X_1, X_2, ..., X_k$ be unbiased random bits.

Define for every nonempty subset $S \subset [k]$,

There are $2^k - 1$ such random variables. We claim that they are pairwise independent.

First, observe that for every $S \subset [k]$,

Moreover, for every pair of nonempty subsets $S \neq S' \subset [k]$, there exists at least one index $j \in S \Delta S'$. Fixing the values of $X_i$ for all $i \in [k] \setminus \{ j \}$, whether $Y_S = Y_{S'}$ or not depends solely on $X_j$. Hence,

$\square$

Remark: We can label the nonempty subsets $\{ S \subset [k] : S \neq \emptyset \}$ by numbers in $[n]$ and rewrite the random variables $\{ Y_S : S \subset [k] \wedge S \neq \emptyset \}$ as an $n$-bit vector $\pmb Y = (Y_1, ..., Y_n)$. The vector $\pmb Y$ has $2^k$ distinct values.

Reference

[1] S. P. Vadhan, “Pseudorandomness,” TCS, vol. 7, no. 1–3, pp. 1–336, Dec. 2012