6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint, working for both 1 and 2: devise a method that groups bits of what's available, and makes it's best to output what's needed (as a fallback, output nothing) $\endgroup$ – fgrieu Oct 9 at 6:37
  • $\begingroup$ There is a nice problem about generating random from biased dice. It has also at least two solution in our site. $\endgroup$ – kelalaka Oct 9 at 9:29
  • $\begingroup$ Is it still work if I say output $b_{i}=0$ if 0 or 10 comes and output $b_{i}=1 $ if 11 comes ??? @ fgrieu $\endgroup$ – Krishna Mallick Nov 11 at 6:58
7
$\begingroup$

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$).

here

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Another interesting variation is to design a construction that will work for any source which generates bits that are statistically independent, but whose bias may be unknown. To generate a 2/3-1/3 distribution from that, one could take trios of input bits. If 100 or 011, output a. If 010, 001, 101, or 110, output b. If 000 or 111, throw out the bits and try again. Not an optimal approach, but simple to understand, and it will work with any level of bias in the source. $\endgroup$ – supercat Oct 9 at 23:07
  • $\begingroup$ @supercat, of course, that is the standard approach I alluded to in my answer. $\endgroup$ – kodlu Oct 9 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.