Correlation Reversal

In an earlier post, we discussed Kleitman's Theorem, which tells us that monotone events are nonnegatively correlated. So, for example, if we generate a random graph G, including each edge with probability 1/2, and we condition on the event that G is nonplanar, that can only make it more likely that G is Hamiltonian, not less.

There's a further wrinkle we could add to make things more interesting. By a witness for the event f(x) = 1 on a particular bitstring x, we mean a subset of the bits of x that force f(x) = 1. (This event could have multiple, overlapping or disjoint, witnesses.)

Let f, g be monotone Boolean functions, and consider the event we'll call f^^g, the event (over uniformly chosen x)that f(x), g(x) are both 1 and that, moreover, we can find disjoint witnesses for these two conditions.

Problem: Is P(f^^g) greater or less than P(f = 1)*P(g = 1)?

On the one hand, f and g `help each other' to be 1, by Kleitman's Theorem. On the other hand, the disjoint-witness requirement seems to undercut their ability to positively influence each other. Which tendency wins out?

I'll tell you: P(f^^g) <= P(f = 1)*P(g = 1). The latter tendency prevails, although ironically enough, Kleitman's Theorem can actually be used to show this! It's a not-too-hard exercise in conditioning, which I recommend to the interested reader.

Here's the kicker, though: the inequality above is actually true for arbitrary f, g, not just monotone ones! This result, however, took a decade of work to prove; it was conjectured by van den Berg and Kesten, and proved by Reimer in 1994; see this article. Reimer's Inequality appears fruitful in probabilistic analysis, including in theoretical CS, see this article (which I have yet to read).