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: Let X [0,1] (h is an idealized hash func) While (stream is non-empty) Let i be the next element/token Y i S i using Chebyshev's Inequality. n+1 n+1 52