BRS-inequality
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 formula_1. For example, suppose 100 random variables formula_2 are all uniformly distributed on formula_3, not necessarily independent, and let formula_4, say. Let formula_5 be the maximum number of formula_6 one can select in formula_7 such that their sum does not exceed formula_4. formula_9 is a random variable, so what can one say about bounds for its expectation? How would an  upper bound for formula_10 behave, if one changes the size formula_11 of the sample and keeps formula_12 fixed, or alternatively, if one keeps formula_13 fixed but varies formula_12? What can one say about formula_10, if the uniform distribution is replaced by another continuous distribution? In all generality, what can one say if each formula_16 may have its own continuous distribution function formula_17? General problem. Let formula_18 be a sequence of non-negative random variables (possibly dependent) that are jointly continuously distributed. For formula_19 and formula_20 let formula_21 be the maximum number of observations among formula_22 that one can sum up  without exceeding formula_12. Now, to obtain formula_21 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 formula_12. Hence formula_26 can be defined in terms of the increasing order statistics of formula_27, denoted by formula_28, namely by What is the best possible "general" upper bound for formula_10 if one requires only the continuity of the joint distribution of all variables? And then, how to compute this bound? Identically distributed random variables.. Theorem 1 Let  formula_31 be identically distributed non-negative random variables with absolutely continuous distribution function formula_32. Then where formula_34 solves the so-called BRS-equation As an example, here are the answers for the questions posed at the beginning. Thus let all formula_27 be uniformly distributed on formula_3. Then formula_38 on formula_3, and hence formula_40 on formula_3. The BRS-equation becomes The solution is formula_43, and thus from the inequality (2) Since one always has formula_45, this bound becomes trivial for formula_46. For the example questions with formula_47 this yields formula_48. As one sees from (4), doubling the sample size formula_11 and  keeping formula_12 fixed, or vice versa, yield for the uniform distribution in the non-trivial case the same upper bound. Generalised BRS-inequality. Theorem 2. Let formula_27 be positive random variables that are jointly distributed such that formula_16 has an absolutely continuous distribution function formula_53. If formula_21 is defined as before, then where formula_56 is the unique solution of the BRS-equation Clearly, if all random variables formula_58 have the same marginal distribution formula_32, 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 . Depending on the type of the distributions formula_60, refinements of Theorem 2 can be of true interest. We just mention one of them. Let formula_61 be the random set of those variables one can sum up to yield the maximum random number formula_21, that is, and let formula_64 denote the sum of these variables. The so-called residual formula_65 is by definition always non-negative, and one has: Theorem 3. Let formula_27 be jointly continuously distributed with marginal distribution functions formula_67, and let formula_34 be the solution of (6). 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. For example, if all formula_16 are independent exponential random variables, then the memoryless property implies (if s is exceeded) the distributional symmetry of the residual and the overshoot over formula_12. For fixed formula_12 one can then show that :formula_74. This improvement fluctuates around formula_75, and the convergence to formula_75, (simulations) seems quick. Source. 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. 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 formula_21 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. 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.