Weighted Hoeffding Bounds for Unequal Observation Weights

Why Unequal Weights Change Concentration

A weighted average can give observations very different influence. For example, an average that assigns half its total weight to one observation cannot generally concentrate as if it used many equally influential observations. The relevant quantity is not just the number of terms: it is the sum of the squared weights. This tutorial derives the corresponding Hoeffding bounds and shows how to express their scale as an effective sample size.

We assume throughout that the observations are independent and that the weights are fixed before the observations are realized. The observations need not have the same distribution or the same mean. For a common bounded range, the result has a particularly useful interpretation in terms of effective sample size.

Definition: Let $X_1,\ldots,X_n$ be independent random variables with $P(a_i\leq X_i\leq b_i)=1$, where $a_i,b_i$ are finite constants. Let $w_i\geq 0$ be fixed weights, not all zero, and let $W=\sum_{i=1}^n w_i>0$. The weighted average is $$ \bar X_w=\frac{\sum_{i=1}^n w_iX_i}{W}, $$ and its expectation is $E[\bar X_w]=\sum_i w_iE[X_i]/W$. Write $R_i=b_i-a_i$ for the range width of $X_i$.

Weights can be multiplied by the same positive constant without changing the weighted average. Thus, one may equivalently use normalized weights $\alpha_i=w_i/W$, for which $\sum_i\alpha_i=1$. With this notation, the squared-weight quantity in the bound is $\sum_i\alpha_i^2$, not $\sum_i\alpha_i$: the latter is always one and does not capture how concentrated the weights are.

Deriving the Weighted Bound

The proof uses a moment-generating-function bound for a bounded random variable. We give the argument explicitly so that the role of each weight and range is visible.

Lemma (Hoeffding's lemma): If $Y$ is a random variable satisfying $P(a\leq Y\leq b)=1$, then for every real $\lambda$, $$ E\!\left[\exp\{\lambda(Y-E[Y])\}\right] \leq \exp\!\left(\frac{\lambda^2(b-a)^2}{8}\right). $$

To prove the lemma, first suppose $a<b$, set $U=(Y-a)/(b-a)$, and write $p=E[U]$. Then $0\leq U\leq1$ and $0\leq p\leq1$. Convexity of the exponential function gives $e^{tu}\leq (1-u)+ue^t$ for $0\leq u\leq1$ and every real $t$. Taking expectations and centering, $$ E[e^{t(U-p)}]\leq e^{-tp}(1-p+pe^t). $$ For $0<p<1$, define $g(t)=\log(1-p+pe^t)-pt$. Direct differentiation gives $g(0)=g'(0)=0$ and $$ g''(t)=q(t)(1-q(t))\leq \frac14,\qquad q(t)=\frac{pe^t}{1-p+pe^t}. $$ The same bound holds when $p=0$ or $p=1$, since then $U=p$ almost surely and the centered moment-generating function equals one. For any real $t$, integrating the second derivative from zero (or using Taylor's formula with integral remainder) yields $g(t)\leq t^2/8$. Therefore $E[e^{t(U-p)}]\leq e^{t^2/8}$. Substituting $t=\lambda(b-a)$ proves the claim. If $a=b$, then $Y$ is constant and the inequality holds with equality. $\square$

Theorem (weighted Hoeffding bound): Under the definition above, put $D=\sum_{i=1}^n w_i^2R_i^2$. If $D>0$, then for every $t>0$, $$ P\!\left(\bar X_w-E[\bar X_w]\geq t\right) \leq \exp\!\left(-\frac{2W^2t^2}{D}\right). $$ The same bound holds for $P(E[\bar X_w]-\bar X_w\geq t)$. Consequently, $$ P\!\left(\left|\bar X_w-E[\bar X_w]\right|\geq t\right) \leq 2\exp\!\left(-\frac{2W^2t^2}{D}\right). $$ If $D=0$, every term with positive weight is constant almost surely, so $\bar X_w=E[\bar X_w]$ almost surely.

Here is the full argument for the upper tail. Let $S=\sum_i w_i(X_i-E[X_i])$, so $\bar X_w-E[\bar X_w]=S/W$. Independence and Hoeffding's lemma, applied to $w_iX_i$, whose range width is $w_iR_i$, give for every $\lambda>0$ $$ E[e^{\lambda S}] =\prod_{i=1}^n E[e^{\lambda w_i(X_i-E[X_i])}] \leq \exp\!\left(\frac{\lambda^2D}{8}\right). $$ By Markov's inequality, $P(S\geq Wt)\leq e^{-\lambda Wt}E[e^{\lambda S}]$. Hence $$ P(S\geq Wt)\leq \exp\!\left(-\lambda Wt+\frac{\lambda^2D}{8}\right). $$ The right side is minimized at $\lambda=4Wt/D$, which is positive because $t,W,D>0$. Substitution gives $\exp(-2W^2t^2/D)$. Applying the same reasoning to $-S$ proves the lower-tail bound, and adding the two tail probabilities proves the two-sided bound. $\square$

If all observations lie in a common interval of width $R$, then $D=R^2\sum_iw_i^2$. Define the effective sample size by $$ n_{\mathrm{eff}}=\frac{W^2}{\sum_{i=1}^n w_i^2}. $$ The two-sided result becomes $$ P\!\left(\left|\bar X_w-E[\bar X_w]\right|\geq t\right) \leq 2\exp\!\left(-\frac{2n_{\mathrm{eff}}t^2}{R^2}\right). $$ For any $0<\delta<1$, choosing the right-hand side to equal $\delta$ gives the confidence statement $$ P\!\left(\left|\bar X_w-E[\bar X_w]\right| \leq R\sqrt{\frac{\log(2/\delta)}{2n_{\mathrm{eff}}}}\right)\geq 1-\delta. $$ This is a probability guarantee for deviation from the weighted expectation; it does not assert that this expectation equals any unweighted population target.

Worked Applications

Worked Example: Three Unequally Weighted Bounded Observations

Suppose $X_1,X_2,X_3$ are independent, each taking values in $[0,1]$, with expectations $0.2,0.5,0.8$, respectively. Use weights $1,2,3$. Bound the probability that the weighted average exceeds its expectation by at least $0.25$.

The total weight is $W=1+2+3=6$. The weighted expectation is $$ E[\bar X_w]=\frac{1(0.2)+2(0.5)+3(0.8)}{6} =\frac{0.2+1.0+2.4}{6} =\frac{3.6}{6}=0.6. $$ Each range width is one, so $D=1^2+2^2+3^2=14$. The one-sided bound at $t=0.25$ is $$ P(\bar X_w-0.6\geq0.25) \leq \exp\!\left(-\frac{2(6)^2(0.25)^2}{14}\right) =\exp\!\left(-\frac{4.5}{14}\right) =\exp(-0.32143) \approx 0.725. $$ Thus the theorem guarantees a probability no larger than approximately $0.725$. This bound is valid but not especially tight; a concentration inequality need not give a small numerical bound for every deviation and weight pattern.

Worked Example: Observations With Different Range Widths

Let $X_1,X_2,X_3$ be independent, with respective ranges $[0,1]$, $[0,2]$, and $[0,0.5]$, and respective expectations $0.5,0.5,0.2$. Give a one-sided bound for the weighted average with weights $1,1,2$ exceeding its expectation by at least $0.3$.

The total weight is $W=1+1+2=4$, and $$ E[\bar X_w]=\frac{1(0.5)+1(0.5)+2(0.2)}{4} =\frac{1.4}{4}=0.35. $$ The weighted range widths are $1(1)=1$, $1(2)=2$, and $2(0.5)=1$. Therefore $D=1^2+2^2+1^2=6$. The bound is $$ P(\bar X_w-0.35\geq0.3) \leq \exp\!\left(-\frac{2(4)^2(0.3)^2}{6}\right) =\exp\!\left(-\frac{2.88}{6}\right) =\exp(-0.48) \approx 0.619. $$ Using a common range width for all three observations would discard the information that their ranges differ. The general denominator $D=\sum_iw_i^2R_i^2$ accounts for each range separately.

Worked Example: Effective Sample Size and a Confidence Radius

Suppose four independent observations lie in $[0,1]$ and have normalized weights $0.4,0.3,0.2,0.1$. Find the two-sided Hoeffding radius for confidence level $0.90$, meaning a failure probability $\delta=0.10$.

The weights sum to one, and their squared sum is $$ 0.4^2+0.3^2+0.2^2+0.1^2 =0.16+0.09+0.04+0.01=0.30. $$ Thus $n_{\mathrm{eff}}=1/0.30=10/3$, which is below the actual count of four observations. With $R=1$, the radius is $$ \sqrt{\frac{\log(2/0.10)}{2(10/3)}} =\sqrt{\frac{\log(20)}{20/3}} =\sqrt{\frac{3\log(20)}{20}} =\sqrt{0.44936} \approx 0.670. $$ Here $\log(20)\approx2.995732$, so $3\log(20)/20\approx0.44936$. The theorem states that the weighted average lies within approximately $0.670$ of its expectation with probability at least $0.90$. The radius is large because the effective sample size is only $10/3$ and the requested confidence level is high relative to this small sample.

Interpreting the Effective Sample Size

For normalized nonnegative weights $\alpha_i$, the effective sample size is $1/\sum_i\alpha_i^2$. Equal weights $\alpha_i=1/n$ give $\sum_i\alpha_i^2=n(1/n)^2=1/n$, hence $n_{\mathrm{eff}}=n$. Unequal weights increase the sum of squares and reduce the effective sample size. More precisely, Cauchy–Schwarz gives $$ \left(\sum_{i=1}^n\alpha_i\right)^2 \leq n\sum_{i=1}^n\alpha_i^2, $$ so $n_{\mathrm{eff}}\leq n$. Also, because $\alpha_i\geq0$ and $\sum_i\alpha_i=1$, we have $\sum_i\alpha_i^2\leq1$, so $n_{\mathrm{eff}}\geq1$.

The upper end occurs when the weights are equal. At the lower end, if one observation has weight one and all others have weight zero, then $n_{\mathrm{eff}}=1$: the weighted average is just that single observation. This explains why the effective sample size is useful as a concentration summary, while also reminding us that it is not a literal count of independent observations.

Common Mistake

A frequent error is to replace the squared weights by their sum and conclude that normalized weights always provide the same concentration, since $\sum_i\alpha_i=1$. That reasoning ignores how the total weight is distributed. The bound depends on $\sum_i\alpha_i^2$: four equal weights give a squared sum of $1/4$, whereas weights $(0.7,0.1,0.1,0.1)$ give a squared sum of $0.52$. Their effective sample sizes are $4$ and $1/0.52\approx1.92$, respectively. The correction is to retain the squared weights in the denominator of the exponent, or equivalently to use the corresponding $n_{\mathrm{eff}}$.

A second caution is that the common-range effective-sample-size formula does not directly apply when the ranges differ. In that case use $D=\sum_iw_i^2R_i^2$ in the general bound. A large weight and a wide range both increase this denominator and therefore weaken the guarantee.

Key takeaway: For independent observations bounded in a common interval of width $R$, a weighted average concentrates at a Hoeffding rate governed by $n_{\mathrm{eff}}=W^2/\sum_iw_i^2$. With different ranges, the controlling quantity is $\sum_iw_i^2R_i^2$. Both forms make explicit how unequal influence affects the confidence radius.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

For normalized weights $0.5,0.25,0.25$, calculate the effective sample size. Is it greater or less than the number of observations?
State the weighted Hoeffding upper-tail bound when the observations have different range widths.
Why does a single normalized weight equal to one give an effective sample size of one?
If all weights are multiplied by the same positive constant, which quantities change and which remain unchanged in the weighted average and its concentration bound?
For a two-sided confidence level $1-\delta$, write the weighted Hoeffding confidence radius when all observations lie in an interval of width $R$.