The Smallest Weight Punches Above Its Weight (in Expectation)

02 Apr, 2025

Screenshot 2025-03-24 at 19

I saw this nice bound on Twitter; it's proved as part of this work.

Assuming:

$X_{1}, X_{2}, \dots, X_{n} \geq 0$ are IID (independent and identically distributed) non-negative random variables and
$w_{1} \geq w_{2} \geq \dots \geq w_{n} \geq 0$ are non-negative weights,

we want to show that for the smallest of the $w$ 's, we have:

𝔼 [\frac{w_{n} X_{n}}{\sum_{i = 1}^{n} w_{i} X_{i}}] \geq \frac{w_{n}}{\sum_{i = 1}^{n} w_{i}} .

It is necessary that at least one of $w_{i} \neq 0$ and if $w_{n} = 0$ then there's nothing to prove, so let's assume that $w_{n} > 0$ (this also means that all $w_{i} \neq 0$ ). It is also necessary that not all of $X_{i}$ are 0 at the same time (an unlikely event as they are independent).

We can rewrite the bound as follows. First set $r_{j} : = w_{j} / \sum_{i} w_{i}$ , $0 < r_{i} \leq 1$ . Then, we want to prove:

𝔼 [\frac{X_{n}}{\sum_{i = 1}^{n} r_{i} X_{i}}] \geq 1 .

A simpler result

There's a similar result that is a bit easier to show. First, set $r_{i} = 1 / n$ , then we can argue that the distribution of $X_{i} / \sum_{j = 1}^{n} r_{j} X_{j}$ does not depend on $i$ (this is called "symmetrization"), so they should all have the same expected value, let's say $μ$ . From this, we have that $𝔼 [\sum_{k = 1}^{n} \frac{X_{k}}{\sum_{i = 1}^{n} X_{i} / n}] = n μ$ and so

𝔼 [\frac{X_{n}}{\sum_{i = 1}^{n} X_{i} / n}] = 1 .

A search for a proof

We can't use symmetrization immediately with the weighted version, the $r_{i} X_{i}$ variables are not identically distributed anymore.

Here's an idea, though. Let us first define the shorthand $S : = \sum_{k = 1}^{n} r_{i} X_{i}$ and $E_{i} : = E [X_{i} / S]$ . Then, from linearity of expectation, we have:

\sum_{i = 1}^{n} r_{i} E_{i} = 𝔼 [S / S] = 1 .

As a side effect, $1 = \sum_{i = 1}^{n} r_{i} E_{i} \leq {max}_{k} E_{k} \sum_{i} r_{i} \leq {max}_{k} E_{k}$ , so if we show ${max}_{k} E_{k} = E_{n}$ , then we are done!

Instead of going for a clever two-step-Jensen proof (like the authors of the paper), I'll attempt to show this with calculus. 🤔 This assumes more stuff, but it's fine, this isn't math class.

Proof

For $i : = j + 1, j$ , $0 < r_{i} \leq r_{j}$ (from the ordering of the $w_{i}$ ) and we want to show that $E_{i} \geq E_{j} .$ Let’s be adventurous and take a derivative with respect to $r_{j}$ while holding $r_{k}$ for $k \neq i, j$ constant. Then because of $\sum_{k} r_{k} = 1$ , we get that $d r_{j} = - d r_{i}$ and

\frac{d}{d r_{j}} (E_{i} - E_{j}) = 𝔼 [(X_{i} - X_{j})^{2} / S^{2}] \geq 0,

so the difference $E_{i} - E_{j}$ is increasing as $r_{j}$ is increasing (and $r_{i}$ is decreasing, to compensate)¹. We just need to find the minimum of $E_{i} - E_{j}$ . We can bound this minimum from below by setting $r_{i}$ and $r_{j}$ to be equal to the middle point $r^{'} = (r_{i} + r_{j}) / 2$ (as we are decreasing $r_{j}$ , this also decreases the difference $E_{i} - E_{j}$ )².

But now $X_{i}$ and $X_{j}$ have the same weight $r ’$ , so by symmetrization the lower bound is 0, i.e.,

E_{i} - E_{j} \geq 𝔼 [\frac{X_{i} - X_{j}}{\sum_{k \neq i, j} r_{k} X_{k} + r^{'} (X_{i} + X_{j})}] = 0

So, we have shown that $E_{i}$ are increasing with $i$ , so $E_{n}$ is the maximum, which implies $E_{n} \geq 1$ , and we are done! $∎$

To justify swapping derivative and expectation, we bound the term $f = (X_{i} - X_{j})^{2} / S^{2}$ . It can be shown that $S^{2} = (\sum r_{k} X_{k})^{2} \geq (r_{i} (X_{i} - X_{j}))^{2}$ , relying on $r_{k}, X_{k} \geq 0$ and the condition $r_{j} \geq r_{i}$ (for $i = j + 1$ ). This inequality implies $f \leq \frac{(X_{i} - X_{j})^{2}}{(r_{i} (X_{i} - X_{j}))^{2}} = \frac{1}{r_{i}^{2}}$ . Since $r_{i} \geq r_{n} > 0$ , $f$ is bounded by the finite constant $1 / r_{n}^{2}$ , allowing the interchange.↩
Remember that $r_{i} \leq r_{j}$ according to the original assumptions, so setting the two equal is the smallest allowed value for $r_{j}$ .↩