Documentation

of the application "bonferroni1"

 

If you use any of the applications in an academic or other type of work, please refer to the relating papers of the section References!

 

Overview

The application is the implementation of the method of Example 5.2 and 5.3 of the paper Mádi-Nagy (2009). It yields upper bound on the probability of the union of n events, using the information of the individual probabilities of the occurrences of the events, of the intersections of pairs of events etc. up to the intersections of m events. These bounds are sometimes called Bonferroni-type bounds. Usually m<<n.

 

Manual

 

1.      Download the binary file

bonferroni1.exe (Windows) or

bonferroni1 (Linux)

(Alternatively you can download and compile the C++ source file

bonferroni1.cpp)

 

2.      The binary file reads the probabilities of the (intersections of the) events from the file “prob.txt”. 

 

This file must be in the same directory where the binary file can be found. The probabilities must be listed in individual lines, in the following (subscript) order. E.g., in case of n=4, m=3:

P(A1)

P(A2)

P(A3)

P(A4)

P(A1∩A2)

P(A1∩A3)

P(A1∩A4)

P(A2∩A3)

P(A2∩A4)

P(A3∩A4)

P(A1∩A2∩A3)

P(A1∩A2∩A4)

P(A1∩A3∩A4)

P(A2∩A3∩A4)

 

One example for “prob.txt” corresponding to Case 1 of  Example 5.3 in Mádi-Nagy (2009) (n=20, m=5) can be found here: prob.txt

 

3.      Run the binary file. You will be asked about the number of events (n) and the maximum order of the intersections (m).  Then the program reads the probabilities from the file “prob.txt” and then gives an upper bound on the probabilities of the union of all the n events.

 

The program also writes the detailed results into the file “result.txt”.  The interpretation of those results can be found under the section Technical details.

 

4.      Hints for the first trials:

 

a.       Download the binary file and the prob.txt file. Run the binary file (n=20, m=5) and compare the results (even in the result.txt file) with the results of Table 3 on p. 1804 in Mádi-Nagy (2009) (click here to see the paper (.pdf)).

 

b.      Construct small examples. In this case (for small n and m), the prob.txt file can be written e.g., by hand or by a simple program.  

 

Technical details

 

The program uses the method of Example 5.2 and 5.3 of the paper Mádi-Nagy (2009) for the case of m=mj. It gives bounds for binomial multivariate discrete moment problems (MDMPs), corresponding to various lengths of the subsequences of the events. More precisely, l=m,…,IntegerPart(n/2), and for a certain value of l, the following subsequences are considered:

(A1, …, Al), (Al+1, …, A2l), …, (Akl+1, …, An), where

k=IntegerPart(n/l).

The program returns the best upper bound among them.

 

In the “result.txt” file:

·      In the first line: n is the number of events, m is the maximum order of the intersections, mj is a parameter of the corresponding MDMP, see Mádi-Nagy (2009). In our case m=mj.

·      The length of the subsequences: we bound the binomial MDMP corresponding to  (A1, …, Al), (Al+1, …, A2l), …, (Akl+1, …, An)

·      Upper bound on the probability of the union: the upper bound on the MDMP.

·      Running time: the CPU time.

·      Kjs, q1, Vks  are the optimal parameters of the Min Algorithm of Mádi-Nagy (2009).

·      The binomial moments: the right-hand side vector in the MDMP.

·      Basis subscripts: the subscript of the basic columns corresponding to the best bound.

 

The algorithm of the C++ code uses the parameters m and mj separately, so if in the input the value of mj is also asked then it is capable to solve problems, where m≠mj.

 

First, the algorithm of the C++ code generates a binomial MDMP, then it converts to a power MDMP and then it bounds the objective function value. It means, that it is enough to ask for the appropriate input, in order to bound

·         binomial MDMP, as well as

·         power MDMP.

 

The algorithm of the C++ code, also uses the method of the paper Mádi-Nagy (2005), in order to shorten the running time (in case of m≠mj).

 

References

 

Mádi-Nagy, G. (2005). A method to find the best bounds in a multivariate discrete moment problem if the basis structure is given. Studia Scientiarum Mathematicarum Hungarica, 42(2) 207-226.

click here to see the paper (.pdf)

 

Mádi-Nagy, G.  (2009). On Multivariate Discrete Moment Problems: Generalization of the Bivariate Min Algorithm for Higher Dimensions. SIAM Journal on Optimization 19(4) 1781-1806.

click here to see the paper (.pdf)