Please mention any concerns that you have with the given question by commenting because there is no reason to "revise" this question...

And the question is complete, it is about Counting the number of tokens in a stream (not the number of distinct tokens). Also, read the disclaimer.

Counting the Number of tokens in a stream It is trivial to see that if there are m tokens in the stream, then [logzml many bits suffice to keep track of the number of tokens. Now consider the following randomized algorithm. Probabilistic Counting: Initialize X = 0. While stream is non-empty With probability zix, incrementX ( X + 1. End While Return 2" 1. In the following, let Y be the final value returned by the algorithm. a) Show that E[Y] = n + 1 b) Show that Var[Y] = n(n 1)/2 c) It can be shown that the value ofX 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 algorithm to return an estimator with error E with probability at least 1 5 using at most 0(i log lloglogm) (with high probability), where E, 5 > 0. 2 6' 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 1 (1+a)x , for some a > 0 given algorithm as follows - you increment X with probability (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 IY ml S m 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