BRS-inequality

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2022) (Learn how and when to remove this message)

BRS-inequality is the short name for Bruss-Robertson-Steele inequality. This inequality gives a convenient upper bound for the expected maximum number of non-negative random variables one can sum up without exceeding a given upper bound ${\displaystyle s>0}$.

For example, suppose 100 random variables ${\displaystyle X_{1},X_{2},...,X_{100}}$ are all uniformly distributed on ${\displaystyle [0,1]}$, not necessarily independent, and let ${\displaystyle s=10}$, say. Let ${\displaystyle N[n,s]:=N[100,10]}$ be the maximum number of ${\displaystyle X_{j}}$ one can select in ${\displaystyle \{X_{1},X_{2},...,X_{100}\}}$ such that their sum does not exceed ${\displaystyle s=10}$. ${\displaystyle N[100,10]}$ is a random variable, so what can one say about bounds for its expectation? How would an upper bound for ${\displaystyle E(N[n,s])}$ behave, if one changes the size ${\displaystyle n}$ of the sample and keeps ${\displaystyle s}$ fixed, or alternatively, if one keeps ${\displaystyle n}$ fixed but varies ${\displaystyle s}$? What can one say about ${\displaystyle E(N[n,s])}$, if the uniform distribution is replaced by another continuous distribution? In all generality, what can one say if each ${\displaystyle X_{k}}$ may have its own continuous distribution function ${\displaystyle F_{k}}$?