Random Algorithm HW 9.12March 27, 2006aFirst it is clear that the extracted bits are independent since x2i−1,x2iare independent ondifferent i.So we only need to sh ow the ith bit has equal probability to be 1 or 0. This is actually alsoquite obvious since the probability for the original bias coin to generate a (heads,tails) isthe same as to generate a (tails, heads) since they are independent trails.bThere are bn2c pairs. One pair will only generate a bit if it is a (heads,tails) or (tails,head).The expected number of bits one single pair will generate is p(1 − p) + (1 − p)p = 2p(1 − p)by the linearity of expectation. The expected total number of bits will be bn2c2p(1 − p)cY is a sequence of independent trials with head probabilityp2p2+(1−p)2. So from the result of(a), running A on Y would produce bits that are independent and unbiased. Furthermore,since the original trials are ind ependent and the sequence X and Y will generate bits on aremutually exclusive. So the bits generated from Y are independent from the bits generatedfrom X.dZ is a sequence of independent trials with head probability p2+ (1 − p)2. So the bitsextracted from Z using A is independent and unbiased. It is also independent f rom X andY, since giving X and Y will not affect Z.eFrom th e result of (b),(c) and (d), th e total number of bits generated is th e sum of thosegenerated from X, Y, ZSo, A(p) = P rob(Xwillgenerateabit)∗A(X)+P rob(Y w illgenerateabit)∗A(Y )+P rob(Zwillgenerateabit)∗A(Z) = p(1 − p) +12∗ (p2+ q2)A(p2p2+q2) +12∗ A(p2+ q2)fSubstitute the function A with the entropy function H. The recursive function
View Full Document
Unlocking...