Initial Reading (MANDATORY) -

1. https://drive.google.com/file/d/1drwST1verBJLkLjJIMOBjcsyHrUJA_zm/view?usp=sharing
2. https://drive.google.com/file/d/1THS0UqNQRqHEy4Hj-Ge8CSPIDZnBHmNe/view?usp=sharing

****** I HAVE REVISED THE QUESTION MANY TIMES, IT DOES NOT NEED ANY MORE REVISION ********

IF there is ANY doubt, please COMMENT !

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: LetX 0. 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 6111 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