Collaborative Problem-CLRS 5-1: With a b-bit counter, we can ordinarily only count up to 2b -1. With R. Morris's probabilistic counting, we can count up to a much larger value at the expense some loss of precision. We let a counter value i represent a count of n fori 0,1,..., 26-1, where the ni form an increasing sequence of nonnegative values. We assume that the initial value of the counter is 0, representing a count of no 0. The INCREMENT operation works on a counter containing the value i in a probabilistic manner. If 261, then the operator reports an overflow error. Otherwise, the INCREMENT operator increases the counter by 1 with probabilities 1/(ni+ ), and it remains unchanged with probability 1-1/(ni+1-i) If we select ni for all i 2 0, then the counter is an ordinary one. More interesting situations arise if we select, say, n2fori0 or nF (the ithe Fibonacci number-See Section 3.2 in the text) For this problem, assume that n2b-1 is large enough that the probability of an overflow error is negli- gible (a) [20 points] Prove that the expected value represented by the counter after n INCREMENT operations have been performed is exactly n. (b) [20 points] The analysis of the variance of the count represented by the counter depends on the sequence of the ni. Let us consider a simple case: n 100i for all i 2 0. Determine the variance in the value represented by the register after n INCREMENT operations have been performed