The question is Updated !

Read about "Morris's Algorithm of Counting\" before attempting Counting the Number of tokens in a stream (Not Distinct) 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: LetX ( 0 . While stream is non- empty With probability, incrementX 0. For this part, we consider an alternate (and somewhat more elegant) way of modifying the basic estimator1 to achieve better estimates. Suppose you modify the given algorithm as follows - you increment X with probability (1:61),, , 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 nd an estimate Y such that IY ml S em with probability at least 9/10? [1] Basic estimator (For Distinct Counting): 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 Y