5 Pseudo-independent block generation and amplification
A map \(G:\{ 0,1\} ^m\to (\{ 0,1\} ^n)^k\) is a pseudo-independent block generator with parameter \(\varepsilon \) if for every sequence of sets \(A_1,\ldots ,A_k\subseteq \{ 0,1\} ^n\),
where \((y_1,\ldots ,y_k)=G(x)\) for uniform \(x\) and \(p_i=|A_i|/2^n\).
If \(G:\{ 0,1\} ^m\to (\{ 0,1\} ^n)^k\) is a pseudorandom generator for \(\operatorname {Space}(\log (k+2))\) and block size \(n\) with parameter \(\varepsilon \), then \(G\) is a pseudo-independent block generator with parameter \(\varepsilon \).
Given \(A_1,\ldots ,A_k\), build a finite state machine with states \(0,1,\ldots ,k\) and an extra fail state. The start state is \(0\), the only accepting state is \(k\), the edge from \(i-1\) to \(i\) is labelled by \(A_i\), and the edge from \(i-1\) to \(\mathsf{fail}\) is labelled by \(\{ 0,1\} ^n\setminus A_i\). The machine has \(k+2\) states, hence uses \(\log (k+2)\) space. Under uniform independent blocks its acceptance probability is \(p_1\cdots p_k\); under the generator it is exactly the left probability in Definition 32. The block-PRG guarantee gives the claimed error.
There is a constant \(c{\gt}0\) such that for all integers \(R\) and \(k\le 2^R\), there is an explicit pseudo-independent block generator with parameter \(2^{-R}\) that converts \(cR\log k\) random bits into \(k\) strings of length \(R\).
Apply Lemma 23 with block length \(\Theta (R)\), space at least \(\log (k+2)\), and enough recursive levels to output at least \(k\) blocks. Since \(k\le 2^R\), the required number of levels is \(O(\log k)\) and lies in the permitted range after adjusting the absolute constant. If the block length is larger than \(R\), discard excess bits from each block. Proposition 33 converts the block-space guarantee into pseudo-independence, and the seed consists of \(O(\log k)\) hash descriptions of size \(O(R)\).
Let a one-sided-error randomized algorithm use \(R\) random bits and succeed on yes-instances with probability at least \(1/2\). For every \(k\le R\), one can run \(k\) amplified trials using \(O(R\log k)\) random bits and reduce the probability that all trials fail to \((1+o(1))2^{-k}\). More generally, if the success probability is at least \(1/\operatorname {poly}(k)\), polynomially many trials reduce failure to \(2^{-k}\) while still using \(O(R\log k)\) random bits.
Let \(A_i\) be the set of random strings on which the \(i\)-th trial fails. For independent trials, the probability that all \(k\) trials fail is the product of their individual failure probabilities, at most \(2^{-k}\) in the probability-\(1/2\) case. Theorem 34 makes the joint failure probability differ from this product by at most \(2^{-R}\), which is lower order for \(k\le R\). If each trial succeeds with probability \(1/\operatorname {poly}(k)\), take \(\operatorname {poly}(k)\) trials so that the independent failure product is at most \(2^{-k}\), and apply the same pseudo-independence estimate.
The pseudo-independent block generator also amplifies BPP-type algorithms: if each trial is correct with probability at least \(2/3\), then using \(O(R\log k)\) random bits for \(k\) generated trials and taking the majority reduces the error exponentially in \(k\), up to the generator error.
For each subset \(T\) of more than \(k/2\) trials, let \(A_i\) be the bad-randomness set for trial \(i\) if \(i\in T\) and the full space otherwise. Pseudo-independence bounds the probability that all trials in \(T\) are bad by the corresponding independent product plus \(2^{-R}\). Summing over all majority-size subsets gives the usual Chernoff-style exponential upper bound, with the accumulated additive error controlled by choosing the theorem’s parameter smaller than the target final error. Thus majority voting behaves as it would under independent randomness, up to the pseudorandom error.