Explain estimating moments with example.

Estimating Moments :-

• Estimating moments is a generalization of the problem of counting distinct elements in a stream. The problem, called computing "moments," involves the distribution of frequencies of different elements in the stream.

• Suppose a stream consists of elements chosen from a universal set. Assume the universal set is ordered so we can speak of the $i^{th}$ element for any i.

• Let $m_i$ be the number of occurrences of the $i^{th}$ element for any i. Then the $k^{th}$-order moment of the stream is the sum over all i of $(m_i)^k$

. For example :-

• The $0^{th}$ moment is the sum of 1 of each mi that is greater than 0 i.e., $0^{th}$ moment is a count of the number of distinct element in the stream.

• The 1st moment is the sum of the $m_i$ ’s, which must be the length of the stream. Thus, first moments are especially easy to compute i.e., just count the length of the stream seen so far.

• The second moment is the sum of the squares of the $m_i$’s. It is sometimes called the surprise number, since it measures how uneven the distribution of elements in the stream is.

• To see the distinction, suppose we have a stream of length 100, in which eleven different elements appear. The most even distribution of these eleven elements would have one appearing 10 times and the other ten appearing 9 times each.

• In this case, the surprise number is $10^2$ + 10 × $9^2$ = 910. At the other extreme, one of the eleven elements could appear 90 times and the other ten appear 1 time each. Then, the surprise number would be $90^2$ + 10 × 12 = 8110.