Q1) Suppose you have a true random number generator where ach 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 distributions. However, he bit stream is biased. The probability of a 0 is 0.5 + ε and the probability of a 1 is 0.5 - ε. (0 < ε < 0.5). A simple deskewing algorithm is to look at the bit stream as a sequence of non-overlapping pairs. Discard all 00 and 11 pairs. Replace each 01 pair with 0 and each 10 pair with 1.

Part A: What is the probability of occurrence of each of the four pairs in the original sequence? Show your work.

Part B: What is the probability of occurrence of 0 and 1 in the modified sequence? Show your work.

Part C: What is the expected number of output bits that will be produced by 2x input bits? Show your work.