  In this paper, we provide a characterization of the expected value of
monotone submodular set functions with $n$ pairwise independent random inputs.
Inspired by the notion of ``correlation gap'', we study the ratio of the
maximum expected value of a function with arbitrary dependence among the random
inputs with given marginal probabilities to the maximum expected value of the
function with pairwise independent random inputs and the same marginal
probabilities. Our results show that the ratio is upper bounded by: (a) $4/3$
for $n = 3$ with general marginal probabilities and any monotone submodular set
function (b) $4/3$ for general $n$ with small and large marginal probabilities
and any monotone submodular set function and (c) $4k/(4k-1)$ for general $n$,
general identical probabilities and rank functions of $k$-uniform matroids. The
bound is tight in all three cases. This contrasts with the $e/(e-1)$ bound on
the correlation gap ratio for monotone submodular set functions with mutually
independent random inputs (which is known to be tight in case (b)), and
illustrates a fundamental difference in the behavior of submodular functions
with weaker notions of independence. These results can be immediately extended
beyond pairwise independence to correlated random inputs. We discuss
applications in distributionally robust optimization and mechanism design and
end the paper with a conjecture.
