Documentation

of the application "unibonferroni1"

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 numerically stable dual simplex method of Prékopa (1990). It yields lower and upper bounds 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

unibonferroni1.exe (Windows) or

unibonferroni1 (Linux)

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

unibonferroni1.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(A₁)

P(A₂)

P(A₃)

P(A₄)

P(A₁∩A₂)

P(A₁∩A₃)

P(A₁∩A₄)

P(A₂∩A₃)

P(A₂∩A₄)

P(A₃∩A₄)

P(A₁∩A₂∩A₃)

P(A₁∩A₂∩A₄)

P(A₁∩A₃∩A₄)

P(A₂∩A₃∩A₄)

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 lower and 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. In order to construct other examples, the application “eventsystem1” can be used.

Technical details

The program uses the method of Prékopa (1990) using the implementation of Prékopa and Szedmák (2003). It gives sharp bounds for binomial univariate discrete moment problems (DMPs).

In the “result.txt” file:

· In the first line: n is the number of events, m is the maximum order of the intersections.

· The binomial moments: The univariate binomial moments up to the order m corresponding to the probabilities of the intersections.

· Sharp lower/upper bound on the probability of the union: the minimum/maximum value of the binomial DMP.

· Running time: the CPU time.

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

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

· binomial DMP, as well as

· power DMP.

References

Prékopa, A. (1990). The discrete moment problem and linear programming. Discrete Applied Mathematics, 27 235-254.

Prékopa, A. and S. Szedmák (2003). On the Numerical Solution of the Univariate Discrete Moment Problem. RUTCOR Research Report 32-2003.

click here to see the paper (.ps)

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)