Easier Estimation of Extremes under Randomized Response
share
In this brief note, we consider estimation of the bitwise combination x_1 … x_n = max_i x_i observing a set of noisy bits x̃_i ∈{0, 1} that represent the true, unobserved bits x_i ∈{0, 1} under randomized response. We demonstrate that various existing estimators for the extreme bit, including those based on computationally costly estimates of the sum of bits, can be reduced to a simple closed form computed in linear time (in n) and constant space, including in an online fashion as new x̃_i are observed. In particular, we derive such an estimator and provide its variance using only elementary techniques.
READ FULL TEXT