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 are all uniformly distributed on , not necessarily independent, and let , say. Let be the maximum number of one can select in such that their sum does not exceed . is a random variable, so what can one say about bounds for its expectation? How would an upper bound for behave, if one changes the size of the sample and keeps fixed, or alternatively, if one keeps fixed but varies ? What can one say about , if the uniform distribution is replaced by another continuous distribution? In all generality, what can one say if each may have its own continuous distribution function ?

General problem

edit

Let   be a sequence of non-negative random variables (possibly dependent) that are jointly continuously distributed. For   and   let   be the maximum number of observations among   that one can sum up without exceeding  .

Now, to obtain   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  . Hence   can be defined in terms of the increasing order statistics of  , denoted by  , namely by

 

What is the best possible general upper bound for   if one requires only the continuity of the joint distribution of all variables? And then, how to compute this bound?

Identically distributed random variables.

edit

Theorem 1 Let   be identically distributed non-negative random variables with absolutely continuous distribution function  . Then

  (2)

where   solves the so-called BRS-equation

 . (3)

As an example, here are the answers for the questions posed at the beginning. Thus let all   be uniformly distributed on  . Then   on  , and hence   on  . The BRS-equation becomes

 

The solution is  , and thus from the inequality (2)

 . (4)

Since one always has  , this bound becomes trivial for  .

For the example questions with   this yields  . As one sees from (4), doubling the sample size   and keeping   fixed, or vice versa, yield for the uniform distribution in the non-trivial case the same upper bound.

Generalised BRS-inequality

edit

Theorem 2. Let   be positive random variables that are jointly distributed such that   has an absolutely continuous distribution function  . If   is defined as before, then

 , (5)

where   is the unique solution of the BRS-equation

  (6)

Clearly, if all random variables   have the same marginal distribution  , then (6) recaptures (3), and (5) recaptures (2). Again it should be pointed out that no independence hypothesis whatsoever is needed.

Refinements of the BRS-inequality

edit

Depending on the type of the distributions  , refinements of Theorem 2 can be of true interest. We just mention one of them.

Let   be the random set of those variables one can sum up to yield the maximum random number  , that is,

 ,

and let   denote the sum of these variables. The so-called residual   is by definition always non-negative, and one has:

Theorem 3. Let   be jointly continuously distributed with marginal distribution functions  , and let   be the solution of (6). Then

 . (7)

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. For example, if all   are independent exponential random variables, then the memoryless property implies (if s is exceeded) the distributional symmetry of the residual and the overshoot over  . For fixed   one can then show that : . This improvement fluctuates around  , and the convergence to  , (simulations) seems quick.

Source

edit

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).

Applications

edit

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. Also, and in particular, one notes that the maximum number   always dominates the maximum number of selections under any additional constraint, such as e.g. for online selections without recall. Examples studied in Steele (2016) and Bruss (2021) touch many applications, including comparisons between i.i.d. sequences and non-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.

References

edit

Bruss F. T. and Robertson J. B. (1991) ’Wald's Lemma’ for Sums of Order Statistics of i.i.d. Random Variables, Adv. Appl. Probab., Vol. 23, 612-623.

Bruss F. T. and Duerinckx M. (2015), Resource dependent branching processes and the envelope of societie, Ann. of Appl. Probab., Vol. 25 (1), 324-372.

Steele J.M. (2016), The Bruss-Robertson Inequality: Elaborations, Extensions, and Applications, Math. Applicanda, Vol. 44, No 1, 3-16.

Bruss F. T. (2021),The BRS-inequality and its applications, Probab. Surveys, Vol.18, 44-76.