Question

What is the expected error by the estimator Chernoff bound on the samples performed without replacement?

(a) O (log k!)

(b) O (k!)

(c) O (k^2)

(d) O (1/k½)

This interesting question is from Hash Tables topic in section Hash Tables of Data Structures & Algorithms I

I had been asked this question during an online exam.

Answer 1

The correct choice is (d) O (1/k½)

The best explanation: The expected error for estimating the Jaccard index using MinHash scheme for k different hash functions is O (1/k½). The expected error by the estimator Chernoff bound on the samples performed without replacement is O (1/k½).