Suppose we have a set of number {x1,x2,...,xn}\{x_1, x_2, ..., x_n \} and we would like to estimate its sum s=∑ixis = \sum_i x_i. However, we can only access the set {x1,x2,...,xn}\{x_1, x_2, ..., x_n \} by sampling an element xi,1≤i≤nx_i, 1 \le i \le n randomly. Let pip_i be the probability that we get xix_i. If pip_i is known (either before sampling or the moment we get a sampled element, depending on application), then we can still construct an unbiased estimator of ss: define

yi=xipi, y_i = \frac{x_i} {p_i},

and let YY be the random variable that takes value yiy_i with probability pip_i. The expectation and variance of YY is given by

E[Y]=∑ipiyi=∑ipixipi=∑ixi=s,Var[Y]=E[Y2]−E[Y]2=∑ipi⋅xi2pi2−s2=∑ixi2pi−s2. \begin{aligned} \mathbb{E}[Y] &= \sum_i p_i y_i = \sum_i p_i \frac{x_i} {p_i} = \sum_i x_i = s, \\ \mathbb{Var}[Y] &= \mathbb{E}[Y^2] - \mathbb{E}[Y]^2 \\ &= \sum_i p_i \cdot \frac{x_i^2}{p_i^2} - s^2 = \sum_i \frac{x_i^2}{p_i} - s^2. \end{aligned}

It can be seem that the variance of YY is minimized when pi=xisp_i = \frac{x_i} { s } for all ii. In such case, yi=xi/(xi/s)=sy_i = { x_i } / \big( x_i / s \big) = s is a constant and Var[Y]=0\mathbb{Var}[Y] = 0 (which is the smallest variance possible as its must be non-negative).

Remark: we can also verify this by formulating this as an optimization problem then using Lagrangian method.

In some applications, some elements in {x1,x2,...,xn}\{x_1, x_2, ..., x_n \} may have same value. Suppose there are mm different value in {x1,x2,...,xn}\{x_1, x_2, ..., x_n \} and define Xj(1≤j≤m)X_j ( 1 \le j \le m) the set of elements with the jj-th largest value. Denote the sum of probability of elements in XjX_j as Pr⁡j=∑x∈Xjpx\Pr_j = \sum_{x \in X_j} p_x. Also, let f(xi)f(x_i) denote the group that element xix_i belongs to, i.e., xi∈Xf(xi)x_i \in X_{ f( x_i ) }. Consider

yi′=xi∣Xf(xi)∣Pr⁡f(xi), y'_i = \frac{ x_i |X_{ f(x_i) }| } { \Pr_{ f(x_i) } },

and Y′Y' a random variable that takes value yi′y'_i with probability pip_i. The mean of Y′Y' is also an unbiased estimator of ss:

E[Y′]=∑i=1npiyi′=∑i=1npixi∣Xf(xi)∣Pr⁡f(xi)=∑j=1m∑x∈Xjpxx∣Xf(x)∣Pr⁡j=s. \begin{aligned} \mathbb{E}[Y'] &= \sum_{i = 1}^n p_i y'_i \\ &= \sum_{i = 1}^n p_i \frac{ x_i |X_{ f(x_i) }| } { \Pr_{ f(x_i) } } \\ &= \sum_{j = 1}^m \sum_{x \in X_j} p_x \frac{ x |X_{ f(x) }| } { \Pr_j } \\ &= s. \end{aligned}