Bounds on the expected maximum (or minimum) among a collection of sums.

It can be technically convenient to work with expectations directly, instead of working with probabilities. Here, given a collection of sums of 0/1 random variables, we bound the expected maximum (or minimum) sum in the collection.

For example, suppose Alice throws balls randomly into $n$ bins just until the first bin has $n$ balls. The bound says that the expected maximum number of balls in any bin will be at most $n+2\sqrt{n\ln n}+\ln n$ . Similarly, the expected minimum number of balls in any bin will be at least $n-2\sqrt{n\ln n}$ .

The bound differs from Chernoff in a few ways:

it bounds the expected maximum or minimum (as opposed to the probability of a large deviation),
the sums can have randomly many terms, so they don’t have to be concentrated around their means.

Click for background material…

Warm-up: sums with a fixed number of terms

For a warm up, here are bounds that are directly analogous to standard Chernoff bounds, in that they concern sums that have a fixed number of terms.

Lemma 1 (expected maximum or minimum of many sums).

For each $j\in [m]$ , let $X^j=\sum _{t=1}^T x^j_t$ be a sum of independent random variables, where each $x^j_t$ is in $[0,1]$ and $T\gt 0$ is fixed. Let $\varepsilon , \mu \gt 0$ .

(a) If $\textrm{E}[x^j_t] \le \mu$ for all $t\le T$ and all $j\in [m]$ , then

$\textstyle \textrm{E}\left[\max _{j\in [m]} X^j\right] ~ \lt ~ (1+\varepsilon )(\mu T + \varepsilon ^{-1}\ln m).$

Taking $\varepsilon = \sqrt{\ln (m)/\mu T}$ , the expected maximum is less than $\mu T + 2\sqrt{\mu T \ln m} + \ln m$ .

(b) If $\textrm{E}[x^j_t] \ge \mu$ for all $t\le T$ and all $j\in [m]$ , then

$\textstyle \textrm{E}\left[\min _{j\in [m]} X^j\right] ~ \gt ~ (1-\varepsilon )\mu T - \varepsilon ^{-1}\ln m.$

Taking $\varepsilon = \sqrt{\ln (m)/\mu T}$ , the expected minimum is more than $\mu T - 2\sqrt{\mu T\ln m}$ .

Proof of Lemma 1

Click for proof …

(a) The maximum $\max _{j\in [m]} X^j$ is at most $\log _{1+\varepsilon } \sum _{j=1}^m (1+\varepsilon )^{X^j}.$

By the concavity of the logarithm, the expectation of the log of the sum is at most the log of the expectation of the sum. Following the the proof of the Chernoff bound, the expectation of each term in the sum is at most $\exp (\varepsilon \mu T)$ . Hence (using $\ln (1+\varepsilon )\gt \varepsilon /(1+\varepsilon )$ ), the expectation of the maximum is at most

$\log _{1+\varepsilon } \left[ m \exp (\varepsilon \mu T) \right] ~ =~ \frac{1}{\ln 1+\varepsilon } \left[ \ln m ~ +~ \varepsilon \mu T\right] ~ \lt ~ (1+\varepsilon )(\varepsilon ^{-1} \ln m ~ +~ \mu T).$

(b) Assume $\varepsilon \lt 1$ (if not, (b) is trivial). The minimum $\min _{j\in [m]} X^j$ is at least $\log _{1-\varepsilon } \sum _{j=1}^m (1-\varepsilon )^{X^j}.$

By the convexity of the logarithm with negative base, the expectation of the log of the sum is at least the log of the expectation of the sum. Following the the proof of the Chernoff bound, the expectation of each term in the sum is at least $\exp (-\varepsilon \mu T)$ . Hence (using $\varepsilon \lt \ln (1/(1-\varepsilon ))\le \varepsilon /(1-\varepsilon )$ ), the expectation of the minimum is at least

$\log _{1-\varepsilon } \left[ m \exp (-\varepsilon \mu T) \right] ~ =~ \frac{1}{\ln 1/(1-\varepsilon )} \left[\varepsilon \mu T - \ln m\right] ~ \gt ~ (1-\varepsilon )\mu T - \varepsilon ^{-1} \ln m.$

Sums with a random number of terms

The next bound applies to a system that goes through a random sequence of states $S_1,S_2,S_3,\ldots ,S_T$ , where $T$ is a stopping time with finite expectation. At each time $t$ , the current state $S_t$ determines $m+1$ values: $x^j_t$ for $j\in [m]$ and $y_t$ , where each $x^j_t$ is in $[0,1]$ and $\textrm{E}[x^j_t] \le \textrm{E}[y_t]$ for $j\in [m]$ (or $\textrm{E}[x^j_t] \ge \textrm{E}[y_t]$ for $j\in [m]$ ). The bound shows that the expectation of $\max _j \sum _{t=1}^T x^j_t$ (or $\min _j \sum _{t=1}^T x^j_t$ ) is close to the expectation of $\sum _{t=1}^T y_t$ .

Lemma 2 (expected maximum or minimum of many sums).

Given the conditions above, let $\varepsilon \in [0,1]$ .

$\textstyle \textrm{E}\Big[\, {\max _{j\in [m]}}\, \sum _{t=1}^T x^j_t\, \Big] ~ \le ~ (1+\varepsilon ) \big(\textrm{E}\big[\sum _{t=1}^T y_t\big] \, +\, \varepsilon ^{-1}\ln m\big).$

(d) If $\textrm{E}[x^j_t - y_t\, |\, S_{t-1}]\ge 0$ for all $j\in [m]$ and all $t\le T$ , then

$\textstyle \textrm{E}\Big[\, {\min _{j\in [m]}}\, \sum _{t=1}^T x^j_t\, \Big] ~ \ge ~ (1-\varepsilon )\textrm{E}\big[\sum _{t=1}^T y_t\big] \, -\, \varepsilon ^{-1}\ln m. ~ ~$

The constants in the bounds are not optimized.

Proof of Lemma 2

Click for proof…

(c) Define $X^j_t = \sum _{i=1}^t x^j_i$ and $\phi _t ~ =~ \log _{1+\varepsilon } \sum _{j=1}^m \big(1+\varepsilon \big)^{X^j_t}$ .

Note that $\phi _T$ is an upper bound on the maximum sum: $\max _{j\in [m]} X^j_T ~ \le ~ \phi _T.$

Observe that $\phi$ increases by at most $(1+\varepsilon )\textrm{E}[y_t]$ in expectation in step $t$ . Indeed, letting $\omega _j = (1+\varepsilon )^{X^j_{t-1}}$ , using $x^j_t \in [0,1]$ and $\log _{1+\varepsilon }(1+\varepsilon z) \le (1+\varepsilon ) z$ ,

$\phi _{t} - \phi _{t-1} ~ =~ \log _{1+\varepsilon }\frac{\sum _j (1+\varepsilon )^{x^t_j}\omega _j}{\sum _j \omega _j} ~ \le ~ \log _{1+\varepsilon }\frac{\sum _j (1+\varepsilon x^t_j)\omega _j}{\sum _j \omega _j}$

$\begin{equation} \label{eq:3} ~ =~ \log _{1+\varepsilon } \Big( 1 + \varepsilon \frac{\sum _j x^j_t\omega _j}{\sum _j \omega _j}\Big) ~ \le ~ (1+\varepsilon )\frac{\sum _j x^j_t\omega _j}{\sum _j \omega _j}, \end{equation}$

and, given $S_{t-1}$ , the expectation of $x^j_t$ for each $j\in [m]$ is at most $\textrm{E}[y_t]$ , so by linearity of expectation, the expectation of $\phi _{t}-\phi _{t-1}$ given $S_{t-1}$ is at most $(1+\varepsilon )\textrm{E}[y_t]$ .

Hence $\phi _t - (1+\varepsilon )Y_t$ is a super-martingale, and by Wald’s equation, $\textrm{E}[\phi _T - (1+\varepsilon )Y_T] ~ \le ~ \phi _0$ , which, by calculation, proves part (c).

(d) Given the state $S_t$ after $t$ samples, define $\phi _t ~ =~ \log _{1-\varepsilon } \sum _{j=1}^n \big(1-\varepsilon \big)^{ X^j_t}.$ Then $\phi _T$ is a lower bound on the minimum sum, and $\phi$ increases by at least $(1-\varepsilon )\textrm{E}[y_t]$ in expectation in the $t$ th step. Indeed, letting $\omega _j = (1-\varepsilon )^{X^j_{t-1}}$ , using $x^j_t \in [0,1]$ and $\log _{1-\varepsilon }(1-\varepsilon z) \ge (1-\varepsilon ) z$ ,

$\phi _{t} - \phi _{t-1} ~ =~ \log _{1-\varepsilon }\frac{\sum _j (1-\varepsilon )^{x^t_j}\omega _j}{\sum _j \omega _j} ~ \ge ~ \log _{1-\varepsilon }\frac{\sum _j (1-\varepsilon x^t_j)\omega _j}{\sum _j \omega _j}$

$\begin{equation} \label{eq:4} ~ =~ \log _{1-\varepsilon } \Big( 1 - \varepsilon \frac{\sum _j x^j_t\omega _j}{\sum _j \omega _j}\Big) ~ \ge ~ (1-\varepsilon )\frac{\sum _j x^j_t\omega _j}{\sum _j \omega _j}, \end{equation}$

and, given $S_{t-1}$ , the expectation of $x^j_t$ for each $j\in [m]$ is at least $\textrm{E}[y_t]$ , so the expectation of $\phi _{t}-\phi _{t-1}$ given $S_{t-1}$ is at least $(1-\varepsilon )\textrm{E}[y_t]$ .

By Wald’s equation, $\textrm{E}[\phi _T - (1-\varepsilon )\sum _{t=1}^T y_t] ~ \ge ~ \phi _0$ , which, by calculation, proves part (d).

Some pessimistic estimators for the bound (c)

(Right now we’ve just recorded pessimistic estimators for (c). We’ll add the rest here as needed.)

The bound (c) relates $\max _{j\in [m]} \sum _{t=1}^T x_j^t$ and $\sum _{t=1}^T y_t$ . In a typical use of bound (c), we know a bound on one of the two quantities, and we use (c) to bound the expectation of the other. We start with pessimistic estimators for these two cases. Let $X^j_t = \sum _{i=1}^t x^j_i$ . Let $Y_t = \sum _{i=1}^t y_i$ .

Consider first the case that we start with an upper bound $Y_T \le U$ , and we use (c) to upper bound $\textrm{E}[\max _{j\in [m]} X^j_T]$ by $(1+\varepsilon )(U + \varepsilon ^{-1}\ln m)$ .

Given the outcomes of the first $t$ iterations (in particular, values of $Y_t$ and $X^j_t$ for all $j$ ) the following pessimistic estimator for the conditional expectation of $\textrm{E}[\max _{j\in [m]} X^j_T]$ is implicit in the proof of (c):

$\begin{equation} \label{pe:c:U}\textstyle \psi _t ~ =~ \phi _t + (1+\varepsilon )(U - Y_t) ~ =~ \log _{1+\varepsilon }\sum _{j=1}^m (1+\varepsilon )^{X_t} ~ ~ +~ (1+\varepsilon )(U - Y_t). \end{equation}$

The initial value $\psi _0$ is less than $(1+\varepsilon )(U + \varepsilon ^{-1}\ln m)$ , as desired. The final value $\psi _T$ is an upper bound on the maximum in question (given $Y_T\le U$ ). In a given iteration, letting $\omega _j = (1+\varepsilon )^{X^j_t}$ , the increase $\psi _t-\psi _{t-1}$ is at most

$\begin{equation} \label{pe:c:U:delta}\textstyle (1+\varepsilon ) \sum _j x^j_t \omega _j/\sum _j \omega _j ~ -~ (1+\varepsilon )y_t, \end{equation}$

which, in expectation is non-positive.
Consider next the case that we start with a lower bound $L \le \max _{j\in [m]} X^j_T$ on the maximum, and we use (c) to lower bound $\textrm{E}[Y_T]$ by $(1+\varepsilon )^{-1} L - \varepsilon ^{-1}\ln m$ .

Given the outcomes of the first $t$ iterations (in particular, values of $Y_t$ and $X^j_t$ for all $j$ ), the following pessimistic estimator for the conditional expectation of $\textrm{E}[Y_T]$ is implicit in the proof of (c):

$\begin{equation} \label{pe:c:L}\textstyle \psi _t ~ =~ Y_t + (1+\varepsilon )^{-1}(L - \log _{1+\varepsilon }\sum _{j=1}^m (1+\varepsilon )^{X_t}). \end{equation}$

The initial value $\psi _0$ is more than $(1+\varepsilon )^{-1}L - \varepsilon ^{-1}\ln m$ , as desired. The final value $\psi _T$ is a lower bound on $Y_T$ (given that the maximum is at least $L$ ). In a given iteration, letting $\omega _j = (1+\varepsilon )^{X^j_t}$ , the increase $\psi _t-\psi _{t-1}$ is at least

$\begin{equation} \label{pe:c:L:delta}\textstyle y_t - \sum _j x^j_t \omega _j/\sum _j \omega _j, \end{equation}$

which, in expectation is non-negative.
Or, it may be the case that we have no a-priori upper bound $U$ or lower bound $L$ . Rather, we simply want an outcome where the inequality in (c) holds: $\max _{j\in [m]} X^j_t \le (1+\varepsilon ) (Y_T + \varepsilon ^{-1} \ln m)$ . In that case, we can use the pessimistic estimator

$\begin{equation} \label{pe:c}\textstyle \psi _t ~ =~ \log _{1+\varepsilon } \sum _j (1+\varepsilon )^{X^j_t} ~ ~ -~ (1+\varepsilon ) (Y_t + \varepsilon ^{-1}\ln m). \end{equation}$

It is initially negative. If its final value is at most 0, then the desired inequality holds. In a given iteration, the increase $\psi _{t} - \psi _{t-1}$ is at most Expression \eqref{pe:c:U:delta}, which is non-positive in expectation.

Expected deviation of a single sum from a threshold

Notes on algorithms

Lecture notes on algorithms

Expected maximum (or minimum) of many sums

Warm-up: sums with a fixed number of terms

Proof of Lemma 1

Sums with a random number of terms

Proof of Lemma 2

Some pessimistic estimators for the bound (c)

Related