BRS-inequality
BRS-inequality is the short name for Bruss-Robertson-Steele inequality.
≈ 6 min read
BRS-inequality. encyclopegia.org, snapshot enwiki-001312480525. /a/brs-inequality
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 s > 0 .
For example, suppose 100 random variables X_1, X_2,..., X_{100} are all uniformly distributed on [0, 1] , not necessarily independent, and let s= 10 , say. Let N[n, s] := N[100, 10] be the maximum number of X_j one can select in \{X_1, X_2,..., X_{100}\} such that their sum does not exceed s= 10 . N[100, 10] is a random variable, so what can one say about bounds for its expectation?
How would an upper bound for E(N[n, s]) behave, if one changes the size n of the sample and keeps s fixed, or alternatively, if one keeps n fixed but varies s ? What can one say about E(N[n, s]) , if the uniform distribution is replaced by another continuous distribution? In all generality, what can one say if each X_k may have its own continuous distribution function F_k ?
General problem
Let X_1, X_2,... be a sequence of non-negative random variables (possibly dependent) that are jointly continuously distributed. For n \in \{1, 2,... \} and s\in \mathbb{R}^+ let N[n, s] be the maximum number of observations among X_1, X_2, ..., X_n that one can sum up without exceeding s . Now, to obtain N[n, s] 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 s . Hence N[s, n] can be defined in terms of the increasing order statistics of X_1, X_2,\cdots, X_n , denoted by X_{1,n} \le X_{2,n} \le \cdots \le X_{n,n}, , namely by \begin{align} N[n, s] = \begin{cases} 0 &, {\rm ~if~}~ X_{1,n} > s,\\ \max\{~k \in \N :~ X_{1,n} + X_{2,n}+ \cdots + X_{k,n} \le s\} &, {\rm~ otherwise}. \end{cases} \end{align} (1) What is the best possible general upper bound for E(N[n, s]) if one requires only the continuity of the joint distribution of all variables?
And then, how to compute this bound? where t := t(n, s) solves the so-called BRS-equation n \int_0^t x \,dF(x)\, =\, s . (3) As an example, here are the answers for the questions posed at the beginning. Thus let all X_1, X_2,\cdots, X_n be uniformly distributed on [0, 1] . Then F(t) = t on [0, 1] , and hence dF(x)/dx = 1 on [0, 1] .
The BRS-equation becomes n \int_0^t x dx = n t^2/2 = s. The solution is t =\sqrt{2s/n} , and thus from the inequality (2) E(N[n, s]) \le n\,F(t) = n \sqrt{2s/n }= \sqrt{2sn} . (4) Since one always has N[n, s] \le n , this bound becomes trivial for s \ge nE(X) = n/2 . For the example questions with n=100, s=10 this yields E(N[100, 10]) \le \sqrt{2000} \approx 44.7 .
As one sees from (4), doubling the sample size n and keeping s fixed, or vice versa, yield for the uniform distribution in the non-trivial case the same upper bound. Theorem 2.
Let X_1, X_2,\cdots, X_n be positive random variables that are jointly distributed such that X_k has an absolutely continuous distribution function F_k, ~k=1, 2, \cdots,n. . If N[n, s] is defined as before, then E (N[n, s])\le \sum_{k=1}^n F_k(t) , (5) where t := t(n, s) is the unique solution of the BRS-equation \sum_{k=1}^n \int_0^t \,x\,dF_k(x) = s. (6) Clearly, if all random variables X_i, i=1, 2, \cdots, n have the same marginal distribution F , then (6) recaptures (3), and (5) recaptures (2). Again it should be pointed out that no independence hypothesis whatsoever is needed. \#A[n, s] = N[n, s] , and let S_{A[n,s]} denote the sum of these variables.
The so-called residual s-S_{A[n,s]} is by definition always non-negative, and one has: Theorem 3. Let X_1, X_2,\cdots, X_n be jointly continuously distributed with marginal distribution functions F_k, k=1, 2, \cdots,n , and let t := t(n, s) be the solution of (6). Then E(N[n, s])\le \left( \sum_{k=1}^n F_k(t(n, s))\right)-\frac{s-E(S_{A[n,s]})}{t(n,s)} .
(7) The improvement in (7) compared with (5) therefore consists of \frac{s-E(S_{A[n,s]})}{t(n,s)} . The expected residual in the numerator is typically difficult to compute or estimate, but there exist nice exceptions.
For example, if all X_k are independent exponential random variables, then the memoryless property implies (if s is exceeded) the distributional symmetry of the residual and the overshoot over s . For fixed s one can then show that : \frac{s-E(S_{A[n,s]})}{t(n,s)} \to 1/2 {\rm~as~} n \to \infty . This improvement fluctuates around 1/2 , and the convergence to 1/2 , (simulations) seems quick.
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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1312480525 under CC BY-SA 4.0; modifications have been made.