EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 1, No. 1, 2008, (60-81)
ISSN 1307-5543 – www.ejpam.com

Honorary Invited Paper

Sharp Bounds for the Probability of the Union of Events
Under Unimodality Condition

András Prékopa∗, Mine Subasi , Ersoy Subasi
RUTCOR, Rutgers Center for Operations Research, 640 Bartholomew Road Piscataway, NJ

08854-8003, USA.

Abstract. Linear programming problem is formulated for bounding the probability of the union
of events, where the probability distribution of the occurrences is supposed to be unimodal with
known mode and some of the binomial moments of the events are also known. Using a theorem on
combinatorial determinants the dual feasible bases of a relaxed problem are fully described. The
bounds for the probability of the union are presented in the form of formulas as well as the results
of customized algorithmic solution of the LP’s involved.
AMS subject classifications: 90C05, 90B25, 60E15.
Key words: Binomial moment problem, linear programming, bounding probabilities, discrete uni-
modality, reliability.

1. Introduction

Let A1, ..., An be arbitrary events in an arbitrary probability space. The kth binomial
moment of them is designated by Sk and is defined by the equation:

Sk =
∑

1≤i1<...<ik≤n

P (Ai1 ...Aik) , k = 1, ..., n .

Let S0 = 1. It is well known that (see, e.g., Prékopa [11])

Sk = E
[(

ν
k

)]
, k = 0, ..., n , (1.1)

where ν is the number of those events that occur.
If we introduce the notation pk = P (ν = k), k = 0, ..., n, then we can write (1.1) in

the following more detailed form:

Sk =
n∑

i=0

(
i
k

)
pi , k = 0, ..., n .

∗Corresponding author. Email addresses: prekopa@rutcor.rutgers.edu (A.Prékopa),
Ämsub@rutcor.rutgers.edu (M.Subasi), esub@rutcor.rutgers.edu (E.Subasi)

http://www.ejpam.com 60 c© 2007 EJPAM All rights reserved.



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 61

To compute the probability of the union of the events the inclusion-exclusion formula
is available:

P (A1 ∪ ... ∪An) = S1 − S2 + ... + (−1)n−1Sn .

However, if n is large, we may not be able to compute all the binomial moments, still,
we may be able to compute a few of them. Given that, and further information about
the probability of the random variable ν, we can give lower and upper bounds for the
probability of the union. The bounds may serve for approximation of that probability
provided that they are close to each other.

In this paper we assume that Sk1 , ..., Skm are known for some 1 ≤ k1 < ... < km , m <
n. We do not assume the knowledge of the probability distribution {pi} but we assume
that it is unimodal, i.e., there exists an integer M (0 ≤ M ≤ n) such that p0 ≤ ... ≤ pM ,
pM ≥ ... ≥ pn. The number M may be equal to 0 or n, or satisfy 0 < M < n.

To obtain lower and upper bounds for the probability of the union of events we formu-
late the LP:

min(max)
n∑

i=1

pi

subject to

n∑

i=0

(
i

kj

)
pi = Skj , j = 0, ..., m (1.2)

p0 ≤ ... ≤ pM

pM ≥ ... ≥ pn

pi ≥ 0 , i = 0, ..., n ,

where k0 = 0. In problem (1.2) the p0, ..., pn are unknown variables. If m < n, then there
are infinitely many probability distributions satisfying the constraints of problem (1.2).
One of them is the true distribution of ν. This implies that the optimum value of the
min (max) problem (1.2) is a lower (upper) bound for the probability of the union. These
bounds have the property that, given Sk1 , ..., Skm and the knowledge of the unimodality of
{pi}, no better bounds can be given for P (A1 ∪ ...∪An). In view of this fact, we call them
sharp bounds. The binomial moment problem, without the unimodality constraint, has
extensively been studied. Prékopa [7–10] has shown that the sharp Bonferroni inequalities
of Dawson and Sankoff [4] and others can be formulated as linear programming problems.
For the case of m ≤ 3 and k1 = 1, k2 = 2, k3 = 3, Kwerel [6] has already used linear
programming to obtain sharp bounds for the probability of the union. He fully described
the dual feasible bases of the problem, also in the cases, where we are bounding the
probabilities that at least r and exactly r events occur, reproduced known formulas this
way and gave special dual type algorithms to solve the problems. Boros and Prékopa [1]
exploited the linear programming methodology and derived a variety of sharp bounds of
Boolean functions of events. The list of other papers presenting bounds along this line



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 62

includes Prékopa, Gao [13], Bukszár [3], Bukszár, Prékopa [2].
The paper by E. Subasi, M. Subasi and A. Prékopa [14] is the first, where sharp bounds

are presented for the probability of the union under unimodality constraint for the distri-
bution of the random variable ν. In that paper problem (1.2) was used for the case of
m = 2, k1 = 1, k2 = 2 and bounds are given by the use of formulas as well as by the
dual algorithm of linear programming. In another paper by E. Subasi, M. Subasi and A.
Prékopa, bounding formulas have been obtained for the probability that at least r and
exactly r out of n events occur, under the same conditions.

The purpose of the present paper is to derive a general theorem in connection with
problem (1.2) that characterizes the dual feasible bases of a relaxed version of the prob-
lem, further, to present closed form and algorithmic bounds for the probability of the
union.

As it is known in linear programming theory, the objective function value correspond-
ing to any dual feasible basis in the minimization (maximization) problem provides us
with a lower (upper) bound for the optimum value of the problem.

First we reformulate problem (1.2) by introducing new variables v0, ..., vn. This can be
done in two different ways:

p0 = v0 , p1 = v0 + v1 , ... , pM = v0 + ... + vM

pM+1 = vM+1 + ... + vn , pM+2 = vM+2 + ... + vn , ... , pn = vn , (1.3)

and
p0 = v0 , p1 = v0 + v1 , ... , pM−1 = v0 + ... + vM−1

pM = vM + ... + vn , pM+1 = vM+1 + ... + vn , ... , pn = vn . (1.4)

The case M = n is included in (1.3) and the case M = 0 included in (1.4).
If we use representation (1.3) in problem (1.2), we obtain the following problem:

min(max) {Mv0 +
M∑

i=1

(M − i + 1)vi +
n∑

i=M+1

(i−M)vi}

subject to
M∑

i=0

(M − i + 1)vi +
n∑

i=M+1

(i−M)vi = 1 (1.5)

M∑

i=0

[(
i

kj

)
+ ... +

(
M
kj

)]
vi +

n∑

i=M+1

[(
M + 1

kj

)
+ ... +

(
i

kj

)]
vi = Skj ,

j = 1, ...,m

v0 + ... + vM − vM+1 − ...− vn ≥ 0 (1.5a)

vi ≥ 0 , i = 0, ..., n .



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 63

In case of representation (1.4) the problem can be formulated as follows:

min(max) {(M − 1)v0 +
M−1∑

i=1

(M − i)vi +
n∑

i=M

(i−M + 1)vi}

subject to
M−1∑

i=0

(M − i)vi +
n∑

i=M

(i−M + 1)vi = 1 (1.6)

M−1∑

i=0

[(
i

kj

)
+ ... +

(
M − 1

kj

)]
vi +

n∑

i=M

[(
M
kj

)
+ ... +

(
i

kj

)]
vi = Skj ,

j = 1, ..., m

vM + ... + vn − v0 − ...− vM−1 ≥ 0 (1.6a)

vi ≥ 0 , i = 0, ..., n .

Problem (1.5) without the constraint (1.5a) and problem (1.6) without (1.6a) will be
called relaxed problems. For both relaxed problems A = (a0, ..., an) will designate the ma-
trix of the equality constraints, b the right hand side vector and c the vector of coefficients
of the objective function.

The organization of the paper is as follows. In Section 2 we characterize the dual
feasible bases of the relaxed problem. In Section 3 bounding formulas are derived for the
probability of the union, for the case of m = 2 and general k1, k2 (1 ≤ k1 < k2 ≤ n). In
Section 4 we present closed form bounds for the case of m = 3 and k1 = 1, k2 = 2, k3 = 3.
In Section 5 upper bound formulas are derived for the probability of the union, for the case
of m = 4 and k1 = 1, k2 = 2, k3 = 3, k4 = 4. In Section 6 general algorithms are presented
to obtain algorithmic bounds. In Section 7 we present an application of our bounding
methodology, where shape information about the unknown probability distribution can
be used. Finally, numerical examples are presented in Section 8.



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 64

2. Characterization of the dual feasible bases of the relaxed problem

In what follows we make use of a general theorem for the Pascal matrix, i.e., the matrix
P consisting of binomial coefficients:

P =




1 1 1 1 · · · 1 1
1 2 3 · · · n− 1 n

1
(

3
2

)
· · ·

(
n− 1

2

) (
n
2

)

. . .
...

...

1
(

n
n− 1

)

1




,

where there are zeros in the unfilled positions.
The term “minor” of a matrix will be used in the following sense: it is the determinant

of a submatrix crossed out arbitrarily by the same number of rows and columns.

Theorem 2.1. [5, 7] Any minor of P that has all positive entries in its main diagonal, is
positive.

In the next theorem we characterize the dual feasible bases of the relaxed version of
problems (1.5), (1.6). For basic notions, facts and algorithms in connection with linear
programming the reader is referred to the paper by Prékopa [12].

Theorem 2.2. Any dual feasible basis of any of the relaxed problems (1.5), (1.6) has one of
the following structures, presented in terms of the subscripts:

m + 1 even m + 1 odd

min problem {0, i, i + 1, ..., j, j + 1, n} {0, i, i + 1, ..., j, j + 1}

max problem {0, 1, i, i + 1, ..., j, j + 1} {0, 1, i, i + 1, ..., j, j + 1, n}
or IB ⊂ {1, ..., n} or IB ⊂ {1, ..., n}

where IB is the set of subscripts of the vectors that are in the basis B. In addition all dual
feasible bases are dual nondegenerate, except for those with IB ⊂ {1, ..., n} which are dual
degenerate.

Proof. We carry out the proof for the relaxed problem (1.5). The proof of the assertion
for problem (1.6) is the same. For the sake of simplicity we prove the assertion for the
case of kj = j, j = 1, ..., m. The reasoning is, however applicable for the general case.

Let us write up in detailed form the matrix A of the equality constraints of problem
(1.5), with the objective function coefficients on top of it:



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 65

If M = n, then the columns below M +1, ..., n do not exist. A basis B in the minimization
problem (1.5) is dual feasible if the following inequalities hold:

cT
BB−1ap ≤ cp for any nonbasic p .

For the maximization problem the dual feasibility of a basis is defined by the reversed
inequalities. A basis B is dual degenerate if there is at least one nonbasic p such that
cp − cT

BB−1ap = 0. Since we have
(

1 cT
B

0 B

) (
cp − cT

BB−1ap

B−1ap

)
=

(
cp

ap

)
,

the first component of the solution of this equation can be expressed as

cp − cT
BB−1ap =

1
|B|

∣∣∣∣
cp cT

B

ap B

∣∣∣∣ .

We are interested in the sign of |B| and
∣∣∣ cp cT

B
ap B

∣∣∣. In connection with them we prove the
following.
Lemma. We have the inequality |B| > 0 and if 0 ∈ IB, then the determinant that comes
out of

∣∣∣ cp cT
B

ap B

∣∣∣, if we put
(

cp

ap

)
in its right place (the column subscripts are in increasing

order), is also positive, where p is a nonbasic subscript.
Proof of the Lemma. Since B is a basis, it follows that |B| 6= 0. We prove that this value is
positive.

The entries in the first row can be written up as sum of 1’s so that the number of terms
in any position in that row is equal to the number of terms in any entry in its column. Then
we apply a column subtraction procedure, further, split the obtained determinant into a
sum of determinants. Any determinant in the obtained sum is either zero, or positive, by



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 66

Theorem 1, because they are minors, crossed out of the matrix P . At least one term must
be positive because |B| 6= 0. It follows that |B| > 0.

Now we prove the second assertion. If
(

cp

ap

)
is put in its right place, then the first

column of
(

cT

A

)
will be the first column of the new determinant. If we subtract the

first row from the second row in the determinant, then the first entry in the second row
becomes −1 and the others 0. If we develop the determinant according to the second
row, then, due to the special structure of the determinant, we obtain a minor of order
m + 1 crossed out of the matrix A. If IB = {0, i1, ..., im}, where 1 ≤ i1 < ... < im, then the
subscript set of the columns of the minors is {i1, ..., p, ..., im}, where i1 < ... < p < ... < im.
Thus, 0 is removed from IB and p is included. It is not difficult to see that the positivity of
|B| implies the positivity of the minor. We have proved the Lemma.

Returning to the proof of the Theorem 2, consider first the case 0 /∈ IB. Then |B| > 0
and ∣∣∣∣

cp cT
B

ap B

∣∣∣∣ =
{

0 if p 6= 0
< 0 if p = 0 .

Hence, B is a dual feasible basis in the maximization problem.
If, on the other hand, 0 ∈ IB, then still |B| > 0 and by the Lemma, the determinant∣∣∣ cp cT

B
ap B

∣∣∣ is equal to the (m + 1) × (m + 1) minor taken from A, corresponding to the

columns {i1, ..., p, ..., im}, multiplied by (−1)h(p), where h(p) is the number of subscripts
in B that are smaller than p. The minor is positive by the Lemma. We want to ensure
the positivity of

∣∣∣ cp cT
B

ap B

∣∣∣ for any nonbasic p. Now, if it is a minimization problem, then
h(p) must be even for any nonbasic p which implies that {i1, ..., im} = {i, i + 1, ..., j, j + 1}
if m is even (m + 1 is odd) and {i1, ..., im} = {i, i + 1, ..., j, j + 1, n} if m is odd (m + 1
is even). If it is a maximization problem, then h(p) must be odd for any nonbasic p
which implies that {i1, ..., im} = {1, i, i + 1, ..., j, j + 1, n} if m is even (m + 1 is odd) and
{i1, ..., im} = {1, i, i + 1, ..., j, j + 1} if m is odd (m + 1 is even). This proves the theorem.

Remark. If kj = j, j = 1, ...,m, then all (m+1)×(m+1) submatrices of A are nonsingular.
This is, however, not necessarily the case if {k1, ..., km} 6= {1, ..., m}. Thus, when picking
a dual feasible basis satisfying the structure in Theorem 2, we have to check on their
independence as well.

3. Closed form bounds for the probability of the union based on Sk1 , Sk2

Let m = 2 and assume that the binomial moments Sk1 , Sk2 , 1 ≤ k1 < k2 ≤ n, are

known. If C(n, k) =
(

n
k

)
, then we have the following recurrence relation known as

Pascal’s rule:
C(n + 1, k + 1) = C(n, k) + C(n, k + 1) .



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 67

By the use of these the coefficients of the equality constraints in the relaxed problems can
be given as follows:

j∑

s=i

(
s
k

)
=

(
j + 1
k + 1

)
−

(
i

k + 1

)
. (3.1)

In view of (3.1) the relaxed version of problem (1.5) can be written in the form:

min(max) {Mv0 +
M∑

i=1

(M − i + 1)vi +
n∑

i=M+1

(i−M)vi}

subject to
M∑

i=0

(M − i + 1)vi +
n∑

i=M+1

(i−M)vi = 1 (3.2)

M∑

i=0

[(
M + 1
k1 + 1

)
−

(
i

k1 + 1

)]
vi +

n∑

i=M+1

[(
i + 1

k1 + 1

)
−

(
M + 1
k1 + 1

)]
vi = Sk1

M∑

i=0

[(
M + 1
k2 + 1

)
−

(
i

k2 + 1

)]
vi +

n∑

i=M+1

[(
i + 1

k2 + 1

)
−

(
M + 1
k2 + 1

)]
vi = Sk2

vi ≥ 0 , i = 0, ..., n .

Theorem 2 provides us with the following dual feasible bases for the above problem:

Bmin = {0, i, i + 1} , 1 ≤ i ≤ n− 1 ,

Bmax = {0, 1, n} or Bmax ⊂ {1, ..., n} .



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 68

In order to present our formulas in compact forms we introduce the notations:

Σr
i,j = (j − i + 1)

(
i− 1

r

)
−

(
j + 1
r + 1

)
+

(
i

r + 1

)

Σr,t
i,j =

(
i− 1

r

) [(
j + 1
t + 1

)
−

(
i

t + 1

)]
−

(
i− 1

t

) [(
j + 1
r + 1

)
−

(
i

r + 1

)]

γr
i,j = i

[(
j + 1
r + 1

)
−

(
i

r + 1

)]
− (j − i + 1)

(
i

r + 1

)

γr,t
i,j =

(
i

r + 1

) [(
j + 1
t + 1

)
−

(
i

t + 1

)]
−

(
i

t + 1

) [(
j + 1
r + 1

)
−

(
i

r + 1

)]

βr
i,j = (j + 1)

(
j + 1

r

)
−

(
j + 1
r + 1

)
+

(
i

r + 1

)

βr,t
i,j =

(
j + 1

r

) [(
j + 1
t + 1

)
−

(
i

t + 1

)]
−

(
j + 1

t

) [(
j + 1
r + 1

)
−

(
i

r + 1

)]

αr
i,j = (j − i + 1)

(
j + 1

r

)
−

(
j + 1
r + 1

)
+

(
i

r + 1

)

αr,t
i,j =

(
j + 1

r

) [(
j + 1
t + 1

)
−

(
i

t + 1

)]
−

(
j + 1

t

) [(
j + 1
r + 1

)
−

(
i

r + 1

)]

δr
i,j = (i− 1)

[(
j + 1
r + 1

)
−

(
i

r + 1

)]
− (j − i)

(
i

r + 1

)
.

(3.3)

We use problem (3.2) to present lower and upper bounds for P (ν ≥ 1). To do this we
find the optimal bases for the minimization and maximization problems, respectively. We
already have a full description of the dual feasible bases. What we need is to find those
(one for the min problem and one for the max problem) that are also primal feasible.
Three cases will be considered.
Case 1. Let 1 ≤ i ≤ M − 1. The primal feasibility conditions for Bmin are given below:

Sk1Σ
k2
i+1,M − Sk2Σ

k1
i+1,M + Σk1,k2

i+1,M ≥ 0 ,

Sk1γ
k2
i+1,M − Sk2γ

k1
i+1,M − γk1,k2

i+1,M ≥ 0 ,

Sk1γ
k2
i,M − Sk2γ

k1
i,M + γk1,k2

i,M ≤ 0 .

In this case the closed form lower bound for P (ν ≥ 1) is expressed by

1 −
Sk1Σ

k2
i+1,M − Sk2Σ

k1
i+1,M + Σk1,k2

i+1,k

i Σk1,k2

i+1,M +
(

i
k1 + 1

)
Σk2

i+1,M −
(

i
k2 + 1

)
Σk1

i+1,M

≤ P (ν ≥ 1) , (3.4)

where Σr
i,j , Σ

r,t
i,j , γ

r
i,j , γ

r,t
i,j are given in (3.3).

Case 2. Let i = M . The conditions that ensure the primal feasibility of Bmin = {0,M, M +
1} are as follows:

Sk1

(
M

k2 − 1

)
− Sk2

(
M

k1 − 1

)
− k2 − k1

M − k2 + 1

(
M + 1

k1

)(
M
k2

)
≥ 0 ,



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 69

Sk1β
k2
1,M − Sk2β

k1
1,M + βk1,k2

1,M ≥ 0 ,

Sk1β
k2
1,M−1 − Sk2β

k1
1,M−1 + βk1,k2

1,M−1 ≥ 0 .

The corresponding closed form lower bound for P (ν ≥ 1) is given by

1 −
Sk1

(
M

k2 − 1

)
− Sk2

(
M

k1 − 1

)
− k2−k1

M−k2+1

(
M + 1

k1

)(
M
k2

)

βk1,k2

1,M−1 − M (k2−k1)
M−k2+1

(
M + 1

k1

)(
M
k2

) ≤ P (ν ≥ 1) , (3.5)

where βr
i,j , β

r,t
i,j are given in (3.3).

Case 3. Let M + 1 ≤ i ≤ n − 1. Bmin is primal feasible if and only if i is determined by
the following conditions:

Sk1α
k2
M+1,i − Sk2α

k1
M+1,i + αk1,k2

M+1,i ≥ 0 ,

Sk1γ
k2
M+1,i+1 − Sk2γ

k1
M+1,i+1 − γk1,k2

M+1,i+1 ≥ 0 ,

Sk1γ
k2
M+1,i − Sk2γ

k1
M+1,i − γk1,k2

M+1,i ≥ 0 .

Then the closed form lower bound is the following:

1 − Sk1α
k2
M+1,i − Sk2α

k1
M+1,i + αk1,k2

M+1,i(
M + 1
k1 + 1

)
αk2

M+1,i −
(

M + 1
k2 + 1

)
αk1

M+1,i + (M + 1) αk1,k2

M+1,i

≤ P (ν ≥ 1) , (3.6)

where αr
i,j , α

r,t
i,j , γ

r
i,j , γ

r,t
i,j are given in (3.3).

If Bmax ⊂ {1, ..., n} is primal feasible in the relaxed version of the maximization prob-
lem (3.2), then the upper bound for the probability of the union is equal to 1.

The basis Bmax = {0, 1, n} is primal feasible if and only if the following conditions
hold:

Sk1δ
k2
M+1,n − Sk2δ

k1
M+1,n − γk1,k2

M+1,n ≤ 0 ,

Sk1γ
k2
M+1,n − Sk2γ

k1
M+1,n − γk1,k2

M+1,n ≥ 0 ,

Sk1

(
M + 1
k2 + 1

)
≤ Sk2

(
M + 1
k1 + 1

)
.

The corresponding closed form upper bound for P (ν ≥ 1) is given below:

P (ν ≥ 1) ≤ Sk1δ
k2
M+1,n − Sk2δ

k1
M+1,n

γk1,k2

M+1,n

, (3.7)

where δr
i,j , γ

r
i,j , γ

r,t
i,j are given in (3.3).

If we use the relaxed version of problem (1.6), rather than that of problem (1.5), then
the lower and upper bounds change in such a way that we have to replace M − 1 for M



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 70

in the formulas of Section 3.

4. Closed form bounds for the probability of the union based on S1, S2, S3

We look at the relaxed versions of problems (1.5), (1.6) and create bounds for the
probability of the union, based on the knowledge of the binomial moments S1, S2, S3.
Since m + 1 is even, then by the use of Theorem 2, we derive that any dual feasible basis
Bmin of the relaxed version of the minimization problem (1.5) has the form:

Bmin = {0, i, i + 1, n} , i = 1, ..., n− 2 .

Similarly, any dual feasible basis Bmax of relaxed version of the maximization problem has
the form:

Bmax = {0, 1, i, i + 1}, i = 2, ..., n− 1, or Bmax ⊂ {1, ..., n} .

Below we present conditions that ensure the primal feasibility of Bmin as well as the
corresponding lower bounds for P (ν ≥ 1), i.e., the probability of the union of the events.
Case 1. Let 1 ≤ i ≤ M − 1. Bmin is primal feasible if and only if i is determined by the
conditions

2[iM + (n− 1)(i + M − 1)]S1 − 6(n + i + M − 3)S2 + 24S3 ≥ Mni ,

2[M(i− 1) + (n− 1)(i + M − 2)]S1 − 6(n + i + M − 4)S2 + 24S3 ≤ Mn(i− 1) ,

2(i− 1)(i + 2M − 2)S1 − 6(2i + M − 4)S2 + 24S3 ≥ Mi(i− 1) ,

2[i(n + 2M + i) + (n− 1)(i + M − 1)]S1 − 6(n + 2i + M − 3)S2 + 24S3

≤ i[M(2n + i + 1) + (i + 1)(n + 1)] .

In this case the lower bound for P (ν ≥ 1) is obtained as follows:

2[i(n + 2M + i) + (n− 1)(i + M − 1)]S1 − 6(n + 2i + M − 3)S2 + 24S3

(n + 1)(M + 1)(i + 1)i

+
Mn(i− 1)

(n + 1)(M + 1)(i + 1)
≤ P (ν ≥ 1) . (4.1)

Case 2. Let i = M . Basis Bmin = {0,M, M + 1, n} is primal feasible if and only if the
following conditions are satisfied:

2M(2n + M − 1)S1 − 6(n + 2M − 2)S2 + 24S3 ≥ M(M + 1)n ,

2(M − 1)(2n + M − 2)S1 − 6(n + 2M − 4)S2 + 24S3 ≤ (M − 1)Mn ,

6M(M − 1)S1 − 18S2 + 24S3 ≥ (M − 1)M(M + 1) ,



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 71

6M(n + M)S1 − 6(n + 3M − 2)S2 + 24S3 ≤ (M + 1)(3n + M + 2) .

The corresponding lower bound for P (ν ≥ 1) is given below:

6M(n + M)S1 − 6(n + 3M − 2)S2 + 24S3

M(M + 1)(M + 2)(n + 1)
+

n(M − 1)
(M + 2)(n + 1)

≤ P (ν ≥ 1) . (4.2)

Case 3. Let M +1 ≤ i ≤ n−2. Bmin is primal feasible if and only if i satisfies the following
conditions:

2[nM + i(n + M − 1)]S1 − 6(n + i + M − 2)S2 + 24S3 ≥ Mn(i + 1) ,

2[iM + (n− 1)(i + M − 1)]S1 − 6(n + i + M − 3)S2 + 24S3 ≤ Mni ,

2i(i + 2M − 1)S1 − 6(2i + M − 2)S2 + 24S3 ≥ i(M + 1)M ,

2[i(n + 2M + i) + (n + 1)(i + M + 1)]S1 − 6(n + 2i + M − 1)S2 + 24S3

≤ (i + 1)[iM + (n + 1)(i + 2M + 2)] .

In this case the lower bound is obtained as follows:

2[i(n + 2M + i) + (n + 1)(i + M + 1)]S1 − 6(n + 2i + M − 1)S2 + 24S3

(i + 1)(i + 2)(M + 1)(n + 1)

+
niM

(i + 2)(M + 1)(n + 1)
≤ P (ν ≥ 1) . (4.3)

In order to obtain an upper bound for P (ν ≥ 1) we consider the relaxed version of
the maximization problem (1.5). Note that if the dual feasible basis Bmax ⊂ {1, ..., n} is
also primal feasible, then the optimum value of the maximization problem, i.e., the upper
bound for the probability of the union, is equal to 1. As before, we have three cases for
the choice of i.
Case 1. Let 2 ≤ i ≤ M − 1. The primal feasibility conditions for the basis Bmax =
{0, 1, i, i + 1} are as follows:

2(i− 1)(i + 2M − 2)S1 − 6(2i + M − 4)S2 + 24S3 ≥ M(i− 1)i ,

2(i− 1)(M − 1)S1 − 6(i + M − 3)S2 + 24S3 ≤ 0 ,

2(i− 2)(M − 1)S1 − 6(i + M − 4)S2 + 24S3 ≥ 0 ,

2[i(i + M) + (i− 1)(M − 1)]S1 − 6(2i + M − 3)S2 + 24S3 ≤ i(i + 1)(M + 1) .

The corresponding upper bound for P (ν ≥ 1) is presented below:

P (ν ≥ 1) ≤ 2[i(i + M) + (i− 1)(M − 1)]S1 − 6(2i + M − 3)S2 + 24S3

i(i + 1)(M + 1)
. (4.4)



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 72

Case 2. Let i = M . The basis Bmax = {0, 1, M, M + 1} is primal feasible if and only if

6M(M − 1)S1 − 18(M − 1)S2 + 24S3 ≥ (M − 1)M(M + 1) ,

2M(M − 1)S1 − 12(M − 1)S2 + 24S3 ≤ 0 ,

2(M − 1)(M − 2)S1 − 12(M − 2)S2 + 24S3 ≥ 0 ,

6M2S1 − 6(3M − 2)S2 + 24S3 ≤ M(M − 1)(M + 1) .

The corresponding upper bound for P (ν ≥ 1) is given below:

P (ν ≥ 1) ≤ 6M2S1 − 6(3M − 2)S2 + 24S3

M(M + 1)(M + 2)
. (4.5)

Case 3. Let M + 1 ≤ i ≤ n − 1. The basis Bmax is primal feasible if and only if i is
determined by the following conditions:

2i(i + 2M − 1)S1 − 6(2i + M − 2)S2 + 24S3 ≥ i(i + 1)M ,

2i(M − 1)S1 − 6(i + M − 2)S2 + 24S3 ≤ 0 ,

2(i− 1)(M − 1)S1 − 6(i + M − 3)S2 + 24S3 ≥ 0 ,

2[i(i + M) + (i + 1)(M + 1)]S1 − 6(2i + M − 1)S2 + 24S3 ≤ (i + 1)(i + 2)(M + 1) .

With i satisfying these inequalities we have the upper bound given by:

P (ν ≥ 1) ≤ 2[i(i + M) + (i + 1)(M + 1)]S1 − 6(2i + M − 1)S2 + 24S3

(i + 1)(i + 2)(M + 1)
. (4.6)

If we replace M −1 for M in the formulas of Section 4, then we obtain the closed form
bounds that come out of the relaxed version of problem (1.6).

5. Closed form upper bounds for the probability of the union based on
S1, S2, S3, S4

In this section we present upper bound formulas for the probability of the union of
events based on the first four binomial moments.

Since m + 1 is odd, then by Theorem 2, any dual feasible basis Bmax of the relaxed
version of the maximization problem (1.5) or (1.6) is of the form:

Bmax = {0, 1, i, i + 1, n}, i = 2, ..., n− 1, or Bmax ⊂ {1, ..., n} .

If Bmax ⊂ {1, ..., n}, then the upper bound for P (ν ≥ 1) is 1. In order to determine the
index i that ensures the primal feasibility of the basis of the form Bmax = {0, 1, i, i + 1, n}
we consider the following cases.



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 73

Case 1. Let 2 ≤ i ≤ M − 1. The primal feasibility conditions are:

2[i(i− 1)(n + M)− (M − 1)(n− 1) + 2i(nM + 1)]S1

−6(3n + 3M − nM − i2 + 5i− 2iM − 2ni− 7)S2 + 24(n + 2i + M − 6)S3 − 120S4

≤ i(i + 1)(n + 1)(M + 1) ,

2(i− 1)(ni + iM + 2nM − 2n− i− 2M + 2)S1 − 6[nM + (i− 2)(2n + 2M + i− 5)]S2

+24(n + 2i + M − 7)S3 − 120S4 ≥ (i− 1)inM ,

2(M − 1)(n− 1)(i− 1)S1 − 6(ni + iM + nM − 3n− 3i− 3M + 7)S2

+24(n + i + M − 6)S3 − 120S4 ≤ 0 ,

2(M − 1)(n− 1)(i− 2)S1 − 6(ni + iM + nM − 4n− 3i− 4M + 10)S2

+24(n + i + M − 7)S3 − 120S4 ≥ 0 ,

2(M − 1)(i− 1)(i− 2)S1 − 6(i− 2)(i + 2M − 5)S2

+24(2i + M − 7)S3 − 120S4 ≤ 0 .

Under these conditions the corresponding upper bound is given below:

P (ν ≥ 1) ≤ 2[i(i− 1)(n + M)− (M − 1)(n− 1) + 2i(nM + 1)]S1

(M + 1)i(i + 1)(n + 1)

− 6(3n + 3M − nM − i2 + 5i− 2iM − 2ni− 7)S2

(M + 1)i(i + 1)(n + 1)
(5.1)

+
24(n + 2i + M − 6)S3 − 120S4

(M + 1)i(i + 1)(n + 1)
.

Case 2. Let i = M . The basis Bmax = {0, 1, M, M + 1, n} is primal feasible if and only if

2M(3nM + M2 + 2)S1 − 6(3M2 + (3M − 2)(n− 2))S2 + 24(n + 3M − 5)S3 − 120S4

≤ M(M + 1)(M + 2)(n + 1) ,

2M(M − 1)(3n + M − 2)S1 − 18(M − 1)(n + M − 2)S2 + 24(n + 3M − 6)S3 − 120S4

≥ M(M − 1)(M + 1)n ,

2M(M − 1)(n− 1)S1 − 6(M − 1)(2n + M − 4)S2 + 24(n + 2M − 5)S3 − 120S4 ≤ 0 ,

2(M − 1)(M − 2)(n− 1)S1− 6(M − 2)(2n + M − 5)S2 + 24(n + 2M − 7)S3− 120S4 ≥ 0 ,

2M(M − 1)(M − 2)S1 − 18(M − 1)(M − 2)S2 + 72(M − 2)S3 − 120S4 ≤ 0 .



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 74

The closed form upper bound for P (ν ≥ 1) is given by

P (ν ≥ 1) ≤ 2M(3nM + M2 + 2)S1 − 6(3M2 + (3M − 2)(n− 2))S2

M(M + 1)(M + 2)(n + 1)

+
24(n + 3M − 5)S3 − 120S4

M(M + 1)(M + 2)(n + 1)
. (5.2)

Case 3. Let M + 1 ≤ i ≤ n − 2. Bmax is primal feasible if and only if i satisfies the
conditions:

2[(i+1)(ni+nM + iM +1)+n+ i+M ]S1−6[(i−1)(i−2)+2i(n+M)+(n−1)(M−1)]S2

+24(n + 2i + M − 4)S3 − 120S4 ≤ (i + 1)(i + 2)(M + 1)(n + 1) ,

2i[n(i + M) + (M − 1)(n + i− 1)]S1 − 6[(i− 1)(2n + 2M + i− 4) + nM ]S2

+24(n + 2i + M − 5)S3 − 120S4 ≥ ni(i + 1)M ,

2i(M − 1)(n− 1)S1 − 6[(n− 2)(i + M − 2) + i(M − 1)]S2

+24(n + i + M − 5)S3 − 120S4 ≤ 0 ,

2(i− 1)(M − 1)(n− 1)S1 − 6[(n− 3)(i + M − 1) + iM − 2n + 4]S2

+24(ni + M − 6)S3 − 120S4 ≥ 0 ,

2i(i− 1)(M − 1)S1 − 6(i− 1)(i + 2M − 4)S2 + 24(2i + M − 5)S3 − 120S4 ≤ 0 .

The corresponding upper bound for P (ν ≥ 1) is given by

P (ν ≥ 1) ≤ 2[(i + 1)(ni + nM + iM + 1) + n + i + M ]S1

(i + 1)(i + 2)(n + 1)(M + 1)

− 6[(i− 1)(i− 2) + 2i(n + M) + (n− 1)(M − 1)]S2

(i + 1)(i + 2)(n + 1)(M + 1)
(5.3)

+
24(n + 2i + M − 4)S3 − 120S4

(i + 1)(i + 2)(n + 1)(M + 1)
.

As before, if we apply our bounding technique on the relaxed problem (1.6), rather
than (1.5), then the just derived formulas provide us with the upper bounds if we replace
M − 1 for M .

6. Algorithmic bounds

In Sections 3, 4 and 5 we have derived closed form bounds for the probability of
the union, by the use of the relaxed problems (1.5), (1.6) for the cases of m = 2, 3, 4. For
larger m values the solution of the relaxed problems can be obtained by specially designed
dual algorithms of linear programming. Once an algorithm of this kind terminates, the



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 75

solutions for the non-relaxed problem can be continued again by the dual algorithm. In
fact, as it is well known in linear programming, the dual algorithm can efficiently be used,
as a reoptimization technique, whenever the optimal basis has already been found but a
further constraint is introduced into the problem.

The algorithm presented below works in this way and is applicable to cases with con-
secutive and non-consecutive moments. We remark that it is more practical to carry out
the algorithms to obtain the bound, rather than to apply a complicated closed form for-
mula.
Algorithmic solutions of problems (1.5), (1.6)
Step 0. Find an initial dual feasible basis B to the relaxed problem. Any basis that has the
structure presented in Theorem 2 is suitable.
Step 1. Check for primal feasibility. If B−1b ≥ 0, then the solution of the relaxed problem
terminates. Go to Step 4. Otherwise go to Step 2.
Step 2. If (B−1b)j < 0, then the jth vector in B (not necessarily equal to aj) is a candidate
to leave the basis. Choose arbitrarily among the candidates to leave the basis. Go to Step
3.
Step 3. Include the vector al into the basis that restores the dual feasible basis structure.
Go to Step 1.
Step 4. If the additional constraint v0 + ... + vM ≥ vM+1 + ... + vn (or vM + ... + vn ≥
v0 + ... + vM−1) is satisfied, then the solution of problem (1.5) (or (1.6)) terminates.
Otherwise go to Step 5.
Step 5. Reoptimize the problem with the additional constraint (1.5a) or (1.6a): introduce
slack variable into the additional inequality constraint, prescribe nonnegativity relation
for the slack variable, set up the new dual tableau and carry out the dual method.

If the sequence of probabilities p0, ..., pn is increasing or decreasing, i.e., if M = n or
M = 0, then the solution of problem (1.5) or (1.6) terminates with Step 3. No reopti-
mization is needed. The relaxed problem is equivalent to the original problem (1.5) or
(1.6).

7. Application in Reliability

Let A1, ..., An be independent events and define the random variables X1, ..., Xn as
the characteristic variables corresponding to the above events, respectively, i.e.,

Xi =
{

1 if Ai occurs ,
0 otherwise .

Let pi = P (Xi = 1), i = 1, ..., n. The random variables X1, ..., Xn have logconcave discrete
distributions. Since the convolution of discrete logconcave sequences is logconcave (see,
e.g., Prékopa [11]), it follows that the distribution of X1 + ... + Xn is also logconcave.

In many applications it is an important problem to compute, or at least approximate,



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 76

e.g., by the use of bounds, the probability

P (X1 + ... + Xn ≥ 1) . (7.1)

If I1, ..., IC(n,k) designate the k-element subsets of the set {1, ..., n} and Jl = {1, ..., n}\Il,
l = 1, ..., C(n, k), then we have the equation

P (X1 + ... + Xn ≥ 1) =
n∑

k=1

C(n,k)∑

l=1

∏

i∈Il

pi

∏

j∈Jl

(1− pj) , (7.2)

where C(n, k) =
(

n
k

)
.

If n is large, then the calculation of the probabilities on the right hand side of (7.2)
may be hard, even impossible. However, we can calculate lower and upper bounds for the
probability on the left hand side of (7.2) by the use of the sums:

Sk =
∑

1≤i1<...<ik≤n

pi1 ...pik =
C(n,k)∑

l=1

∏

i∈Il

pi , k = 1, ..., m , (7.3)

where m may be much smaller than n. Since the random variable X1 + ... + Xn has
logconcave, hence unimodal distribution we can impose the unimodality condition on the
probability distribution:

P (X1 + ... + Xn = k) , k = 0, ..., n . (7.4)

Then we solve both the minimization and maximization problems presented in Section 1,
to obtain the bounds for the probability (7.1). If m is small, then the bounds can be
obtained by the formulas of Section 3, 4 and 5. Note that the largest probability (7.4)
corresponds to

kmax =
⌊
(n + 1)

p1 + ... + pn

n

⌋
.

The inclusion-exclusion formula provides us with the probability (7.1), in terms of the
binomial moments S1, ..., Sn:

P (X1 + ... + Xn ≥ 1) =
n∑

k=1

(−1)k−1Sk . (7.5)

However, to compute higher order binomial moments may be extremely difficult, some-
times impossible. The advantage of our approach is that we use the first few binomial
moments S1, ..., Sm, where m is relatively small and in many cases we can obtain very
good bounds.



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 77

8. Numerical examples

We present numerical examples to show that if the probability distribution is unimodal
with known mode, M , then by the use of our bounding methodology, we can obtain tighter
bounds for the probability of the union. In the following examples LB and UB stand for
lower and upper bounds, respectively.
Example 1. We assume that the first m binomial moments of the events are known. In Ta-
ble 1 we present bounds for the probability of the union with and without the unimodality
condition.

The bounds for P (ν ≥ 1), obtained by the use of the relaxed problems (1.5) and (1.6),
are presented in Table 2.



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 78

Example 2. In this example we assume that two (not necessarily consecutive) binomial
moments, Sk1 , Sk2 , (1 ≤ k1 < k2 ≤ n), are known. In Table 2 and 3 we present bounds
for P (ν ≥ 1) with and without the unimodality condition, respectively.



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 79

Example 3. We give an illustration of the algorithm that we have presented in Section
6. Assume that the probability distribution is unimodal and its mode is 5. Let n = 10,
S1 = 5.3568245, S2 = 16.2332237, S3 = 32.377332.

We consider the relaxed version of the minimization problem (1.6) and choose the
initial basis B = {0, 2, 3, 10}, which is dual feasible by Theorem 2.
Iteration 1
Step 0. Initial dual feasible basis: B = {0, 2, 3, 10}. Step 1. Since

B−1b =




0.070527273
−0.024297844
0.06646205
0.097888845


 � 0 ,

it follows that B is not primal feasible.

Step 2. The second vector in B, that is a2, leaves the basis since (B−1b)2 < 0.

Step 3. The vector a4 restores the dual feasible basis structure, hence it enters the basis.

We proceed to the second iteration with the updated basis, B = {0, 4, 3, 10}.
Iteration 2



Prékopa, M. Subasi, E. Subasi / Eur. J. Pure Appl. Math, 1 (2008), (60-81) 80

Step 1. We have

B−1b =




0.068539267
0.046860129
0.0117919

0.097809956


 > 0 .

Thus B is optimal and the optimum value of the relaxed problem (1.6) is 0.931460733.

The solution of the relaxed problem terminates.

Step 4. The additional constraint (1.6a) is equivalent to

v5 + ... + v10 − v0 − ...− v4 = −0.02938134 < 0 .

The optimal solution to the relaxed problem does not satisfy constraint (1.6a).

Step 5. In order to ensure the mode of the distribution is 5 we prescribe (1.6a) as an

additional constraint:

v5 + ... + v10 − v0 − ...− v4 ≥ 0 .

Let us rewrite the constraint in the form

v5 + ... + v10 − v0 − ...− v4 − v11 = 0 ,

where v11 ≥ 0 is slack variable. We use the dual method to reoptimize the problem (see,

e.g., [12]) After applying the dual method to the new problem, we obtain the optimal

basis and the optimum value of problem (1.6), i.e., the lower bound for the probability of

the union as given below:




v0

v3

v4

v5

v10




=




0.0685393
0.0117919
0.0468601
0.0097938
0.09780996




and 0.931905905 ≤ P (ν ≥ 1) .



REFERENCES 81

References

[1] E. Boros, A. Prékopa, Closed form two-sided bounds for probabilities that exactly r and at
least r out of n events occur. Math. Oper. Res., 14: 317–347 (1989).

[2] J. Bukszár, A. Prékopa, Probability bounds with cherry trees. Math. Oper. Res., 26: 174–192
(2001).

[3] J. Bukszár, Hypermultitrees and Bonferroni Inequalities. Mathemtical Inequalities and Appli-
cations, 6: 727–745 (2003).

[4] D.A. Dawson, A. Sankoff, An inequality for probabilities. Proceedings of the American Mathe-
matical Society, 18: 504–507 (1967).

[5] J. Gessel, G. Viennot, Binomial determinants, paths, and hook length formulae. Advences in
Mathematics 58: 300–321 (1985).

[6] S.M. Kwerel, Most Stringent bounds on aggregated probabilities of partially specified depen-
dent probability systems. J. Amer. Stat. Assoc., 70: 472–479 (1975).

[7] A. Prékopa, Boole-Bonferroni inequalities and linear programming. Operations Research 36:
145–162 (1988).

[8] A. Prékopa, Totally positive linear programming problems, in L.V. Kantorovich Memorial Vol-
ume, Oxford Univ. Press, New York, 197–207, 1989.

[9] A. Prékopa, Sharp bounds on probabilities using linear programming. Operations Research,
38: 227–239 (1990).

[10] A. Prékopa, The discrete moment problem and linear programming. Discrete Applied Mathe-
matics 27: 235–254 (1990).

[11] A. Prékopa, Stochastic Programming, Kluwer Academic Publishers, Dordtecht, Boston, 1995.
[12] A. Prékopa, A brief introduction to linear programming. Math. Scientist 21: 85–111 (1996).
[13] A. Prékopa, L. Gao, Bounding the probability of the union of events by the use of aggregation

and disaggregation in linear programs. Discrete Applied Mathematics 145: 444–454 (2005).
[14] E. Subasi, M. Subasi, A. Prékopa, Discrete moment problems with distributions known to

be unimodal. Mathematical Inequalities and Applications, accepted. Available as RUTCOR
Research Report RRR 15-2007.