Easier Estimation of Extremes under Randomized Response

In this brief note, we consider estimation of the bitwise combination $x_1\vee \cdots \vee x_n={\max }_i{x}_i$ observing a set of noisy bits ${\tilde{x}}_i\in \{0,1\}$ that represent the true, unobserved bits $x_i\in \{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 ${\tilde{x}}_i$ are observed. In particular, we derive such an estimator and provide its variance using only elementary techniques.