Here the "first algorithm" refers to essentially the Bottom-k algorithm with k=1.

In the first algorithm for estimating the number of distinct elements, our estimator was E(z) = 1/2 1. Is E(2) an unbiased estimator (i.e., does E[E(z)] equal to the real number of distinct elements) ? Now, suppose we were to take k independent copies z1, ... Zk of the basic estimator. (In other words, each Zj, for E [k], is the minimum of the hash values hj(i) over elements i encountered in the stream, where each hj is an independent random hash function.) Consider the estimator E'(z) = k-1 E(zi) 3-1. Prove that E' is not a good estimator for any arbitrarily large k: e.g., it is not true that it is a 2-approximation with probability at least 90%. (It is ok to fix d to a concrete value if that is convenient.) Justify your answers. In the first algorithm for estimating the number of distinct elements, our estimator was E(z) = 1/2 1. Is E(2) an unbiased estimator (i.e., does E[E(z)] equal to the real number of distinct elements) ? Now, suppose we were to take k independent copies z1, ... Zk of the basic estimator. (In other words, each Zj, for E [k], is the minimum of the hash values hj(i) over elements i encountered in the stream, where each hj is an independent random hash function.) Consider the estimator E'(z) = k-1 E(zi) 3-1. Prove that E' is not a good estimator for any arbitrarily large k: e.g., it is not true that it is a 2-approximation with probability at least 90%. (It is ok to fix d to a concrete value if that is convenient.) Justify your answers