Abstract:

No abstract in the extended abstract. But here is one:

We sketch proofs of the following three results.
(1) Trotter and Winkler proved (Comb. Prob. Comput. 7 (1998), 221-238), among other results, that in each sequence A_1, ..., A_n of n events in a prob. space there are two, i < j, such that

Pr( A_i & non(A_j) ) < 1/4+O(n^{-1/2}).
We improve the error to O(n^{-2/3}).
(2)  We give an explicit formula for the quantity
min max Pr( A_{i_1} & A_{i_2} & ... & A_{i_k} ),
where the maximum is taken over all k-subsets {i_1, ..., i_k} of {1, ..., n} and the minimum over all prob. spaces and n equiprobable events A_i, Pr(A_i)=p.
(3)  In order to prove (2) we prove the inequality
s_k >= s_1.B([s_1], k-1) - (k-1).B([s_1]+1, k).
Here s_k is the sum of the probabilities Pr( A_{i_1} & A_{i_2} & ... & A_{i_k} ) taken over all k-subsets, B(. , .) is the binomial coefficient, and [.] is the integer part function. This inequality is best possible; for nonintegral s_1 it improves the well-known bound s_k >= B(s_1, k).