Negative Association-Definition , Properties , and Applications
Negative Association-Definition , Properties , and Applications
复制标题
负关联-定义、性质和应用
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
David Wajc
中科院分区：
文献类型：
--
作者：
David Wajc
在这些笔记中，我们介绍了负关联的概念，讨论了它的一些有用的属性，并以一些示例应用程序结束。这里要牢记的口号是“独立，或者更好”。 1 负关联定义 在随机算法中，我们的随机性通常采取独立随机变量的形式，使我们能够应用有关这些变量的强大定理，一个突出的例子是 Chernoff-Hoeffding 界限。然而，我们不能总是期望我们观察到的（或在算法运行期间生成的）随机变量是独立的。尽管如此，这些变量可能满足某种形式的负相关性，在这种情况下，有用的独立属性可能会继续存在。本次演讲的重点是消极依赖的一个概念，即消极关联。直觉 考虑一组随机变量 X1, X2,...。 。 。 , Xn，满足以下条件：如果这些变量的子集 S 为“高”，则不相交子集 T 必定为“低”。该属性可以形式化如下。定义 1（负关联 [10, 8]）。一组随机变量 X1, X2,... 。 。 , 如果对于任意两个不相交索引集 I, J ⊆ [n] 和两个函数 f, g 均为单调递增或均为单调递减，则称 Xn 负相关 (NA)，则 E[f(Xi : i ∈ I) · g(Xj : j ∈ J)] ≤ E[f(Xi : i ∈ I)] · E[g(Xj : j ∈ J)] 成立。为了简化后面的表示，我们将把单调函数 f 和 g 以及不相交子集 I, J ⊆ [n] 视为在 n 个变量 fI , gJ : Rn → R 中定义函数，将它们应用于由 (NA) 组随机变量给出的向量 ~ X = (X1, X2, ..., Xn) ，并规定 f( ~ X) 和 g( ~ X) 的值由奚。在这种表示法中，上述定义可以重述如下。定义 2（负关联 [10, 8]）。一组随机变量 X1, X2,... 。 。 , Xn 被称为负关联 (NA)，如果对于任何两个 n 维函数 f, g : Rn → R，根据索引的不相交子集以及各自索引中的两个单调递增或两个单调递减，它成立 E[f( ~ X) · g( ~ X)] ≤ E[f( ~ X)] · E[g( ~ X)]。 2 有用的属性第1部分作为NA定义的一个特例，取fi(~X)=Xi，我们发现NA变量是负相关的。推论 1（NA 意味着负相关）。令 X1, X2, . 。 。 , Xn 是 NA 随机变量。那么，对于所有的i 6=j，以下成立：E[XiXj]≤E[Xi]·E[Xj]。也就是说，Cov(Xi, Xj) ≤ 0。NA 变量的另一个有用属性是负或相关性 (NOD)，如下所示。
In these notes we present the notion of Negative Association, discuss some of its useful properties, and end with some example applications. The slogan to bear in mind here is “independent, or better”. 1 Negative Association Definition In randomized algorithms, our randomness often takes on the form of independent random variables, allowing us to apply powerful theorems concerning such variables, a prominent example being Chernoff-Hoeffding bounds. However, we can’t always expect random variables we observe (or generate during the run of our algorithms) to be independent. Nonetheless, these variables may satisfy some form of negative dependence, in which case useful properties of independence may carry over. This talk focuses on one such notion of negative dependence, namely Negative Association. Intuition Consider a set of random variables X1, X2, . . . , Xn, satisfying the following: if a subset S of these variables is “high”, then a disjoint subset T must be “low”. This property can be formalized as follows. Definition 1 (Negative Association [10, 8]). A set of random variables X1, X2, . . . , Xn is said to be negatively associated (NA) if for any two disjoint index sets I, J ⊆ [n] and two functions f, g both monotone increasing or both monotone decreasing, it holds E[f(Xi : i ∈ I) · g(Xj : j ∈ J)] ≤ E[f(Xi : i ∈ I)] · E[g(Xj : j ∈ J)]. In order to simplify notation later, we will think of monotone functions f and g and disjoint subsets I, J ⊆ [n] as defining functions in n variables fI , gJ : Rn → R, applying them to vectors ~ X = (X1, X2, . . . , Xn) given by sets of (NA) random variables, and stipulate that the values of f( ~ X) and g( ~ X) be determined by disjoint subsets of the Xi. In this notation, the above definition can be restated as follows. Definition 2 (Negative Association [10, 8]). A set of random variables X1, X2, . . . , Xn is said to be negatively associated (NA) if for any two n-dimensional functions f, g : Rn → R, depending on disjoint subsets of indices and both monotone increasing or both monotone decreasing in their respective indices, it holds E[f( ~ X) · g( ~ X)] ≤ E[f( ~ X)] · E[g( ~ X)]. 2 Useful Properties Part 1 As a special case of the definition of NA, taking fi( ~ X) = Xi, we find that NA variables are negatively correlated. Corollary 1 (NA implies Negative Correlation). Let X1, X2, . . . , Xn be NA random variables. Then, for all i 6= j, the following holds: E[XiXj ] ≤ E[Xi] · E[Xj ]. That is, Cov(Xi, Xj) ≤ 0. Another useful property of NA variables is Negative Orthant Dependence (NOD), given below.