Thursday, May 11, 2006

A lemma

When I was a graduate student, I wanted to learn a lemma a day (may be I should have set my sights higher and targeted a theorem a day, sigh). Here is a cute lemma.

Consider f_1,f_2,..,f_n such that each f_i is non-negative and not all 0. If (\sum_i f_i) (\sum_i (i^2 f_i))= (\sum_i (i f_i))^2, then there exists a unique f_i not equal to 0.

Sumit Ganguly uses this claim and shows a proof in his paper on Counting distinct elements over update streams.

0 Comments:

Post a Comment

<< Home