Optimality conditions for Hunter’s bound. (English) Zbl 1155.60003
Summary: The bound known as D. Hunter’s bound [J. Appl. Probab. 13, 597–603 (1976; Zbl 0349.60007)] states that \(P(A_1 \cup \cdots \cup A_n)\leq \sum_{i=1}^n p_i - \sum _{\{i,j\}\in T}p_{i,j}\), where \(T\) designates the heaviest spanning tree of the graph on \(n\) nodes with edge weights \(p_{i,j}\). We prove that Hunter’s bound is optimal if and only if the input probabilities are given on a tree.
Citations:
Zbl 0349.60007References:
| [1] | Hunter, D., An upper bound for the probability of the union, J. Appl. Probab., 30, 597-603 (1975) · Zbl 0349.60007 |
| [2] | Lovász, L.; Plummer, M. D., Matching theory, Ann. Discrete Math., 29, 307 (1986) · Zbl 0618.05001 |
| [3] | A. Prékopa, B. Vizvári, G. Regös, Lower and upper bounds on probabilities of boolean functions of events, Rutcor Research Report 36-95, 1995; A. Prékopa, B. Vizvári, G. Regös, Lower and upper bounds on probabilities of boolean functions of events, Rutcor Research Report 36-95, 1995 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
