Pseudorandom Generator

Question

In a cryptographic application, two types of (pseudo)random bit streams are needed:

• a stream $A= a_{1}a_{2}a_{3}\ldots$ in which $\Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i$ and
• a stream $B= b_{1}b_{2}b_{3}\ldots$ in which $\Pr[b_{i}=0]=2/3; \Pr[b_{i}=1]=1/3\ \forall i$.

Propose the following constructions:

1. Given a generator $G_{A}$ for $A$, propose an efficient construction that uses $G_{A}$ to generate $B$.
2. Given a generator $G_{B}$ for $B$, propose an efficient construction that uses $G_{B}$ to generate $A$.

I don't need the solution to this question. I want to know, how to think about this problem to get a solution. I know basic definition of Pseudorandom generator.

Answer 1

The hints given refer to unbiasing algorithms, which is the standard answer in cryptography. However, there is a very nice and different solution for the example of generating the $(2/3,1/3)$ distributed bits from an unbiased stream which I will mention here. For clarity call the output symbols $a$ and $b$ with $p_a=2/3=1-p_b$ instead of using binary symbols

Expand the probabilities in base 2 to get: $$ \frac{2}{3}=0.101010101010\ldots $$ and $$ \frac{1}{3}=0.0101010101\ldots $$ which means these probability atoms have dyadic expansions $$ \frac{2}{3}=\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\cdots=\frac{1/2}{1-{1/4}} $$ and $$ \frac{1}{3}=\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\cdots=\frac{1/4}{1-{1/4}} $$ This decomposition yields the following infinite tree which generates the symbols required:

if the unbiased bit is 0 go left, otherwise go right, when an $a$ or $b$ is emitted start again;

(the first left branch should have the symbol $a$).

In Chapter 5 of Cover & Thomas' Elements of Information Theory book it is proved that this procedure is optimal, i.e., it gives a tree of expected minimum length generating this distribution.

Edit: As in the comments by @supercat, if $p$ is unknown but the input bits are independent, one can group say $3-$tuples into two sets of desired probability ratio, and also try to maximize the probability that a bit is actually output. $k=3$ is convenient for this case since the binomial coefficients $\binom{3}{j}$ are divisible by 3, if we ignore the first and last coefficient, so the grouping to obtain a $(1/3,2/3)$ probability [when symbols are output] becomes possible. Concretely

If you see 100 or 011, output $b$. If you see 010, 001, 101, or 110, output $a.$ If you see 000 or 111, throw out the bits and try again.