Read about "Morris's Algorithm of Countingf' 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 suffice to keep track of the number of tokens. Now consider the following randomized algorithm. Probabilistic Counting: LetX ( 0 . While stream is non-emplty With probability21X incrementX ( X + 1. End While Return 2X - 1 In the following, let Y = 2". m = number of tokens in the entire stream E[Y] = m + 1 (Can be proven Inductively) Var[Y] = m(m - 1)/2. 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 (\"lay , 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? [1] Basic estimator (For Distinct Counting): Let Y [0,1] (h is an idealized hash func) While (stream is non-empty) Let i be the next element/token Y ( min{ Y, h(i)] Return % 1 Space: Just the number of bits to represent Y. 1 Var [Y] S (M 1)2 Probability of error E(that the error is more than allowed): P \"Y S i using Chebyshev's Inequality. n+1 n+1 E2 using Chebyshev's Inequality