A Better Linear Unbiased Estimator for Averages over Discrete Structures

Given an i.i.d. sample drawn from some probability distribution on a finite set, the best (in the sense of least variance) linear unbiased estimator (BLUE) of the average of any quantity with respect to that distribution is the sample average of the quantity. Here we consider the situation in which, together with the sample, also the probability mass (possibly unnormalized) at each sample point is provided. We show that with that information BLUE can be systematically improved. The proposed procedure is expected to have applications in statistical physics, where it is common to have a closed-form specification of the relevant (unnormalized) probability distribution.