A Better Linear Unbiased Estimator for Averages over Discrete Structures

Bastiaan J. Braams · 2025

Read A Better Linear Unbiased Estimator for Averages over Discrete Structures by Bastiaan J. Braams (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19294.txt.

Introduction

Bastiaan Braams wrote a 2025 paper on a better linear unbiased estimator for averages over discrete structures. Given a random sample from a distribution on a finite set, the sample average is the best such estimator in terms of low variance, when nothing else is known.

Braams adds one more input: the probability mass at each sample point, which may be unnormalized. With that extra fact, the classic estimator can be improved in a systematic way, step by step. He points to statistical physics as a prime field of use, since closed forms for such distributions are common there.

Catalog record

CREATORBastiaan J. Braams
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-19294

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Better Linear Unbiased Estimator for Averages over Discrete Structures Bastiaan J. Braams Abstract . 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. † † footnotetext: MSC2020: Primary 62F10. Introduction The present work is concerned with Monte Carlo evaluation of averages with respect to a probability distribution that is defined on a discrete space. Let D be that space and let p:D\to{\mathbb{R}}_{+} be an unnormalized probability distribution with (unknown) normalization constant Z . Using vector notation with vectors indexed over D , Z=p^{T}.e , where superscript T denotes the transpose and e is the all-ones vector. We consider the situation, common in statistical physics, that a sampling procedure is available to generate i\sim p/Z and that for each point in the sample the probability mass p(i) is given or can be computed. The result of a sampling process may be encoded in a count vector c:D\to{\mathbb{N}} , in which c(i) is the number of times that element i\in D is found in the sample. We imagine that a hash table will be used to store the nonzero c(i) together with the associated p(i) . Let f:D\to{\mathbb{R}} be a quantity of interest, and it is desired to estimate \bar{f}=Z^{-1}p^{T}.f . The standard Monte Carlo estimate, here expressed using the count vector c , is \bar{f}\simeq N^{-1}c^{T}.f . This estimator is linear in f and is unbiased, because for each i , c(i)/N is an unbiased estimate of p(i)/Z . It is known by the acronym BLUE, the Best Linear Unbiased Estimator. The question naturally arises, can we do better, and more specifically, can we do better within the class of linear unbiased estimators? In a standard setting in applied statistics, only the counts c(i) and function values f(i) are available, but in our setting in statistical physics, also the p(i) are known. We will show that indeed, using all the data, a better linear unbiased estimator is available. Given a count vector c that is the result of sampling independently N times from the distribution p/Z , define S\subseteq D by i\in S\Leftrightarrow 1\leq c(i) . S is a random set, and (given N , but before sampling) for any i\in D the probability of i\in S is q(i)=1-(1-p(i)/Z)^{N} : one minus the probability of obtaining c(i)=0 . It follows that the function w , defined on D by w(i)=p(i)/q(i) for i\in S and w(i)=0 for i\in D\setminus S , is an unbiased estimate of p . For \bar{f} this leads to the estimator \bar{f}\simeq Z^{-1}w^{T}.f , which is linear in f and unbiased. The inner product reduces to a sum over S only, just like the BLUE estimator. Note that the quantity Z is explicitly used here, and we will describe how to obtain it within the present context. For now, assume that Z is known. The primary objective of the present work is to show that the variance of the estimator \bar{f}\simeq Z^{-1}w^{T}.f is at most the variance of BLUE, up to a small correction associated with uncertainty in the normalization constant Z . The reduction of variance is significant if a significant fraction of the total mass of the distribution is concentrated on points that are expected to be found at least once in the sample. In the limit that all the mass is concentrated on such points, the proposed procedure tends smoothly to zero-variance exact summation. At the other extreme, if the probability distribution has a very small fraction of the total mass on points that may be expected to occur at least once in the sample, then the proposed procedure reduces to BLUE. Notation In the remainder of this manuscript we will employ some notational conventions associated primarily with E. W. Dijkstra [ 1 ] . If \mathop{\rm Op}\nolimits is any associative and commutative operation then \langle\mathop{\rm Op}\nolimits i,j:\mathop{\rm Dom}\nolimits(i,j):\mathop{\rm Fun}\nolimits(i,j)\rangle is the result of applying \mathop{\rm Op}\nolimits to the values \mathop{\rm Fun}\nolimits(i,j) as the indices i,j vary over the domain indicated by the boolean expression \mathop{\rm Dom}\nolimits(i,j) . This applies, for example, to sum ( \Sigma ), product ( \Pi ), Min, Max, set union and intersection, and existential and universal quantification. If f is a vector, matrix, function, or other structure that involves indices or arguments, and if \mathop{\rm Fun}\nolimits(f) is a boolean expression that may be understood pointwise, then [\mathop{\rm Fun}\nolimits(f)] means \mathop{\rm Fun}\nolimits(f) at all points of the domain of f . (Example: [0\leq f] to say that f is everywhere nonnegative.) We review some notation that has already been introduced and that will retain its meaning. D is the fixed finite domain of interest. It is expected to be made up of combinatorial objects and to be exponentially large in some natural parameter. Elements of D will be called points or objects, and we try to always use i to refer to an element of D . p:D\to{\mathbb{R}}_{+} is a probability distribution (possibly unnormalized) on D . Z=\langle\Sigma i:i\in D:p(i)\rangle is the normalization constant. f:D\to{\mathbb{R}} is a quantity of interest; i.e., we want to estimate averages \langle\Sigma i:i\in D:p(i)f(i)\rangle/\langle\Sigma i:i\in D:p(i)\rangle . In the context of sampling, N is the number of sample points including repetitions. Given N , but before drawing a sample, q:D\to[0,1] is defined by q(i)=1-(1-p(i)/Z)^{N} ; this is the probability that the point i is included in a sample obtained by N draws from p/Z . After the draw, c:D\to{\mathbb{N}} is the count vector associated with the sample. S is the set of points in D included in the sample. M=\mathop{\rm Card}\nolimits(S) , the cardinality of S . (Therefore, M=\langle\Sigma i:i\in S:1\rangle and N=\langle\Sigma i:i\in S:c(i)\rangle .) e is the base of the natural logarithm or it is the all-ones vector; I think that the two meanings will not be confused. For any subset D^{\prime}\subseteq D we use P(D^{\prime}) for the total mass on D^{\prime} : P(D^{\prime})=\langle\Sigma i:i\in D^{\prime}:p(i)\rangle . \mathop{\rm Char}\nolimits is the characteristic function of a relation ( \mathop{\rm Char}\nolimits({\rm false})=0 , \mathop{\rm Char}\nolimits({\rm true})=1 ). \mathop{\rm Card}\nolimits is used for the cardinality of a set. Determining the normalization constant If Z is known, then the proposed method to evaluate \bar{f} employs the approximation (1) \bar{f}\simeq Z^{-1}\,\langle\Sigma i:i\in S:(p(i)/(1-(1-p(i)/Z)^{N}))\cdot f(i)\rangle It is natural to require that this approximation is an identity when applied to the constant function f : [f=1] . That requirement leads to a nonlinear equation for Z : (2) Z=\phi(Z)\;,\quad\phi(Z)=\langle\Sigma i:i\in S:p(i)/(1-(1-p(i)/Z)^{N})\rangle In this section, we investigate properties of the iteration Z:=\phi(Z) . We will show that (away from boundary cases that will be identified) the iteration map is a contraction on the range P(S)\leq Z , with \phi increasing and convex. This implies that simple Picard

Read the complete text