sages that can be encrypted using k$)?$

Suppose you have a true random bit generator 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 dis$-$

tribution. However, the bit stream is biased. The probability of a $1$ is $0\mathrm{.}5+$ a and the

probability of a $0$ is $0\mathrm{.}5-$ a$,$ where $0<$ a $<0\mathrm{.}5.$ A simple conditioning algorithm is

as follows: Examine the bit stream as a sequence of nonoverlapping pairs. Discard all

$00$ and $11$ pairs. Replace each $01$ pair with $0$ and each $10$ pair with $1.$

a$.$ What is the probability of occurrence of each pair in the original sequence?

b$.$ What is the probability of occurrence of $0$ and $1$ in the modified sequence?

c$.$ What is the expected number of input bits to produce x output bits?

d$.$ Suppose that the algorithm uses overlapping successive bit pairs instead of non$-$

overlapping successive bit pairs. That is$,$ the first output bit is based on input bits $1$

and $2,$ the second output bit is based on input bits $2$ and $3,$ and so on$.$ What can you

say about the output bit stream?