Robust estimation of the mean probability of binary events: A low-complexity minimax approach

In this paper we present a simple procedure for estimating the mean probability of binary events from samples of heterogeneous size. The estimator is specifically designed to cope with heavy-tailed distribution of the data sample size. Starting from an heuristic identified in a previous work in the context of packet loss estimation, we distill a general hierarchical estimation problem where different-sized samples from multiple binary sources are available and the goal is to estimate the mean overall probability. We show by formal analysis that common estimators fail to provide a low-variance estimator for this problem when the distribution of the sample size is heavy-tailed. Then we propose a minimax optimization procedure to inject robustness, which ultimately yields a low-complexity estimator with general applicability. The derivation highlights also a surprising connection between the piecewise-linear structure of the estimator and the “water-filling” (max-min fair) structure arising as solution of a some resource allocation problems. Performance comparisons against a theoretical benchmark and conventional estimator are provided via Monte Carlo simulation.