Question

Suppose you have a true random bit generated where each bit in the generated stream has the same probability of being a 0 or 1 as any other bit in the stream and that the bits are not correlated; that is the bits are generated from identical independent distribution. However, the bit stream is biased.

Answer 1

c) We consider the original stream as a sequence of pairs. The pairs are clearly independent, so to find the
expected number of bits in the output we need to find the probability that 01 or 10 occurs. This probability
equals $2(\frac{1}{2} + \delta )(\frac{1}{2} - \delta ) = \frac{1}{2} - \delta ^2.$

Thus, if the original stream contains n bits (assume it is even), then the expected number of output bits

$\frac{n}{2}(\frac{1}{2} -2 \delta ^2).$

If we want to obain x output bits, the expected number of original bits is:

$\frac{2x}{\frac{1}{2} -2 \delta ^2}.$

d) The output stream is not independent. Indeed, if some output bit is 0, that is, the original stream contains
pair 01, then the next pair starts with 1. If it is 10 then the next output bit is 1. If the original stream contains
several consequent 1s, then some pairs are 11 and therefore skipped. But then, the first pair that is not skipped
must be 10. In a similar way, after each 1 in the output stream we must have a 0. Thus the output stream looks
like 01010101...