论文标题
与成对独立性的紧密概率边界
Tight Probability Bounds with Pairwise Independence
论文作者
论文摘要
尽管文献中提出了至少一个整数$ k $的$ n $成对独立伯努利随机变量的有用概率范围，但总体而言，这些范围都不紧张。在本文中，我们在这个方向上提供了几个结果。首先，当$ k = 1 $时，对于任何输入边缘概率向量向量$ \ mathbf {p} \ in [0,1]^n $，以$ n $成对独立事件的结合概率的最紧密的上限提供。为了证明结果，我们显示了与转化的双变量概率的正相关的伯努利随机载体的存在，这是独立的。在此基础上，我们表明，Boole Union绑定的比率和紧密的成对独立界限的上限为$ 4/3 $，并且达到了比率。讨论了该结果在相关差距分析和分布稳健瓶颈优化中的应用。将结果扩展以找到$ n $成对独立事件的交点的最紧密的下限。其次，对于任何$ k \ geq 2 $和输入边缘概率向量$ \ mathbf {p} \ in [0,1]^n $，通过利用概率的排序来得出新的上限。提供了数值示例，以说明何时对现有界限进行改进。最后，我们确定了当现有和新界限紧密的情况下，例如具有相同的边缘概率。
While useful probability bounds for $n$ pairwise independent Bernoulli random variables adding up to at least an integer $k$ have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results in this direction. Firstly, when $k = 1$, the tightest upper bound on the probability of the union of $n$ pairwise independent events is provided in closed-form for any input marginal probability vector $\mathbf{p} \in [0,1]^n$. To prove the result, we show the existence of a positively correlated Bernoulli random vector with transformed bivariate probabilities, which is of independent interest. Building on this, we show that the ratio of the Boole union bound and the tight pairwise independent bound is upper bounded by $4/3$ and that the ratio is attained. Applications of the result in correlation gap analysis and distributionally robust bottleneck optimization are discussed. The result is extended to find the tightest lower bound on the probability of the intersection of $n$ pairwise independent events. Secondly, for any $k \geq 2$ and input marginal probability vector $\mathbf{p} \in [0,1]^n$, new upper bounds are derived by exploiting ordering of probabilities. Numerical examples are provided to illustrate when the bounds provide improvement over existing bounds. Lastly, we identify specific instances when the existing and the new bounds are tight, for example, with identical marginal probabilities.
