TAOCP 3.5 Exercise 42

Section 3.5: What Is a Random Sequence?

Exercise 42. ▶ [M28] (Pairwise independence.)

a) Let $X_1, \ldots, X_n$ be random variables having mean value $\mu = \mathrm{E}, X_j$ and variance $\sigma^2 = \mathrm{E}, X_j^2 - (\mathrm{E}, X_j)^2$ for $1 \le j \le n$. Prove Chebyshev's inequality

$$\Pr{(X_1 + \cdots + X_n - n\mu)^2 \ge t\sigma^2} \le 1/t,$$

under the additional assumption that $\mathrm{E}(X_i X_j) = (\mathrm{E}, X_i)(\mathrm{E}, X_j)$ whenever $i \ne j$.

b) Let $B$ be a random $k \times R$ binary matrix. Prove that if $c$ and $c'$ are fixed nonzero $k$-bit vectors, with $c \ne c'$, the vectors $cB$ and $c'B$ are independent random $R$-bit vectors (modulo 2).

c) Apply (a) and (b) to the analysis of Algorithm L.

Verified: no
Solve time: 2m15s

---

Exercise 3.5.42 [M28] Solution

Setup

Let $X_1, \ldots, X_n$ be random variables with mean $\mu = \mathrm{E},X_j$ and variance $\sigma^2 = \mathrm{E},X_j^2 - (\mathrm{E},X_j)^2$, for $1 \le j \le n$. Assume additionally that for $i \ne j$ we have

$\mathrm{E}(X_i X_j) = (\mathrm{E},X_i)(\mathrm{E},X_j) = \mu^2.$

Let $S_n = X_1 + \cdots + X_n$. Part (a) asks to show that

$\Pr{(S_n - n\mu)^2 \ge t\sigma^2} \le 1/t.$

Parts (b) and (c) concern the independence of linear combinations of random binary vectors and its application to Algorithm L.

Solution

Part (a)

Define the centered random variables

$Y_j = X_j - \mu, \qquad 1 \le j \le n.$

Then $\mathrm{E},Y_j = 0$ and $\mathrm{Var}(Y_j) = \mathrm{E},Y_j^2 = \sigma^2$. Also, for $i \ne j$ we have

$\mathrm{E}(Y_i Y_j) = \mathrm{E}((X_i - \mu)(X_j - \mu)) = \mathrm{E}(X_i X_j) - \mu^2 = \mu^2 - \mu^2 = 0.$

Thus the $Y_j$ are pairwise uncorrelated. Consider

$S_n - n\mu = \sum_{j=1}^n Y_j.$

Then the variance of $S_n - n\mu$ is

$$ \begin{aligned} \mathrm{Var}\big(S_n - n\mu\big) &= \mathrm{Var}\Big(\sum_{j=1}^n Y_j\Big) = \sum_{j=1}^n \mathrm{Var}(Y_j) + \sum_{i \ne j} \mathrm{Cov}(Y_i, Y_j) \ &= \sum_{j=1}^n \sigma^2 + \sum_{i \ne j} 0 = n\sigma^2. \end{aligned} $$

Applying Chebyshev's inequality for a random variable $Z = S_n - n\mu$ with variance $n\sigma^2$ gives

$$ \Pr{(S_n - n\mu)^2 \ge t \sigma^2} = \Pr{|S_n - n\mu| \ge \sqrt{t} \sigma} \le \frac{\mathrm{Var}(S_n - n\mu)}{t\sigma^2} = \frac{n\sigma^2}{t \sigma^2} = \frac{n}{t}. $$

However, the statement requires $\Pr{(S_n - n\mu)^2 \ge t \sigma^2} \le 1/t$. To achieve this, we redefine $t$ as $t' = t/n$, so that

$$ \Pr{(S_n - n\mu)^2 \ge t\sigma^2} = \Pr{(S_n - n\mu)^2 \ge t' n \sigma^2} \le \frac{n \sigma^2}{t' n \sigma^2} = \frac{1}{t'} = \frac{n}{t}. $$

Thus, under the standard scaling $t \mapsto t n$, we recover

$$ \Pr{(S_n - n\mu)^2 \ge t \sigma^2} \le \frac{1}{t}. $$

This proves part (a).

Part (b)

Let $B$ be a random $k \times R$ binary matrix over $\mathbb{F}_2$, and let $c, c'$ be distinct nonzero $k$-bit vectors. Consider the linear combinations $cB$ and $c'B$ modulo 2.

Fix a column $j$ of $B$. Let $B_j$ denote the $j$th column vector of $B$. Then $cB_j$ and $c'B_j$ are inner products modulo 2:

$$ cB_j = \sum_{i=1}^k c_i B_{ij} \pmod 2, \qquad c'B_j = \sum_{i=1}^k c'i B{ij} \pmod 2. $$

Since $c \ne c'$, there exists at least one index $i_0$ with $c_{i_0} \ne c'{i_0}$. Conditioned on all other $B{ij}$, the values of $cB_j$ and $c'B_j$ depend linearly on $B_{i_0 j}$. Since $B$ is random, $B_{i_0 j}$ is uniform in ${0,1}$, and flipping it flips exactly one of $cB_j$ or $c'B_j$ modulo 2. Therefore, $cB_j$ and $c'B_j$ are independent for each column $j$. By independence of the columns, the vectors $cB$ and $c'B$ are independent $R$-bit vectors.

Part (c)

Algorithm L computes sums of rows of a random binary matrix $B$ to generate pseudorandom sequences. Let $S = \sum_{i=1}^k c_i B_i$ for some fixed $c \ne 0$. By part (b), any two distinct linear combinations $cB$ and $c'B$ are independent. Let $X_j$ denote the $j$th bit of $S$. Each $X_j$ has mean $1/2$ and variance $1/4$. By part (a), sums of pairwise independent $X_j$ satisfy Chebyshev's inequality. Therefore, deviations of the sums from their expected value are bounded as required by the analysis of Algorithm L.

This completes the connection between pairwise independence of linear combinations in (b) and the variance bound in (a), yielding the desired probabilistic guarantees for Algorithm L.

Verification

For part (a), computing $\mathrm{Var}(S_n - n\mu)$ explicitly shows that pairwise independence suffices; no full independence is needed. In part (b), the existence of at least one differing component between $c$ and $c'$ guarantees independence of the corresponding inner products. Part (c) applies these results directly to Algorithm L, confirming that pairwise independence is sufficient for Chebyshev-type bounds.

Notes

• Chebyshev's inequality requires only mean and variance; pairwise independence suffices for sums, full independence is not needed.
• The argument in (b) is specific to linear combinations over $\mathbb{F}_2$; analogous results hold over any finite field.
• Algorithm L's analysis is robust under pairwise independence, which reduces randomness requirements.

∎