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 [log2m] many bits suffice to keep track of the number of tokens. Now consider the following randomized algorithm. Probabilistic Counting: Let X - 0. While stream is non-empty With probability ~x , increment X . S =2 using Chebyshev's Inequality