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
For example, suppose 100 random variables
is a random variable, so what can one say about bounds for its expectation?
be a sequence of non-negative random variables (possibly dependent) that are jointly continuously distributed.
one may think of looking at the list of all observations, first select the smallest one, then add the second smallest, then the third and so on, as long as the accumulated sum does not exceed
can be defined in terms of the increasing order statistics of
, namely by What is the best possible general upper bound for
if one requires only the continuity of the joint distribution of all variables?
solves the so-called BRS-equation As an example, here are the answers for the questions posed at the beginning.
As one sees from (4), doubling the sample size
fixed, or vice versa, yield for the uniform distribution in the non-trivial case the same upper bound.
be positive random variables that are jointly distributed such that
has an absolutely continuous distribution function
is the unique solution of the BRS-equation Clearly, if all random variables
Again it should be pointed out that no independence hypothesis whatsoever is needed.
, refinements of Theorem 2 can be of true interest.
Then The improvement in (7) compared with (5) therefore consists of The expected residual in the numerator is typically difficult to compute or estimate, but there exist nice exceptions.
are independent exponential random variables, then the memoryless property implies (if s is exceeded) the distributional symmetry of the residual and the overshoot over
The first version of the BRS-inequality (Theorem 1) was proved in Lemma 4.1 of F. Thomas Bruss and James B. Robertson (1991).
This paper proves moreover that the upper bound is asymptotically tight if the random variables are independent of each other.
The generalisation to arbitrary continuous distributions (Theorem 2) is due to J. Michael Steele (2016).
Theorem 3 and other refinements of the BRS-inequality are more recent and proved in Bruss (2021).
The BRS-inequality is a versatile tool since it applies to many types of problems, and since the computation of the BRS-equation is often not very involved.
Examples studied in Steele (2016) and Bruss (2021) touch many applications, including comparisons between i.i.d.
sequences, problems of condensing point processes, “awkward” processes, selection algorithms, knapsack problems, Borel-Cantelli-type problems, the Bruss-Duerinckx theorem, and online Tiling strategies.
(1991) ’Wald's Lemma’ for Sums of Order Statistics of i.i.d.
Bruss F. T. and Duerinckx M. (2015), Resource dependent branching processes and the envelope of societie, Ann.
(2016), The Bruss-Robertson Inequality: Elaborations, Extensions, and Applications, Math.
Bruss F. T. (2021),The BRS-inequality and its applications, Probab.