3 The recursive generator and its block-space analysis
Let \(Q\) be a finite state machine with \(s\) states over alphabet \(\{ 0,1\} ^n\) and let \(D\) be a distribution on \((\{ 0,1\} ^n)^k\). The matrix \(Q(D)\) is the \(s \times s\) matrix whose \((i,j)\) entry is the probability that \(Q\), started at state \(i\), reaches state \(j\) after reading a random sequence drawn from \(D\). Let \(U_n\) denote the uniform distribution on \(\{ 0,1\} ^n\).
For a vector \(x \in \mathbb R^s\), set \(\left\| x\right\| _1=\sum _i |x_i|\). For an \(s \times s\) matrix \(M\), set
All matrix norms in this blueprint use this induced one-norm.
For compatible real matrices \(M,N\): \(\left\| M+N\right\| _1\le \left\| M\right\| _1+\left\| N\right\| _1\), \(\left\| MN\right\| _1\le \left\| M\right\| _1\left\| N\right\| _1\), \(\left\| M\right\| _1=\max _i\sum _j |M_{ij}|\) in the row-vector convention of the paper, if every entry of an \(s \times s\) matrix has absolute value at most \(\eta \) then \(\left\| M\right\| _1\le s\eta \), and every transition probability matrix has norm \(1\).
The first two inequalities follow immediately from the triangle inequality and the definition of the induced norm. The formula \(\left\| M\right\| _1=\max _i\sum _j |M_{ij}|\) is obtained by bounding \(\sum _j|\sum _i x_iM_{ij}|\) by \(\sum _i |x_i|\sum _j|M_{ij}|\) and taking \(x\) to be the basis vector on a row attaining the maximum. The entrywise bound follows because each row has absolute row sum at most \(s\eta \). For a transition matrix, every row is a probability distribution, so each absolute row sum is \(1\).
Fix a universal family \(\mathcal{H}\) of functions \(h:\{ 0,1\} ^n \to \{ 0,1\} ^n\). Define \(G_k:\{ 0,1\} ^n \times \mathcal{H}^k \to (\{ 0,1\} ^n)^{2^k}\) recursively by \(G_0(x)=x\) and
where \(\circ \) denotes concatenation of the two output block sequences.
For a finite state machine \(Q\), a sequence \((h_1,\ldots ,h_k)\) is \((\varepsilon ,Q)\)-good if
where \(G_k(*,h_1,\ldots ,h_k)\) is the distribution induced by a uniform \(x \leftarrow \{ 0,1\} ^n\).
For \(k=0\), the empty hash sequence is \((0,Q)\)-good for every finite state machine \(Q\).
Suppose Lemma 21 has been proved for \(k-1\). Then for random \(h_1,\ldots ,h_{k-1}\leftarrow \mathcal{H}\), the probability that \((h_1,\ldots ,h_{k-1})\) is not \(((2^{k-1}-1)\varepsilon ,Q)\)-good is at most \(2^{6w}(k-1)/(\varepsilon ^2 2^{2n})\).
This is exactly the inductive hypothesis in Lemma 21 with \(k\) replaced by \(k-1\).
Fix \(h_1,\ldots ,h_{k-1}\). For states \(i,\ell ,j\) of a \(2^w\)-state machine \(Q\), let \(B_{i,\ell }^{h_1,\ldots ,h_{k-1}}\) be the set of seeds \(x\) for which \(G_{k-1}(x,h_1,\ldots ,h_{k-1})\) takes \(Q\) from \(i\) to \(\ell \). With probability at least \(1-2^{6w}/(\varepsilon ^2 2^{2n})\) over \(h_k\leftarrow \mathcal{H}\), the function \(h_k\) is \((2^{-2w}\varepsilon ,B_{i,\ell },B_{\ell ,j})\)-independent for every triple \(i,\ell ,j\).
For a fixed triple \(i,\ell ,j\), apply Lemma 10 with \(A=B_{i,\ell }\), \(B=B_{\ell ,j}\), and tolerance \(2^{-2w}\varepsilon \). Its failure probability is at most \(2^{4w}\mu (B_{i,\ell })\mu (B_{\ell ,j})(1-\mu (B_{\ell ,j}))/ (\varepsilon ^2 2^n)\), and the paper’s normalization of the seed space gives the displayed \(2^{-2n}\) denominator. Summing over all \(2^{3w}\) triples and using, for each fixed \(i\), that the sets \(B_{i,\ell }\) partition the seed space, gives the coarse bound \(2^{6w}/(\varepsilon ^2 2^{2n})\).
If the simultaneous independence event of Lemma 18 holds, then
By Construction 14, the \((i,j)\) entry of \(Q(G_k(*,h_1,\ldots ,h_k))\) is
The corresponding \((i,j)\) entry of \(Q(G_{k-1}(*,h_1,\ldots ,h_{k-1}))^2\) is \(\sum _\ell \mu (B_{i,\ell })\mu (B_{\ell ,j})\). Each summand differs by at most \(2^{-2w}\varepsilon \) under the event of Lemma 18; after summing over at most \(2^w\) intermediate states, every entry differs by at most \(2^{-w}\varepsilon \). Lemma 13 then bounds the matrix norm by \(\varepsilon \).
If \((h_1,\ldots ,h_{k-1})\) is \(((2^{k-1}-1)\varepsilon ,Q)\)-good, then
Let \(M=Q(G_{k-1}(*,h_1,\ldots ,h_{k-1}))\) and \(N=Q((U_n)^{2^{k-1}})\). Since two independent uniform halves form \((U_n)^{2^k}\), the target matrix is \(N^2\). Hence
Both \(M\) and \(N\) are transition matrices, so their norms are \(1\) by Lemma 13. Goodness gives \(\left\| M-N\right\| _1\le (2^{k-1}-1)\varepsilon \), and the displayed bound follows.
Let \(\mathcal{H}\) be a universal family of functions \(\{ 0,1\} ^n\to \{ 0,1\} ^n\), let \(Q\) be a finite state machine of size \(2^w\), and let \(k\ge 0\). Then
The case \(k=0\) is Lemma 16. For \(k{\gt}0\), expose \(h_1,\ldots ,h_{k-1}\) and \(h_k\). Event one is that the first \(k-1\) hashes are good; its failure probability is bounded by Lemma 17. Event two is the simultaneous independence of the last hash; its failure probability is bounded by Lemma 18. By the union bound, both events fail with total probability at most \(2^{6w}k/(\varepsilon ^2 2^{2n})\). If both events hold, the triangle inequality plus Lemmas 19 and 20 give
Therefore the complement of the good event has the stated probability.
If \((h_1,\ldots ,h_k)\) is \((\eta ,Q)\)-good, then the difference between the acceptance probability of \(Q\) on a uniform string in \((\{ 0,1\} ^n)^{2^k}\) and on \(G_k(x,h_1,\ldots ,h_k)\) with uniform \(x\) is at most \(\eta \).
Let \(e_{\mathsf{start}}\) be the row vector concentrated on the start state and let \(1_{\mathsf{accept}}\) be the column vector that is \(1\) on accepting states and \(0\) elsewhere. The two acceptance probabilities differ by
The vector \(e_{\mathsf{start}}\) has one-norm \(1\), and every entry of \(1_{\mathsf{accept}}\) has absolute value at most \(1\). The induced matrix norm therefore bounds the absolute value of the expression by \(\eta \).
There is a constant \(c{\gt}0\) such that for all integers \(n\) and \(k\le cn\), the recursive generator \(G_k:\{ 0,1\} ^n\times \mathcal{H}^k\to (\{ 0,1\} ^n)^{2^k}\) is a pseudorandom generator for \(\operatorname {Space}(cn)\) and block size \(n\) with parameter \(2^{-cn}\).
Fix a \(2^{cn}\)-state machine \(Q\). The acceptance gap is at most the probability that the sampled hash sequence is not good, plus the worst acceptance gap conditioned on goodness. Lemma 22 bounds the second term by the goodness parameter. Lemma 21 bounds the first term by \(2^{2k}2^{6cn}k/(\varepsilon ^2 2^{2n})\) after choosing the good parameter so that \((2^k-1)\varepsilon \) is the final norm error. Taking, for example, \(c=0.05\) and the paper’s \(\varepsilon =2^{-cn-1}\) makes the sum at most \(2^{-cn}\) for every \(k\le cn\). This is precisely Definition 2.