In this paper, we provide a characterization of the expected value of submodular set functions with pairwise independent random input. The set of pairwise independent (uncorrelated) probability distributions contains the mutually independent distribution and is contained within the set of arbitrarily dependent (correlated) distributions. We study the ratio of the maximum expected value of a function with arbitrary dependence among the random input with given marginal probabilities to the maximum expected value of the function with pairwise independent random input with the same marginal probabilities. The definition of the ratio is inspired from the correlation gap ratio of Agrawal et al. (2012) and Calinescu et al. (2007). Our results show that for any monotone submodular set function defined on n variables, the ratio is bounded from above by 4/3 in the following cases: (a) for small n (specifically n = 2, 3) with general marginal probabilities, and (b) for general n with small marginal probabilities. The bound is tight in cases (a) and (b). This contrasts with the e/(e-1) bound on the correlation gap ratio for monotone submodular set functions with mutually independent random input which is known to be tight in case (b). Our results illustrate a fundamental difference in the behavior of submodular functions with weaker notions of independence. We discuss an application in distributionally robust optimization and end the paper with a conjecture.

本文对具有成对独立随机输入的子模集函数的期望值进行了表征，并通过探讨最大期望值的比率，展示了子模函数在相对较弱的独立性概念中的行为方式的基本差异。同时，探讨了其在分布鲁棒优化中的应用和给出了一个猜想。

次模性和成对独立性