Read about \"Morris's Algorithm of Counting\" before attempting 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 suffice to keep track of the number of tokens. Now consider the following randomized algorithm. Probabilistic Counting: Let X 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 1 (1+a)x ' given algorithm as follows - You increment X with probability 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 ml 5 em with probability at least 9/10? Disclaimer: The solution to the above problem can be found on the internet with a little effort. But I need an answer with good and legit explanation. [1] Basic estimator: LetY [0,1] (h is an idealized hash func) While (stream is non-empty) Let i be the next element/token Y 4- min { Y, h(i)} Return % 1 Space: Just the number of bits to represent Y. 1 . , . Var[Y] S (n+1? usmg Chebyshev s Inequality. Probability of error (that the error is more than allowed): 1 e 1 . , . P \"Y El > m S 5 using Chebyshevs Inequality