Generating pairwise independent bits

Question

Following the algorithm below, it's possible to generate $2^N-1$ pairwise independent bits from N independent random bits:

If I am using these pairwise independent bits to derandomize an algorithm and realize that I need additional bits, is it possible to generate more pairwise independent bits on the fly without repeating the whole process?

Answer 1

Yes, it is possible to use one more independent random bit, to double the number of pairwise independent bits you have produced so far (more accurately, to go from $2^N - 1$ to $2^{(N+1)} - 1$).

Let $l$ be a list containing the same $2^N - 1$ bits you generated earlier, as well as a new bit set to $0$. Toss a "purely random" coin (i.e. read another uniformly distributed, independent bit). If it comes out "heads" return $l$ as is. Else return $\neg l$ (i.e. flip every one of the bits in $l$ before outputting it).

This construction produces uniformly, pairwise independent bits, because:

1. The newly generated bits are uniformly distributed (since the final step was to flip them with probability $1/2$).
2. No two of the new bits are correlated, since up to a global value XORed to both of them, they are generated just like the original (pairwise independent distribution).
3. No pair of old bit and new bit can be correlated, since the final step of the construction involves XORing a random bit (independent of any of the old bits) to all the new bits.

In fact, the distribution obtained by this method is the same distribution as would have been obtained by the original construction, if it had been this large from the start.