will be easier to apply the expectation to.
So the counter times s(i)- f(i) the entire thing squared can do it in
estimation over J different from I.
J prime, different from I of the products of the frequencies, fJ and
fJ prime times the product of sine times the sine of i squared.
Now of course the sine of i squared is nothing but 1.
So, what we get is a double estimation over a pair of items j and
j prime that are distinct from i of the product of their frequencies and
the product of their sines.
So, now if we take the expectation of this quantity,
we'll see that the following happens.
If we look at a term in this double summation that corresponds to j
different from j prime.
Then the expectation of the product of the sines is exactly zero by the same
token in our mean analysis.
So, what we get is that all terms with j distinct from j
prime are zero in expectation.
And so the variance, is exactly the summation of all data items in
the universe other than i of their frequency squared.
Okay, so we have been able to construct a randomized estimate for
the frequency of any fixed item i.
And we have been able to balance variants, so we would like to now conclude
by Chebyshev's inequality our estimate is good.
Meaning that our estimate is close to its mean
the frequency of i with high probability.
But in order to do that,
we need to check that the square root of the summation over other data items j of
their frequency squared is actually small compared to the frequency of our item i.
Now, this is not generally true.
This depends on the actual stream, and
on the actual item that we're trying to estimate.
So, let's look at some examples,
because these examples will show when our estimate works well, and when it does not.
This will inform us in using our basic estimate that we just constructed as
a building block for the full algorithm in the rest of the lecture.
Okay, so this is our expression for the variance.
And again, think of item I as fixed, this is the item that we're trying to estimate.