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.
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