论文标题
成对独立相关差距
Pairwise independent correlation gap
论文作者
论文摘要
在本文中，我们介绍了带有随机元素的集合函数的``成对独立相关差距''的概念。成对独立的相关差距定义为设定函数的最大期望值比，在元素之间具有任意依赖性的固定边缘概率的依赖性，具有具有相同边缘概率的成对独立元素的最大期望值。我们表明，对于在$ n $元素上定义的任何非负单调的子模块集合功能，该比率在以下两种情况下由$ 4/3 $限制为$ 4/3 $：（a）所有边际概率的$ n = 3 $，以及（b）所有小边缘概率的$ n $（以及类似的大型Margical概率）。这与``相关差距''的结合有所不同，``相关差距''具有相互独立性，并展示了成对独立性和相互独立性之间的基本差异。我们通过两个示例讨论结果的含义，并以猜想结束论文。
In this paper, we introduce the notion of a ``pairwise independent correlation gap'' for set functions with random elements. The pairwise independent correlation gap is defined as the ratio of the maximum expected value of a set function with arbitrary dependence among the elements with fixed marginal probabilities to the maximum expected value with pairwise independent elements with the same marginal probabilities. We show that for any nonnegative monotone submodular set function defined on $n$ elements, this ratio is upper bounded by $4/3$ in the following two cases: (a) $n = 3$ for all marginal probabilities and (b) all $n$ for small marginal probabilities (and similarly large marginal probabilities). This differs from the bound on the ``correlation gap'' which holds with mutual independence and showcases the fundamental difference between pairwise independence and mutual independence. We discuss the implication of the results with two examples and end the paper with a conjecture.
