University of Sydney, School of Mathematics and Statistics Research Report 99-17, July, 1999

MULTIVARIATE SOBEL-UPPULURI-GALAMBOS-TYPE BOUNDS

By E. SENETA and T. CHEN*

School of Mathematics and Statistics, University of Sydney, NSW 2006, Australia. and Department of Statistics, University of Pittsburgh, PA 15260, USA

SUMMARY The upper and lower bounds in a recent multivariate generalization (Galambos and

Xu, 1996) of the univariate Sobel-Uppuluri-Galambos inequalities are shown in the following to be weighted averages of individual multivariate bounds, and hence can be sharpened by optimizing over these individual bounds. Examples are used to illustrate the improvement and to illustrate the difference between bounds of this kind, and the kind of multivariate bounds appearing in Chen and Seneta (1996) and Galambos and Lee(1994). We consider only bounds for the probability of the intersection of exactly k_{i} events occurring, from the ith event group of n_{i} events, i = 1, ..., d.

Keywords: Degree of Bonferroni-type inequality, Meyer’s identity, Sobel-Uppuluri inequalities, optimization, weighted average.

1. INTRODUCTION and MAIN RESULTS Suppose A_{1}...A_{n} are arbitrary events in an arbitrary probability space (Ω, B, P) and

v_{1} be the number of events which occur at a given sample point. For any positive integers u and r, Sobel-Uppuluri bounds refer to

* Work of this author done at the University of Sydney with support of an ARC Small Grant to Professor E. Seneta.

\begin{matrix}∑_{k=0}^{2u+1}(−1)^{k}\binom{k + r}{r}S_{k+r} + \frac{2u + 2}{n − r}\binom{2u + r}{r}S_{2u+r+2} \\ ≤ P (v_{1} = r) \\ ≤ ∑_{k=0}^{2u}(−1)^{k}\binom{k + r}{r}S_{k+r} − \frac{2u + 1}{n − r}\binom{2u + r + 1}{r}S_{2u+r+1}, \end{matrix}  (1)

where

S_{i} = E(\binom{v_{1}}{i}) for 1 ≤ i ≤ n.

(See for example, Galambos 1978 or Recsei and Seneta 1987).

A bound (upper or lower) is called “a degree s bound” if max_{i∈I} i = s, where I is the index set of all S_{i} used in the bound. A higher degree bound usually provides more accurate evaluation at the cost of more complicated computation in calculating S_{i}’s, since higher dimensional joint probabilities are involved. The application of (1) is extensive; details can be found in sources such as the book by Galambos and Simonelli (1996).

In multivariate setting, d sets of events are considered, A_{ij}, i = 1, ..., n_{j} for j = 1, ..., d respectively. Let v = (v_{1}, ..., v_{d})′ and r = (r_{1}, ..., r_{d})′. Bounds extending (1) are sought for P (v = r) using

S_{k} = E(∏_{i=1}^{d} \binom{v_{i}}{k_{i}}) = E(\binom{v}{k}),

where k = (k_{1}, ..., k_{d})′ is a vector of non-negative integers.

Galambos and Lee (1994) proposed bounds extending (1) to a bivariate setting (d = 2), which were then uniformly improved by Chen and Seneta (1996) as follows, where u_{1} and u_{2} are non-negative integers:

\begin{matrix}∑_{k_{1}=0}^{2u_{1}+1} ∑_{k_{2}=0}^{2u_{2}+1}(−1)^{k_{1}+k_{2}} \binom{k_{1} + r_{1}}{r_{1}}\binom{k_{2} + r_{2}}{r_{2}}S_{k_{1}+r_{1},k_{2}+r_{2}} + Δ_{1} + Δ_{2} − Δ_{3} \\ ≤ P (v_{1} = r_{1}, v_{2} = r_{2}) \\ ≤ ∑_{k_{1}=0}^{2u_{1}} ∑_{k_{2}=0}^{2u_{2}}(−1)^{k_{1}+k_{2}} \binom{k_{1} + r_{1}}{r_{1}}\binom{k_{2} + r_{2}}{r_{2}}S_{k_{1}+r_{1},k_{2}+r_{2}} − H_{1} − H_{2} + H_{3} \end{matrix}  (2)

where

Δ_{1} = 0 for n_{1} = r_{1};

= \binom{r_{1} + 2u_{1} + 1}{r_{1}} \frac{r_{1} + 2u_{1} + 2}{n_{1} − r_{1}} ∑_{y=0}^{n_{2}−r_{2}}(−1)^{y}S_{r_{1}+2u_{1}+2,r_{2}+y}\binom{r_{2} + y}{r_{2}} for n_{1} > r_{1}.

Δ_{2} = 0 for n_{2} = r_{2};

= \binom{r_{2} + 2u_{2} + 1}{r_{2}} \frac{r_{2} + 2u_{2} + 2}{n_{2} − r_{2}} ∑_{x=0}^{n_{1}−r_{1}}(−1)^{x}S_{r_{1}+x,r_{2}+2u_{2}+2}\binom{r_{1} + x}{r_{1}} for n_{2} > r_{2}.

Δ_{3} = 0 for n_{1} = r_{1} or n_{2} = r_{2};

= \binom{r_{1} + 2u_{1} + 1}{r_{1}}\binom{r_{2} + 2u_{2} + 1}{r_{2}} \frac{r_{1} + 2u_{1} + 2}{2u_{1} + 2} \frac{r_{2} + 2u_{2} + 2}{2u_{2} + 2}S_{r_{1}+2u_{1}+2,r_{2}+2u_{2}+2}

for n_{1} > r_{1} and n_{2} > r_{2}.

H_{1} = 0 for n_{1} = r_{1};

= \binom{r_{1} + 2u_{1}}{r_{1}} \frac{r_{1} + 2u_{1} + 1}{n_{1} − r_{1}} ∑_{y=0}^{2u_{2}}(−1)^{y}S_{r_{1}+2u_{1}+1,r_{2}+y}\binom{2u_{2} + y}{2u_{2}} for n_{1} > r_{1}.

H_{2} = 0 for n_{2} = r_{2};

= \binom{r_{2} + 2u_{2}}{r_{2}} \frac{r_{2} + 2u_{2} + 1}{n_{2} − r_{2}} ∑_{x=0}^{2u_{1}}(−1)^{x}S_{r_{1}+x,r_{2}+2u_{2}+1}\binom{2u_{1} + x}{2u_{1}} for n_{2} > r_{2}.

H_{3} = 0 for n_{1} = r_{1} or n_{2} = r_{2};

= \binom{r_{1} + 2u_{1}}{r_{1}}\binom{r_{2} + 2u_{2}}{r_{2}} \frac{r_{1} + 2u_{1} + 1}{n_{1} − r_{1}} \frac{r_{2} + 2u_{2} + 1}{n_{2} − r_{2}}S_{r_{1}+2u_{1}+1,r_{2}+2u_{2}+1}

for n_{1} > r_{1} and n_{2} > r_{2}. The nature of this extension is to use the quantity

∑_{i=0}^{a} ∑_{j=0}^{b}(−1)^{i+j}\binom{i + r_{1}}{r_{1}}\binom{j + r_{2}}{r_{2}}S_{i+r_{1},j+r_{2}}

as the generic term for inclusion and exclusion, with upper bounds (lower bounds) being obtained by setting a and b both odd (even), and then to bound the difference from P (v_{1} = r_{1}, v_{2} = r_{2}). The central idea is the application of Meyer’s identity

\begin{aligned}S_{kt} & = E(\binom{v_{1}}{k}\binom{v_{2}}{t}) \\ & = ∑_{i=k}^{n_{1}} ∑_{j=t}^{n_{2}} \binom{v_{1}}{k}\binom{v_{2}}{t}P (v_{1} = i, v_{2} = j), \end{aligned}

in conjunction with lemmas on combinatorial coefficients via the method of indicators. This direction of generalization in theory separately involves all the degrees for event sets {A_{11}, ..., A_{n_{1}1}} and {A_{12}, ..., A_{n_{2}2}} from 0 to a + r_{1} and 0 to b + r_{2} respectively.

This involvement of individual bivariate degrees differs from that in multivariate inequalities where degree p is that figuring in the quantity

d_{p} = ∑_{|k|=p} \binom{k}{r}S_{k},

with |k| = ∑_{i=1}^{d} k_{i}, k = (k_{1}, ..., k_{d})′ and

\binom{k}{r} = ∏_{i=1}^{d} \binom{k_{i}}{r_{i}}, S_{k} = S_{k_{1},...,k_{d}},

in the sense that p-dimensional joint probabilities are calculated. For example, the multivariate identity stated in Meyer (1969) reads

P (v = r) = ∑_{i=|r|}^{|n|}(−1)^{i} ∑_{|k|=i} \binom{k}{r}S_{k}  (3)

and its inverse form

S_{k} = ∑_{p=|k|}^{|n|} ∑_{|s|=p} \binom{s}{k}P (v = s)  (4)

and so (3) is of degree |n|. Thus, bounds generalizing (1) by using multivariate degree p quantities d_{p} is a perhaps more natural way of extension, although each direction of generalization has its own advantage under different circumstances. We shall illustrate by constructing numerical examples in Section 3.

The manner of generalizing univariate inequalities using d_{p}’s first appeared in Meyer (1969) where univariate Bonferroni bounds were extended to multivariate. Recently Galambos and Xu (1996) put forward, by using the method of polynomials, the bounds:

∑_{i=0}^{2t+1}(−1)^{i} ∑_{|k|=i} \binom{k + r}{r}S_{k+r} + \frac{2t + 2}{|n| − |r|} ∑_{|k|=2t} \binom{k + r}{r}S_{k+r}

≤ P (v = r)

≤ ∑_{i=0}^{2t}(−1)^{i} ∑_{|k|=i} \binom{k + r}{r}S_{k+r} − \frac{2t + 1}{|n| − |r|} ∑_{|k|=2t+1} \binom{k + r}{r}S_{k+r},

(5) aiming at extension of univariate Sobel-Uppuluri-Galambos bounds. They assert that their result is analogous to the way Galambos (1978) extended Bonferroni’s classical univariate bounds; but that univariate extension in fact did not come from the method of polynomials. The dissonance between the method used by Galambos and Xu (1996) and the result achieved prompted our investigation, and we obtained by extending Galambos’(1978) original methodology, the following two theorems:

Theorem 1: For any integer t ≥ 0 with 2t + 1 ≤ |n| − |r|,

∑_{i=0}^{2t+1}(−1)^{i} ∑_{|k|=i} \binom{k + r}{r}S_{k+r} + max_{i} A_{i}(2t + 1)

≤ P (v = r)

≤ ∑_{i=0}^{2t}(−1)^{i} ∑_{|k|=i} \binom{k + r}{r}S_{k+r} − max_{i} A_{i}(2t),

(6)

where

A_{i}(x) = ∑_{|k|=x} S_{k_{1}+r_{1},...,k_{i}+r_{i}+1...k_{d}+r_{d}} \binom{k_{1} + r_{1}}{r_{1}}...\binom{k_{i} + r_{i} + 1}{r_{i}}...\binom{k_{d} + r_{d}}{r_{d}} \frac{k_{i} + 1}{n_{i} − r_{i}} ,

i = 1, ..., d. Note that A_{i}(x) has degree |r| + x + 1. # Theorem 2: Inequality (5) can be written

∑_{i=0}^{2t+1}(−1)^{i} ∑_{|k|=i} \binom{k + r}{r}S_{k+r} + ∑_{i=1}^{d} \frac{n_{i} − r_{i}}{|n| − |r|}A_{i}(2t + 1)

≤ P (v = r)

≤ ∑_{i=0}^{2t}(−1)^{i} ∑_{|k|=i} \binom{k + r}{r}S_{k+r} − ∑_{i=1}^{d} \frac{n_{i} − r_{i}}{|n| − |r|}A_{i}(2t),

so (6) is sharper than (5). #

Remark: Theorem 2 shows that Galambos and Xu’s (1996) Theorem 1 can be improved uniformly. The nature of improvement, from averaging to optimization, is similar in sense to the way in which Hunter’s Inequality improves certain univariate inequalities (Seneta, 1988).

2. PROOF OF THEOREMS

Lemma 1. For any integer T ≥ 0 and non-negative integers x_{1}, ..., x_{d},

∑_{i=0}^{T} ∑_{|k|=i}(−1)^{i}\binom{x_{1}}{k_{1}}...\binom{x_{d}}{k_{d}} = (−1)^{T} ∑_{|k|=T} \binom{x_{1} − 1}{k_{1}}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}}.  (7)

Since all (x_{i}, k_{i}), i = 1, ..., d are interchangeable on the left, the right hand side can be rewritten in d ways. Proof of Lemma 1: We use proof by induction.

When T = 0, left=1=right.

When T = 1, the left becomes 1 − x_{1} − x_{2} − ... − x_{d} while the right equals (−1)(x_{1} − 1 + x_{2} + ... + x_{d}) which is the same as the left.

Supposing that (5) is true for any integer T ≥ 0, in the case of T + 1 we have

∑_{i=0}^{T +1} ∑_{|k|=i}(−1)^{i}\binom{x_{1}}{k_{1}}...\binom{x_{d}}{k_{d}}

= ∑_{i=0}^{T} ∑_{|k|=i}(−1)^{i}\binom{x_{1}}{k_{1}}...\binom{x_{d}}{k_{d}} + (−1)^{T +1} ∑_{|k|=T +1} \binom{x_{1}}{k_{1}}...\binom{x_{d}}{k_{d}}

= (−1)^{T} ∑_{|k|=T} \binom{x_{1} − 1}{k_{1}}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}} + (−1)^{T +1} ∑_{|k|=T +1} \binom{x_{1}}{k_{1}}...\binom{x_{d}}{k_{d}}

= (−1)^{T +1}\{− ∑_{|k|=T} \binom{x_{1} − 1}{k_{1}}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}} + ∑_{|k|=T +1} \binom{x_{1}}{k_{1}}...\binom{x_{d}}{k_{d}}\}

= (−1)^{T +1}\{ ∑_{|k|=T} \binom{x_{1}}{k_{1} + 1}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}} − ∑_{|k|=T} \binom{x_{1} − 1}{k_{1}}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}}

+ ∑_{|k|=T +1} \binom{x_{1}}{0}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}}\}

= (−1)^{T +1}\{ ∑_{|k|=T} \binom{x_{1} − 1}{k_{1} + 1}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}} + ∑_{|k|=T +1} \binom{x_{1}}{0}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}}\},

by putting the first two summations together and using

\binom{x_{1}}{k_{1} + 1} − \binom{x_{1} − 1}{k_{1}} = \binom{x_{1} − 1}{k_{1} + 1}.

Thus

∑_{i=0}^{T +1} ∑_{|k|=i}(−1)^{i}\binom{x_{1}}{k_{1}}...\binom{x_{d}}{k_{d}} = (−1)^{T +1} ∑_{|k|=T +1} \binom{x_{1} − 1}{k_{1}}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}},

since

\begin{aligned}∑_{|k|=T} \binom{x_{1} − 1}{k_{1} + 1}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}}+ & ∑_{|k|=T +1} \binom{x_{1}}{0}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}} \\ & = ∑_{|k|=T +1} \binom{x_{1} − 1}{k_{1}}\binom{x_{2}}{k_{2}}...\binom{x_{d}}{k_{d}}. # \end{aligned}

Proof of Theorem 1: Let a be any non-negative integer and write P (s) = P (v = s) = P (v_{1} = s_{1}, ..., v_{d} = s_{d}). Then

∑_{i=0}^{a}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r}

= ∑_{i=0}^{a}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k} ∑_{p=i+|r|}^{|n|} ∑_{|s|=p} \binom{s}{k + r}P (s),

by (4), noting that |k| = i. Thus

∑_{i=0}^{a}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r} = ∑_{p=|r|}^{|n|} ∑_{|s|=p} P (s) ∑_{i=0}^{J} ∑_{|k|=i}(−1)^{i}\binom{k + r}{r}\binom{s}{k + r} where J = min(a, |n| − |r|) = ∑_{p=|r|}^{|n|} ∑_{|s|=p} P (s)\binom{s}{r} ∑_{i=0}^{J} ∑_{|k|=i}(−1)^{i}\binom{s − r}{k}, .

This is because

\binom{k + r}{r}\binom{s}{k + r} = \binom{s}{r}\binom{s − r}{k},  (8)

so

∑_{i=0}^{a}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r} = P (r) + ∑_{p=|r|+1}^{|n|} ∑_{|s|=p} P (s)\binom{s}{r} ∑_{i=0}^{J} ∑_{|k|=i}(−1)^{i}\binom{s − r}{k} = P (r) + ∑_{p=|r|+1}^{|n|} ∑_{|s|=p} P (s)\binom{s}{r}(−1)^{J} ∑_{|k|=J} \binom{s_{1} − r_{1} − 1}{k_{1}}\binom{s_{2} − r_{2}}{k_{2}}...\binom{s_{d} − r_{d}}{k_{d}} ,

by Lemma 1. Then

∑_{i=0}^{a}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r}

= P (r) + ∑_{p=|r|+1}^{|n|} ∑_{|s|=p} P (s)\binom{s}{r}(−1)^{a} ∑_{|k|=a} \binom{s_{1} − r_{1} − 1}{k_{1}}\binom{s_{2} − r_{2}}{k_{2}}...\binom{s_{d} − r_{d}}{k_{d}}

for a ≤ |n| − |r|;

= P (r) + (−1)^{a} ∑_{|k|=a} ∑_{p=|r|+1}^{|n|} ∑_{|s|=p} P (s)\binom{s}{r}\binom{s_{1} − r_{1} − 1}{k_{1}}\binom{s_{2} − r_{2}}{k_{2}}...\binom{s_{d} − r_{d}}{k_{d}}.

Thus we have

∑_{i=0}^{a}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r} = P (r) + (−1)^{a}B_{1}(a),  (9)

where

B_{1}(a) = ∑_{|k|=a} ∑_{p=|r|+a+1}^{|n|} ∑_{|s|=p} P (s)\binom{s}{r}\binom{s_{1} − r_{1} − 1}{k_{1}}\binom{s_{2} − r_{2}}{k_{2}}...\binom{s_{d} − r_{d}}{k_{d}},

since only when p ≥ |r| + a + 1 can we obtain

\binom{s_{1} − r_{1} − 1}{k_{1}}\binom{s_{2} − r_{2}}{k_{2}}...\binom{s_{d} − r_{d}}{k_{d}} ≠ 0.

With (9), we are ready to prove Theorem 1. To show the upper bounds of the theorem, we set a = 2t, which makes (9) become

∑_{i=0}^{2t}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r} = P (r) + B_{1}(2t).

We shall first show A_{1}(2t) ≤ B_{1}(2t), which can be seen by recalling that

A_{1}(2t) = ∑_{|k|=2t} S_{k_{1}+r_{1}+1,k_{2}+r_{2},...,k_{d}+r_{d}} \binom{k_{1} + r_{1} + 1}{r_{1}}\binom{k_{2} + r_{2}}{r_{2}}...\binom{k_{d} + r_{d}}{r_{d}} \frac{k_{1} + 1}{n_{1} − r_{1}}

= ∑_{|k|=2t} ∑_{p=|k|+|r|+1}^{|n|} ∑_{|s|=p} P (s)\binom{s_{1}}{k_{1} + r_{1} + 1}\binom{s_{2}}{k_{2} + r_{2}}...\binom{s_{d}}{k_{d} + r_{d}}

\binom{k_{1} + r_{1} + 1}{r_{1}}\binom{k_{2} + r_{2}}{r_{2}}...\binom{k_{d} + r_{d}}{r_{d}} \frac{k_{1} + 1}{n_{1} − r_{1}} .

This is because by (4)

S_{k_{1}+r_{1}+1,k_{2}+r_{2},...,k_{d}+r_{d}} = ∑_{p=|k|+|r|+1}^{|n|} ∑_{|s|=p} P (s)\binom{s_{1}}{k_{1} + r_{1} + 1}\binom{s_{2}}{k_{2} + r_{2}}...\binom{s_{d}}{k_{d} + r_{d}}.

On the other hand,

B_{1}(2t) = ∑_{|k|=2t} ∑_{p=|r|+2t+1}^{|n|} ∑_{|s|=p} P (s)\binom{s_{1}}{r_{1}}...\binom{s_{d}}{r_{d}}\binom{s_{1} − r_{1} − 1}{k_{1}}\binom{s_{2} − r_{2}}{k_{2}}...\binom{s_{d} − r_{d}}{k_{d}}.

Comparing

\binom{s_{1}}{k_{1} + r_{1} + 1}\binom{k_{1} + r_{1} + 1}{r_{1}} vs \binom{s_{1}}{r_{1}}\binom{s_{1} − r_{1} − 1}{k_{1}} \frac{n_{1} − r_{1}}{k_{1} + 1}

we find by expanding the left-hand expression that

\binom{s_{1}}{k_{1} + r_{1} + 1}\binom{k_{1} + r_{1} + 1}{r_{1}} ≤ \frac{n_{1} − r_{1}}{k_{1} + 1} \binom{s_{1}}{r_{1}}\binom{s_{1} − r_{1} − 1}{k_{1}}.  (10)

Further, as in (8):

\binom{s_{i}}{k_{i} + r_{i}}\binom{k_{i} + r_{i}}{r_{i}} = \binom{s_{i}}{r_{i}}\binom{s_{i} − r_{i}}{k_{i}} for i = 2, ..., d.  (11)

Thus, for each P (s) in A_{1}(2t) and B_{1}(2t), we can compare pairs of associated coefficients in A_{1}(2t) and B_{1}(2t) individually, by (10) and (11), and the immediate conclusion is that A_{1}(2t) ≤ B_{1}(2t). Noting that x_{1} can be replaced by any one of x_{2}, ..., x_{d} establishes the upper bounds in Theorem 1, for 2t ≤ |n| − |r|.

Taking a = 2t + 1 in (9) yields

∑_{i=0}^{2t+1}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r} = P (r) − B_{1}(2t + 1).

To establish the lower bounds we need first to show

∑_{i=0}^{2t+1}(−1)^{i} ∑_{|k|=i} \binom{k + r}{k}S_{k+r} ≤ P (r) − A_{1}(2t + 1).

This can be achieved if A_{1}(2t + 1) ≤ B_{1}(2t + 1), which follows from applying (10) and (11) to the comparison between A_{1}(2t + 1) and B_{1}(2t + 1) term by pairwise term. Considering the fact that x_{1} can be replaced by any one of x_{2}, ..., x_{d} completes the proof of Theorem 1. #

The following well-known result is necessary to establish Theorem 2. Lemma 2. For positive numbers a_{1}, ..., a_{n} with positive weights c_{1}, ..., c_{n} respectively, such that ∑_{i=1}^{n} c_{i} = 1,

max_{1≤i≤n} a_{i} ≤ c_{1}a_{1} + ... + c_{n}a_{n},

and equality can be attained only when a_{i}=constant for all i = 1, ..., n. Proof of Theorem 2. For notational convenience, we state the proof of Theorem 2 in the bivariate setting. The proof for the multivariate setting follows analogously.

In the bivariate case, Theorem 1 yields

∑_{i=0}^{2t+1}(−1)^{i} ∑_{k_{1}+k_{2}=i} \binom{k + r}{r}S_{k+r} + A_{1}(2t + 1)

≤ P (v = r)

≤ ∑_{i=0}^{2t}(−1)^{i} ∑_{k_{1}+k_{2}=i} \binom{k + r}{r}S_{k+r} − A_{1}(2t)

(12)

and

∑_{i=0}^{2t+1}(−1)^{i} ∑_{k_{1}+k_{2}=i} \binom{k + r}{r}S_{k+r} + A_{2}(2t + 1)

≤ P (v = r)

≤ ∑_{i=0}^{2t}(−1)^{i} ∑_{k_{1}+k_{2}=i} \binom{k + r}{r}S_{k+r} − A_{2}(2t)

(13)

where

A_{1}(2t) = ∑_{k_{1}+k_{2}=2t} S_{k_{1}+r_{1}+1,k_{2}+r_{2}} \binom{k_{1} + r_{1} + 1}{r_{1}}\binom{k_{2} + r_{2}}{r_{2}} \frac{k_{1} + 1}{n_{1} − r_{1}}

and

A_{2}(2t) = ∑_{k_{1}+k_{2}=2t} S_{k_{1}+r_{1},k_{2}+r_{2}+1}\binom{k_{1} + r_{1}}{r_{1}}\binom{k_{2} + r_{2} + 1}{r_{2}} \frac{k_{2} + 1}{n_{2} − r_{2}} .

Multiplying (12) by \frac{n_{1}−r_{1}}{|n|−|r|}, (13) by \frac{n_{2}−r_{2}}{|n|−|r|} respectively and adding them yields

∑_{i=0}^{2t+1}(−1)^{i} ∑_{k_{1}+k_{2}=i} \binom{k + r}{r}S_{k+r} + A_{1}(2t + 1)\frac{n_{1} − r_{1}}{|n| − |r|} + A_{2}(2t + 1)\frac{n_{2} − r_{2}}{|n| − |r|}

≤ P (v = r)

≤ ∑_{i=0}^{2t}(−1)^{i} ∑_{k_{1}+k_{2}=i} \binom{k + r}{r}S_{k+r} − A_{1}(2t)\frac{n_{1} − r_{1}}{|n| − |r|} − A_{2}(2t)\frac{n_{2} − r_{2}}{|n| − |r|.}

(14)

Comparing (14) with (5), if we prove

A_{1}(2t)\frac{n_{1} − r_{1}}{|n| − |r|} + A_{2}(2t)\frac{n_{2} − r_{2}}{|n| − |r|} = \frac{2t + 1}{|n| − |r|} ∑_{|k|=2t+1} \binom{k + r}{r}S_{k+r},  (15)

we can then claim that the upper bound given in (5) is a weighted average of d upper bounds in Theorem 1, by Lemma 2, we can have the upper bounds of Theorem 2. The proof for the sharperness of lower bounds in Theorem 2 follows similarily, thus the key here is to prove equation (15). To see (15), note that

A_{1}(2t)\frac{n_{1} − r_{1}}{|n| − |r|} + A_{2}(2t)\frac{n_{2} − r_{2}}{|n| − |r|}

= ∑_{k_{1}+k_{2}=2t} S_{k_{1}+r_{1}+1,k_{2}+r_{2}} \binom{k_{1} + r_{1} + 1}{r_{1}}\binom{k_{2} + r_{2}}{r_{2}} \frac{k_{1} + 1}{|n| − |r|}+

∑_{k_{1}+k_{2}=2t} S_{k_{1}+r_{1},k_{2}+r_{2}+1}\binom{k_{1} + r_{1}}{r_{1}}\binom{k_{2} + r_{2} + 1}{r_{2}} \frac{k_{2} + 1}{|n| − |r|}

= ∑_{k_{1}=0}^{2t−1} S_{k_{1}+r_{1}+1,2t−k_{1}+r_{2}} \binom{k_{1} + r_{1} + 1}{r_{1}}\binom{2t − k_{1} + r_{2}}{r_{2}} \frac{k_{1} + 1}{|n| − |r|}+

S_{r_{1}+2t+1,r_{2}} \binom{2t + r_{1} + 1}{r_{1}} \frac{2t + 1}{|n| − |r|} + S_{r_{1},2t+r_{2}+1}\binom{2t + r_{2} + 1}{r_{2}} \frac{2t + 1}{|n| − |r|}+

∑_{k_{1}=1}^{2t} S_{k_{1}+r_{1},2t−k_{1}+r_{2}+1}\binom{k_{1} + r_{1}}{r_{1}}\binom{2t − k_{1} + r_{2} + 1}{r_{2}} \frac{2t − k_{1} + 1}{|n| − |r|}.

Setting k_{1} + 1 = j in the first summation yields

A_{1}(2t)\frac{n_{1} − r_{1}}{|n| − |r|} + A_{2}(2t)\frac{n_{2} − r_{2}}{|n| − |r|}

= ∑_{j=1}^{2t} S_{j+r_{1},2t−j+r_{2}+1}\binom{j + r_{1}}{r_{1}}\binom{2t − j + r_{2} + 1}{r_{2}} \frac{j}{|n| − |r|}+

S_{r_{1}+2t+1,r_{2}} \binom{2t + r_{1} + 1}{r_{1}} \frac{2t + 1}{|n| − |r|} + S_{r_{1},2t+r_{2}+1}\binom{2t + r_{2} + 1}{r_{2}} \frac{2t + 1}{|n| − |r|}+

∑_{k_{1}=1}^{2t} S_{k_{1}+r_{1},2t−k_{1}+r_{2}+1}\binom{k_{1} + r_{1}}{r_{1}}\binom{2t − k_{1} + r_{2} + 1}{r_{2}} \frac{2t − k_{1} + 1}{|n| − |r|}

= S_{r_{1}+2t+1,r_{2}} \binom{2t + r_{1} + 1}{r_{1}} \frac{2t + 1}{|n| − |r|} + S_{r_{1},2t+r_{2}+1}\binom{2t + r_{2} + 1}{r_{2}} \frac{2t + 1}{|n| − |r|}+

∑_{k_{1}=1}^{2t} S_{k_{1}+r_{1},2t−k_{1}+r_{2}+1}\binom{k_{1} + r_{1}}{r_{1}}\binom{2t − k_{1} + r_{2} + 1}{r_{2}} \frac{2t + 1}{|n| − |r|}

= \frac{2t + 1}{|n| − |r|} ∑_{|k|=2t+1} \binom{k + r}{r}S_{k+r}. #

3. NUMERICAL EXAMPLES In this section, we shall present two examples. Example 1 shows that in some cases (5)

does not give a useful result while (6) can still be very effective. Example 2, in conjunction with Example 1, clarifies the relationship between the two directions of generalization as mentioned in Section 1. We see from the examples that in some cases, bounds (2) based on the direction of Galambos and Lee (1994) and then Chen and Seneta (1996) work better, while in some other cases, the bounds from (6) are sharper. EXAMPLE 1. Consider A_{1}, A_{2}, A_{3}, A_{4} and B_{1}, B_{2}, B_{3}, B_{4} with non-zero probabilities of elementary conjunctions assigned as follows

P (A_{1}A_{2}A_{3}^{c}A_{4}B_{1}^{c}B_{2}^{c}B_{3}^{c}B_{4}) = 0.18 P (A_{1}A_{2}A_{3}A_{4}^{c}B_{1}^{c}B_{2}B_{3}^{c}B_{4}^{c}) = 0.12
P (A_{1}A_{2}A_{3}A_{4}B_{1}B_{2}B_{3}B_{4}^{c}) = 0.31 P (A_{1}A_{2}A_{3}A_{4}B_{1}B_{2}^{c}B_{3}B_{4}) = 0.19
P (A_{1}A_{2}A_{3}A_{4}^{c}B_{1}B_{2}B_{3}B_{4}) = 0.01 P (A_{1}^{c}A_{2}^{c}A_{3}^{c}A_{4}^{c}B_{1}^{c}B_{2}^{c}B_{3}^{c}B_{4}^{c}) = 0.19

Hence we have the corresponding non-zero probabilities of the number of exactly A′s and B′s which occur as

P (v_{A} = 3, v_{B} = 1) = 0.3 P (v_{A} = 3, v_{B} = 4) = 0.01
P (v_{A} = 4, v_{B} = 3) = 0.50 P (v_{A} = 0, v_{B} = 0) = 0.19

and then the associated Bonferroni summations

S_{31} = 6.34 S_{32} = 6.06 S_{33} = 2.04 S_{34} = 0.01
S_{41} = 1.5 S_{42} = 1.5 S_{43} = 0.5 S_{44} = 0. #

EXAMPLE 2. Consider A_{1}, A_{2}, A_{3}, A_{4} and B_{1}, B_{2}, B_{3}, B_{4} with non-zero probabilities of elementary conjunctions specified as follows

P (A_{1}A_{2}A_{3}A_{4}^{c}B_{1}B_{2}B_{3}^{c}B_{4}^{c}) = 0.1 P (A_{1}^{c}A_{2}A_{3}A_{4}B_{1}^{c}B_{2}^{c}B_{3}B_{4}) = 0.1
P (A_{1}A_{2}^{c}A_{3}A_{4}B_{1}^{c}B_{2}B_{3}B_{4}^{c}) = 0.1 P (A_{1}A_{2}A_{3}^{c}A_{4}B_{1}B_{2}B_{3}^{c}B_{4}^{c}) = 0.1
P (A_{1}A_{2}A_{3}^{c}A_{4}B_{1}B_{2}^{c}B_{3}^{c}B_{4}^{c}) = 0.2 P (A_{1}^{c}A_{2}^{c}A_{3}^{c}A_{4}^{c}B_{1}^{c}B_{2}^{c}B_{3}^{c}B_{4}^{c}) = 0.1
P (A_{1}A_{2}A_{3}A_{4}^{c}B_{1}^{c}B_{2}^{c}B_{3}^{c}B_{4}) = 0.3

Such an assignment gives the corresponding non-zero probabilities of the number of exactly A′s and B′s which occur as

P (v_{A} = 3, v_{B} = 2) = 0.4 P (v_{A} = 3, v_{B} = 1) = 0.5 P (v_{A} = 0, v_{B} = 0) = 0.1,

and then corresponding Bonferroni summations can be calculated as

S_{31} = 1.3 S_{32} = 0.4 S_{33} = 0 S_{34} = 0
S_{41} = 0 S_{42} = 0 S_{43} = 0 S_{44} = 0. #

We first compare the upper bounds in (5) and (6).

In Example 1, d = 2, n_{1} = n_{2} = 4 and setting r_{1} = 3, r_{2} = 1 and t = 1 in Theorem 1 yields as the upper bounds entering into (6), using A_{i}(.) at each of i = 1 and 2 respectively:

P (v_{A} = 3, v_{B} = 1) ≤ S_{31} − (2S_{32} + 4S_{41}) + (3S_{33} + 8S_{42}) − 12S_{43} = 0.34

and

P (v_{A} = 3, v_{B} = 1) ≤ S_{31} − (2S_{32} + 4S_{41}) + (3S_{33} + 8S_{42}) − (4S_{34} + 8S_{43}) = 2.3.

Thus, the upper bound from Theorem 1 reads

P (v_{A} = 3, v_{B} = 1) ≤ min(0.34, 2.3) = 0.34

while the upper bound of (5) reads

P (v_{A} = 3, v_{B} = 1) ≤ S_{31} − (2S_{32} + 4S_{41}) + (3S_{33} + 8S_{42}) − (3S_{34} + 9S_{43}) = 1.81.

Thus (5) gives a trivial upper bound (greater than 1). The actual value is P (v_{A} = 3, v_{B} = 1) = 0.30. (15) in this example reads:

0.34 × \frac{4 − 3}{4 + 4 − 3 − 1} + 2.3 × \frac{4 − 1}{4 + 4 − 3 − 1} = 1.81.

Both (5) and (6) give the lower bound 0.3 #

Next we shall use Example 1 to show that (2) can be sharper than (6), and then use Example 2 to show that (6) can be sharper than (2).

In Example 1, we know that (6) gives a upper bound of 0.34 which is very effective in estimating the exact value of 0.3. However, (2) does even better. Letting u_{1} = 1, u_{2} = 0, n_{1} = n_{2} = 4, r_{1} = 3, r_{2} = 1 the upper bound in (2) yields

\begin{aligned}P (v_{A} = 3, v_{B} = 1) & ≤ ∑_{k=0}^{2} ∑_{t=0}^{0}(−1)^{k+t}\binom{k + 3}{3}\binom{t + 1}{1}S_{k+3,t+1} − H_{2} \\ & ≤ S_{31} − 4S_{41} − \frac{2}{3}(S_{32} − 4S_{42}). \end{aligned}

Applying the values of S_{ij}’s in Example 1 yields

P (v_{A} = 3, v_{B} = 1) ≤ 0.3

which exactly hits the value to be evaluated. However, the upper bound in (2) is not always better than (6) as demonsrated by Example 2, where (2) gives the bound

P (v_{A} = 3, v_{B} = 1) ≤ 1.3 − \frac{2}{3} × 0.4 = 1.03

which is a trivial upper bound. On the other hand, (6) provides an upper bound

P (v_{A} = 3, v_{B} = 1) ≤ 1.3 − (2 × 0.4 + 4 × 0) = 0.5

which is the exact value to be estimated. Both (2) and (6) give the lower bound 0.5. #

References

[1] Chen T. and Seneta E. (1996) Multivariate Bonferroni-type lower bounds. Journal of Applied Probability 33 729-740.

[2] Galambos J. (1978) The Asymptotic Theory of Extreme Order Statistics. New York: Wiley.

[3] Galambos J. and Lee M.-Y. (1994) Further studies of bivariate Bonferroni-type inequalities. Journal of Applied Probability 31A, 63-69.

[4] Galambos J. and Simonelli I. (1996) Bonferroni-type Inequalities with Applications. Springer, New York.

[5] Galambos J. and Xu Y. (1995) Two sets of multivariate Bonferroni-type inequalities. Statistical Theory and Applications. ( H. N. Nagaraja et al. eds.) Heidelberg: Springer-Verlag, pp.29-36,

[6] Hoppe, F.M.(1993) Beyond inclusion-and exclusion: Natural identities for P[exactly t events] and P[at least t events] and resulting inequalities. International Statistical Review, 61 435-446 [7] Meyer R. M.(1969) Note on a ‘multivariate’ form of Bonferroni’s inequalities.Ann.

Math. Statist., 40, 692-693

[8] Recsei,E. and E.Seneta (1987) Bonferroni-type inequalities.Adv. Appl. Prob., 19, 508-511.

[9] Seneta E. (1988) Degree, iteration and permutation in improving Bonferroni-type bounds. Australian Journal of Statistics, 30A, 27-38.

[10] Sobel. M and Uppuluri, V.R.R. (1972) On Bonferroni-type inequalities of the same degree for the probability of unions and intersections. Ann. Math. Statist., 43, 1549-1558.

This research report is electronically accessible: http://siv:8000/res/Statistics/tr.html