The Flajolet-Martin Algorithm. The analysis of FM in LRU (and in class) assumed that the data stream was drawn from a universe of an unlimited number of unique entities. That is, there was nowhere a limit on the number of bits of the label. That is why we obtained a probability of of the tail length being at least r, for any r, no matter how large.

In this problem, let us impose a bound on the number of bits of the labels. In particular, all labels are n bits long (this places an upper bound of n on the tail length).

(a) Derive an expression for the probability mass function of the maximum tail length conditioned on the number of unique elements in the stream. That is, obtain gT|U(t, u) = Prob{Max tail length, T = t|no of unique elements,U = u}.

(b) From (a), obtain the mean tail length if the number of unique elements is U = u (this is a conditional expectation of the tail length). You can leave this as a sum.

(c) From (a), obtain the mean square error of your estimate of 2T for U, i.e., write an expression for the root mean square error . (No need to simplify it to a closed form; you can leave it as a summation.)

That is, you are assuming a value for U is given and calculating the mean square error of the estimate based on this.

root mean square error pE[(2T U)2]. (No need to simplify it to a closed form; you can leave it as a summation.)

That is, you are assuming a value for U is given and calculating the mean square error of the estimate based on this.

Next, fix n = 20 and plot the root mean square error divided by U as a function of U, for U = , where k takes the values 10 to 15, in steps of 1. That is, your x-axis will be k and the y axis will be the square root of the mean square error divided by U.

E|(27 U)2 E|(27 U)2