Optimal bivariate bonferroni-type inequalities via taking average

OPTIMAL BIVARIATE BONFERRONI-TYPE INEQUALITIES VIA TAKING AVERAGE

MIN-YOUNG LEE

1. Introduction

Let AI, A

_{2 , •••}

,Am be a sequence of events on a given probability

space and let X

^m

(A) be the number of those A's which occur. Put So

=

1 and

Sk

= "

L..J P(A·

¹¹

n A·

¹²

n··· n A·)

I~'-

(1 < k)

where the summation is over all subscripts satisfying 1

:$ il

<

i₂

<

... < ik

~ m.

For convenience in some formulae we adopt the convention S

k =

0 if

k

> m. By turing to indicator variables we immediately find that

(0

~

k

~

m).

Inequalities of the form 2:;==0 ^CkSk

~

P(Xm(A) ;:.:: r)

~

2:;=0 ^dkSk,

where

Cl =

q(r,m) and dk

=

dk(r,m) are constant, possible zero, are called Bonferroni-type inequalities.

In this univariate case, we have proved that

(1)

m-2

P(Xm(A) ~

¹⁾

~ ^{SI -} L ^{P(Ai n Aj) +} L ^{P(Ai n Ai+l n Ai+2)'}

i<jSi+2 i==1

Received July 10, 1995. Revised February 20, 1996.

1991 AMS Subject Classification: 60E15, 60C05.

Key words: Bonferroni-type inequality, the method of indicators.

This paper was supported by NON DIRECTED RESEARCH FUND, Korea Research Foundation, 1994.

Taking the averages of the above upper bounds over

i =

1,2,· .. ,m of (1), we get the following Bonferroni-type inequality (B-T-I).

(2m -

3) (m - 2) P(Xm(A) ;::: 1) ::;

SI -

C;)

^S2

+ (r;) Sa

This inequality is known that it is the best possible upper bound in terms of

SI, S2

and Sa [see Kwerel(1975)].

Now we can extend the univariate B-T-I into the bivariate one. Let Ab A

2 , · · ·

,Am and Bb B

_{2 , · · ·}

,B

n

be two sequences of events on the same probability space. Let X = ^{Xm(A) and Y} = ^Yn(B), respectively, denote the numbers of those Ai and Bj which occur. Put So,o

=

1 and, for integers r and t, set

(2) S

_r,t

= '"' '"' L.J L.J P(A- A· ... A· B· B·

^{11 12 Ir J1 J2} ... B· )^Jt

where the summation is over

all

subscripts satisfying 1 ::;

il

<

i2

<

... <

i_r ::; m

and 1 ::; it < h < ... < jt ::;

n ,

0 ::;

r ::; m

and

o ::; t ::;

n

(We abbreviate An B as AB and an empty intersection is the sample space). We can easily prove (2) by using the method of indicators. The number Sr,t , 1 ::; r , 1 ::; t, is called the binomial moment of the vector (X,Y) because

(3)

Although the univariate case has been studied by many authors, in the bivariate case little information is know.

In

fact, Eva, Galambos [1965] and Meyer [1969J introduced the classical bivariate inequalities and Lee [1992], Galambos and Lee [1992J presented its extensions by using the method of indicators and combinations, and examples of optimal inequalities are shown by Galambos and XU [1993J.

We are interested in bivariate B-T-I which mean bounds by linear combinations of the binomial moments Sr,t. In particular, we want to establish upper bound of

Yl,1 =

P(X ;::: 1, Y ;::: 1) which appears in many problems in statatics (See for example Galambos and Lee [1994]);

Galambos and Xu have proved that

(4) 2 2 4

P(X;::: 1, Y ;::: 1)

= Yll ::; SII - -S21 - -SI2 - -S22

, ' m ' n ' m n '

which insists the best upper bound among all upper bounds of the form d

1

5

1 ,1

+ ^d

²

⁵

^{2 ,1}

+ ^d

³

⁵

1 ,2

+ ^d

4

5

2 ,2.

When we compare (4) with the classical lower bound (5)

51,1-51,2-52,1 ~

P((Ur:,lAi)n(uj=lBj)) = ^P(X

~

1,Y

_~ 1)

=

^Y1,1

We see that if we subtract from

51 ,1

all intersections of triples (i.e., 5

1 ,2

+ 5

2 ,1 )

we get a lower bound but if only a percentage of these triples are subtracted we get an upper bound (note that 8

2 ,2

is negative in (4)). This suggests that if, instead of 8

1,2

and 8

2 ,1 ,

we subtract a restricted number of terms ofthe form P(AiBjBk) and P(AiAjBk) we shall have an upper bound. The question is that what kind of sums of P(AiBjBk) and P(AiAjBk) will guarantee to have a universal upper bound when these sums are subtracted from 8

1 ,1.

An answer to this question is contained in Theorem 1 of the next section.

2. The Inequlities

We establish some new inequalities in which our ideas are to prove upper bounds using some of terms instead of all terms 5

1 ,2 ,

5

2 ,1

and 5

2 ,2.

Also, we prove optimal upper bounds on

Yl,l

by taking average of new ones.

THEOREM 1..

Let

i

and

j

be integers with 1

~ i ~

rn, 1

~ j ~

n.

Then (6)

Yl,1 <; SI,1 - max{'f.' t,P(A;A;+I Bj ) + ~ P(A,BjBi+.l,

f I: P(AiBjBj+l) + ~l P(AiAi+lBk)}

i=l j=l i=l

where Ak and B k are arbitrary fixed events.

Taking the averages ofthe above upper bounds overi = 1,2, ... , rn,

j

=

1,2, ... , n,

we

get theorem 2.

THEOREM

2. For positive integers m, n,

. ( 2 2 2 2 )

(7)

Yl 1 ~

mm

SI1 - -S21 - - S I2, SI 1 - -SI 2 - -S21

, , m ' m n ' , n ' mn '

This inequality

is a

new one and better than the inequality

in

Lee [1992]

in

terms of the binomial moments

SI,l, SI,2

and

S2,1 ;

that is, for integers m and n, 2

~

m; 2

~

n,

3. Proofs

Proof of Theorem 1. We use the method of indicators. Let

{

1 if X> 1 and Y > 1,

l(X

~

1, Y

~

1)

= -. -

o ^otherwIse

and by using binomial moment of (3) and indicators, the right hand side of (6) becomes

(8)

[

X y

{m-l n n-l

E

C) C) -

^max

.?:.?:

I(A;)I(A;+t>I(Bj)

+ .?:

I(Ak)I(Bj )I(Bj+l)'

.=1 3=1 3=1

f:: 1:

¹I(A;)I(Bj )I(Bj+l)

+ 1:

¹I(A;)I(A;+I)I(Bk) }].

;=1 j=1 ;=1

Then E[l(X

~

1, Y

~

1)]

=

P(X

~

1, Y

~

1), and thus in order to prove (8), it suffices to show that

(9)

I(X ~1)I(Y ~1)

~XY

^-

max{~1~I(A;)I(A;+t>I(Bj) ⁺ ~

I(Ak)I(Bj)I(Bj+1) ,

f:: E

I(A;)I(Bj)I(Bj+1)

+ 3:

¹I(A;)I(A;+1)I(Bk)}

;=1 j=1 ;=1

Note that both sides of (9) are zero if either X or Y equals zero, hence, in proving (9) we may assume that X

~

1 and Y 2:: 1 , in which the left hand side of (9) is identically one. Thus, we have to prove that (10)

U(X, Y) = the right hand side of (9)

~

1 forI

~

X

~

rn, 1

~

Y

~

n.

We distinguish three cases.

(i) First case. There are integers

X

and

Y

with X=I,

Y

=1 ; that is, there are only two events Ai and B

j

occur because the events Ai'S and B

j

's occur numercal order. Then this case is evident, having one on both sides of (10).

(ii) Second case. For integers p,q with

2 ~

p

_~

rn,

2 ~

q

_~

n , X = 1 and Y = q or X = p and Y = 1 ; that is, there are the events that exactly one Ai(B

j )

and at least two more Bjs(Ais) occur. Then

u(l,q) = 1· q - max{O,(q -1) + O} = 1 and u(p, 1) = p. 1 - max{(p -1) + 0, O} = 1.

Hence, we get (10).

(iii) Third case. For integers p,q with

2~

p

~

rn,

2~

q

~

n, X = p and Y

= q ;

that is, there are the events that at least two more AisandBjs occur. Then

u(p,q) = p. q - max{(p -l)q + (q -l),p(q -1) + (p -I)}

=

1 Hence, We get (10). This completes the proof.

Proof of Theorem 2. We turn to indicators. Hence, to prove (7) it suffices to show that

(11)

(12)

1 < XY _ X(X -1)Y _ XY(Y -1)

- rn

rnn

if

1~

X

~

rn,

1~ Y ~

nand

1

< Xy _ Xy(y -

1) _ X( X-I )Y

- n rnn

if 1

~

X

~

rn, 1

~

Y

~

n

Let

f(X, Y)

= the right hand side of

(11)

₌

XY(mn - n(X

-1) -

(Y

-1))_. Then t e unctIOnh f .

f(X Y)

, is parabola whose minimum point, for integers

mn X,Y

with

1 ::;

X ::;

m, 1::; Y ::;

^{n , are at}

{ m+1 m+1 }

C = (X, Y) = (1,1), (1, n), (m, 1), (m, n), ([-2-], 1)([-2-]+1, 1)

. m+1 8f(X,Y) m+1

where the orderedpror

(-2-' 1)

come from

ax

⁼

0

and

[-2-]

means the integer part of

m;

^{1 .} We know that

f((X, Y)

E

C) ~

¹

if

1 ::; X ::;

m,

1::; Y ::; n

which completes the proof of

(11).

Let

g(X, Y)

= the right hand side of

XY(mn - m(Y -1) - (X -1))

(12)

= .By the same way,

g((X, Y)

E

D) _~

1

if

1 ::;

X ::;m,

mn 1::; Y ::; n

where the set

n+1 n+l

D =

{(X, Y) = (1,1), (l,n), (m, 1), (m,n), (1, [-2-])' (1, [-2-]+1)}

. . n + 1 ag(X, Y) n + 1

which theorderedpmr

(1, -2-)

come from

ay

=

0

and

[-2-]

means the integer part of

n; ^{1 .}

This completes the proof of

(12).

References

1. Eva Galambos, Discussion of probabilistic inequalities by the method of A.

Renyi(Hungarian), Dissertation, L. Eotvos University, Budapest., 1965.

2. J. Galambos and M.-Y. Lee, Extensions of some univariate Bonferroni-type inequalities to multivariate setting, In Probability Theory and Applications, ed. J. Galambos and L Katai, Kluwer, Dordrecht (1992), 143-154.

3. J. Galambos and M.-Y. Lee, Further studies of Bonferroni-type inequalities, Journal of applied probability3lA (1994), 63-69.

4. J. Galambos and Y. XU, Some optimal bivariate Bonferroni-type bounds, Proc.

Amer. Math. Soc. 117 (1993), 523-528.

5. M.-Y. Lee, Bivariate Bonferroni inequalities, Aequationes Maht. 44 (1992), 220-225.

6. S. M. Kwerel, Most stringent bounds on aggregated probabilities of partially specified dependent systems, J. Amer. Stat. Assoc. 70 (1975), 472-479.

7. R. M. Meyer, Note on a multivariate form of Bonferroni's inequalities, Ann.

Math. Statist. 40 (1969),692-693.

Department of Mathematics Dankook University

Cheonan, Chungnam, Korea