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
X1,X2,...,X100
[0,1]
s=10
N[n,s]:=N[100,10]
Xj
\{X1,X2,...,X100\}
s=10
N[100,10]
E(N[n,s])
n
s
n
s
E(N[n,s])
Xk
Fk
Let
X1,X2,...
n\in\{1,2,...\}
s\inR+
N[n,s]
X1,X2,...,Xn
s
Now, to obtain
N[n,s]
s
N[s,n]
X1,X2, … ,Xn
X1,n\leX2,n\le … \leXn,n,
\begin{align} N[n,s]= \begin{cases}0&,{\rm~if~}~X1,n>s,\\ max\{~k\in\N:~X1,n+X2,n+ … +Xk,n\les\}&,{\rm~otherwise}.\end{cases} \end{align}(1)
What is the best possible general upper bound for
E(N[n,s])
Theorem 1 Let
X1,X2, … ,Xn
F
E(N[n,s])\lenF(t),
where
t:=t(n,s)
n
t | |
\int | |
0 |
xdF(x)=s
As an example, here are the answers for the questions posed at the beginning.Thus let all
X1,X2, … ,Xn
[0,1]
F(t)=t
[0,1]
dF(x)/dx=1
[0,1]
n
t | |
\int | |
0 |
xdx=nt2/2=s.
The solution is
t=\sqrt{2s/n}
E(N[n,s])\lenF(t)=n\sqrt{2s/n}=\sqrt{2sn}
Since one always has
N[n,s]\len
s\genE(X)=n/2
For the example questions with
n=100,s=10
E(N[100,10])\le\sqrt{2000} ≈ 44.7
n
s
Theorem 2. Let
X1,X2, … ,Xn
Xk
Fk,~k=1,2, … ,n.
N[n,s]
E(N[n,s])\le
n | |
\sum | |
k=1 |
Fk(t)
where
t:=t(n,s)
n | |
\sum | |
k=1 |
t | |
\int | |
0 |
xdFk(x)=s.
Clearly, if all random variables
Xi,i=1,2, … ,n
F
Depending on the type of the distributions
Fk
Let
A[n,s]
N[n,s]
\#A[n,s]=N[n,s]
and let
SA[n,s]
s-SA[n,s]
Theorem 3. Let
X1,X2, … ,Xn
Fk,k=1,2, … ,n
t:=t(n,s)
E(N[n,s])\le\left(
n | |
\sum | |
k=1 |
Fk(t(n,s))\right)-
s-E(SA[n,s]) | |
t(n,s) |
The improvement in (7) compared with (5) therefore consists of
s-E(SA[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
Xk
s
s
s-E(SA[n,s]) | |
t(n,s) |
\to1/2{\rm~as~}n\toinfty
1/2
1/2
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. Also, and in particular, one notes that the maximum number
N[n,s]
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.