Weighted Hoeffding Bounds for Unequal Ranges

Why Weights and Individual Ranges Matter

A sum of independent bounded variables can concentrate around its expectation even when its terms have different scales. In a weighted sum, each variable’s contribution to the deviation depends both on its original range and on its weight. Treating all terms as if they had the same range can produce an unnecessarily weak bound—or, if the weights are omitted, an invalid one.

The central calculation is to find the range width of each weighted term. Once those widths are known, Hoeffding’s inequality applies without requiring the variables to have the same distribution, the same range, or the same weight.

Weighted Sums and Effective Range Widths

Let $X_1,\ldots,X_n$ be independent random variables with finite expectations. Suppose that for each $i$, there are finite constants $a_i\le b_i$ such that $P(a_i\le X_i\le b_i)=1$. Let $w_1,\ldots,w_n$ be fixed, nonrandom real numbers, and define the weighted sum $S=\sum_{i=1}^n w_iX_i$.

Definition: The effective range width of the $i$th weighted term is $d_i=|w_i|(b_i-a_i)$. The total squared effective range is $D=\sum_{i=1}^n d_i^2=\sum_{i=1}^n w_i^2(b_i-a_i)^2$. The expectation of the sum is $E[S]=\sum_{i=1}^n w_iE[X_i]$.

If $w_i\ge 0$, then $w_iX_i$ lies between $w_ia_i$ and $w_ib_i$. If $w_i<0$, multiplication reverses the endpoints: $w_iX_i$ lies between $w_ib_i$ and $w_ia_i$. In either case, the width of the interval is $|w_i|(b_i-a_i)=d_i$. Independence is preserved by applying a fixed weight to each variable, so the weighted terms can be handled directly.

A fact established with Hoeffding’s lemma for bounded variables is that if $Z$ lies almost surely in an interval of width $d$, then, for every real $\lambda$,

E\!\left[\exp\{\lambda(Z-E[Z])\}\right]\le \exp\left(\frac{\lambda^2d^2}{8}\right).

This bound holds for positive and negative $\lambda$. Applying it to each weighted term is the key step in the weighted inequality.

The Weighted Moment-Generating-Function Bound

Theorem: Under the independence and boundedness conditions above, for every real $\lambda$, $$ E\!\left[\exp\{\lambda(S-E[S])\}\right]\le \exp\left(\frac{\lambda^2D}{8}\right). $$

Proof. Write $S-E[S]=\sum_{i=1}^n(w_iX_i-E[w_iX_i])$. Independence implies that the expectation of the product of the exponentials factors into a product of expectations. Each $w_iX_i$ has range width $d_i$, so Hoeffding’s lemma gives

\begin{aligned} E\!\left[\exp\{\lambda(S-E[S])\}\right] &=\prod_{i=1}^n E\!\left[\exp\{\lambda(w_iX_i-E[w_iX_i])\}\right]\\ &\le \prod_{i=1}^n \exp\left(\frac{\lambda^2d_i^2}{8}\right)\\ &=\exp\left(\frac{\lambda^2}{8}\sum_{i=1}^n d_i^2\right) =\exp\left(\frac{\lambda^2D}{8}\right). \end{aligned}

The factorization is valid because the $X_i$ are independent and each exponential is a measurable function of its corresponding variable. This proves the bound. $\square$

One-Sided and Two-Sided Deviation Bounds

Theorem: If $D>0$, then for every $t>0$, $$ P(S-E[S]\ge t)\le \exp\left(-\frac{2t^2}{D}\right), \qquad P(|S-E[S]|\ge t)\le 2\exp\left(-\frac{2t^2}{D}\right). $$

Proof. For any $\lambda>0$, on the event $S-E[S]\ge t$ we have $\exp\{\lambda(S-E[S])\}\ge \exp(\lambda t)$. Markov’s inequality and the moment-generating-function bound therefore imply

P(S-E[S]\ge t) \le \exp(-\lambda t)\,E[\exp\{\lambda(S-E[S])\}] \le \exp\left(-\lambda t+\frac{\lambda^2D}{8}\right).

The exponent is minimized over $\lambda>0$ at $\lambda=4t/D$. Substituting this value gives $-4t^2/D+2t^2/D=-2t^2/D$, which proves the upper-tail bound. Apply the same argument to $-S$ to obtain $P(E[S]-S\ge t)\le \exp(-2t^2/D)$. The event $|S-E[S]|\ge t$ is the union of these two tail events, so the union bound gives the stated two-sided result. $\square$

If $D=0$, every $d_i=0$, so each weighted term $w_iX_i$ is constant almost surely. Thus $S=E[S]$ almost surely, and every deviation event with $t>0$ has probability zero. This handles the zero-width case separately, without dividing by $D$.

Worked Example: Weighted Bernoulli Variables

Let $X_1,X_2,X_3$ be independent Bernoulli variables with success probabilities $0.4$, $0.7$, and $0.2$, respectively. Set $S=2X_1-X_2+0.5X_3$. Find a Hoeffding upper bound for $P(S-E[S]\ge 1.5)$.

Each Bernoulli variable lies in $[0,1]$, so the three effective widths are $2(1-0)=2$, $|-1|(1-0)=1$, and $0.5(1-0)=0.5$. Therefore $D=2^2+1^2+0.5^2=5.25=21/4$.

The expectation is $E[S]=2(0.4)-0.7+0.5(0.2)=0.8-0.7+0.1=0.2$. The requested event is $S\ge 0.2+1.5=1.7$. Since $t=1.5$, the one-sided bound is

P(S-E[S]\ge 1.5) \le \exp\left(-\frac{2(1.5)^2}{21/4}\right) =\exp\left(-\frac{18}{21}\right) =\exp(-6/7) \approx 0.424.

The negative weight causes no special difficulty: its contribution to $D$ is the square of its effective width, $1^2$.

Worked Example: Combining Different Ranges and Weights

Suppose independent variables satisfy $X_1\sim\operatorname{Uniform}[0,2]$, $X_2\sim\operatorname{Uniform}[1,4]$, and $X_3\sim\operatorname{Uniform}[-1,1]$. Consider $S=X_1+0.5X_2+0.5X_3$. Bound the probability that $S$ exceeds its expectation by at least $2$.

The interval widths of $X_1,X_2,X_3$ are $2,3,2$. After weighting, the effective widths are $2$, $0.5(3)=1.5$, and $0.5(2)=1$. Hence $D=2^2+1.5^2+1^2=4+2.25+1=7.25=29/4$.

The uniform means are $1$, $2.5$, and $0$. Thus $E[S]=1+0.5(2.5)+0.5(0)=2.25$, and the event in question is $S\ge4.25$. The upper-tail inequality gives

P(S-E[S]\ge 2) \le \exp\left(-\frac{2(2)^2}{29/4}\right) =\exp\left(-\frac{32}{29}\right) \approx 0.332.

The range widths are not interchangeable: the second variable has width $3$, but its weight reduces its effective width to $1.5$.

Worked Example: Choosing a Two-Sided Deviation Threshold

Let $X_1,\ldots,X_9$ be independent, with $X_i\sim\operatorname{Uniform}[0,i]$, and define $S=\sum_{i=1}^9 X_i/i$. Find a threshold $t$ for which the two-sided Hoeffding bound guarantees $P(|S-E[S]|\ge t)\le0.05$.

The range of $X_i$ is $i$, and its weight is $1/i$, so every effective width is $(1/i)i=1$. Therefore $D=9$. To make the two-sided bound at most $0.05$, solve $2\exp(-2t^2/9)=0.05$. Dividing by $2$ and taking logarithms gives $-2t^2/9=\log(0.025)=-\log(40)$, so

t=\sqrt{\frac{9}{2}\log(40)}\approx 4.074.

Consequently, $P(|S-E[S]|\ge4.074)\le0.05$. As a check on the scale, each $X_i/i$ has expectation $1/2$, so $E[S]=9/2=4.5$; the stated bound concerns deviations around that expectation, not around zero.

Interpreting the Bound Correctly

The bound is driven by $D=\sum_i w_i^2(b_i-a_i)^2$. A weight twice as large doubles that term’s range width but multiplies its contribution to $D$ by four. A variable with a wide range can still have a small effect if its weight is small. The squares also mean that a negative weight contributes just as much to the deviation scale as a positive weight of the same magnitude.

For a desired one-sided error probability $\alpha\in(0,1)$, solving $\exp(-2t^2/D)=\alpha$ gives the sufficient threshold $t=\sqrt{(D/2)\log(1/\alpha)}$. For a two-sided error probability at most $\alpha$, the corresponding sufficient threshold is $t=\sqrt{(D/2)\log(2/\alpha)}$. These are guarantees, not generally exact quantiles; the actual tail can be smaller.

Common Mistake

A frequent error is to use $\sum_i(b_i-a_i)^2$ for a weighted sum, forgetting the weights. For example, if a variable in $[0,1]$ is multiplied by $5$, the resulting term has range width $5$, not $1$, and contributes $25$ to $D$. The correction is to find the range of each entire term $w_iX_i$ first, then square that width. Another mistake is to add the widths and square the total; Hoeffding’s bound for independent summands uses the sum of squared individual widths, $\sum_i d_i^2$.

The method needs independence and almost-sure finite bounds for each variable. It does not require identical distributions or identical ranges. If the variables are not independent, the factorization in the moment-generating-function proof does not follow from these assumptions, so this bound cannot be applied by the same argument.

Check Your Understanding

Use the effective range widths to answer the following questions.

If $X_i$ lies in $[a_i,b_i]$ and is multiplied by a negative weight $w_i$, what is the width of the resulting interval?
For independent $X_1,X_2$ in $[0,1]$, let $S=3X_1-2X_2$. Calculate $D$.
Why does the upper-tail proof choose $\lambda=4t/D$, rather than an arbitrary positive value?
State the two-sided Hoeffding bound in terms of $D$ and a deviation $t>0$.
What changes in the argument if $D=0$?