This question is related to "Morris's Algorithm" (google "Morris's Algorithm counting")

A little background information for "Approximate Counting" algorithms (Actual question is after this):

This question demands knowledge of Hashing and Streaming Algorithms!

Algorithm using basic estimator: Let Y ( 1 h : {1, 2, .., n} > [0,1] (h is an idealized hash func) While (stream is non-empty) Let i be the next element/token 1' S i using Chebyshev's Inequality. n+1 n+1 52 Algorithm using parallel estimator: Run k independent copies of the basic estimator: Y1,Y2, , Yk. 1 \"52'? I 1 Return E 1 _ L E[Z] _ n+1' VaT[Z] n+1 S E_ 4(settlngk _ 52)" To put this probability to be at most 6, put k = i Space: 0(k). The actual Question: Counting the Number of tokens in a stream It is trivial to see that if there are m tokens in the stream, then [logzm] many bits sufce to keep track of the number of tokens. Now consider the following randomized algorithm. Probabilistic Counting: Let X - 0. While stream is non-empty With probability ~x , increment X - X + 1. End While Return 24 - 1. In the following, let Y be the final value returned by the algorithm. m = number of tokens in the entire stream a) Show that E [Y] = m b) Show that Var[Y] = m(m - 1)/2 c) It can be shown that the value of X grows only till loglogm with high probability - the proof is highly non-trivial and we just need to believe this for now. Using this fact, the analysis above and the idea of using parallel estimators, show how to modify the basic estimator algorithm to return an estimator with error e with probability at least 1 - 6 using at most O(-2 log -loglogm) (with high probability), where E, 6 > 0. d) For this part, we consider an alternate (and somewhat more elegant) way of modifying the basic estimator to achieve better estimates. Suppose you modify the given algorithm as follows - you increment X with probability (14a)x' -, for some a > 0 (a = 1 in the above algorithm). What should the algorithm return now? Determine the value of a that you need to choose in order to find an estimate Y such that |Y - m|