Harris inequality

Remarks

The proof is by induction on $n$. For $n = 1$, the inequality is equivalent to $p_1 (1 - p_1) (f(1) - f(0)) (g(1) - g(0)) \ge 0$, which holds because both differences are nonnegative. The induction step conditions on the last coordinate and applies the case $n = 1$ to the conditional expectations, which are again increasing.

For indicator functions of increasing events $A$ and $B$, the inequality reads $\mu(A \cap B) \ge \mu(A) \, \mu(B)$: increasing events are positively correlated. For example, in the Erdős–Rényi model $G(n, p)$ the events "the graph is connected" and "the graph has a triangle" are increasing, so they are positively correlated. If $f$ is increasing and $g$ is decreasing, the inequality is reversed. The product structure of $\mu$ matters. For the measure giving probability $1/2$ to each of $(1, 0)$ and $(0, 1)$, the increasing events $\set{x_1 = 1}$ and $\set{x_2 = 1}$ have probability $1/2$ each but are disjoint.

Going deeper

For a student

The Harris inequality is the case of a product measure in the FKG inequality, which allows any measure on a distributive lattice satisfying the log-supermodularity condition. Both follow from the Ahlswede–Daykin inequality. For the uniform measure on subsets of a finite set, it is Kleitman's lemma: two up-sets $\mathcal{A}, \mathcal{B}$ of subsets of $\set{1, \ldots, n}$ satisfy $2^n |\mathcal{A} \cap \mathcal{B}| \ge |\mathcal{A}| \, |\mathcal{B}|$. It is a standard tool in percolation theory and random graphs, often together with the Janson inequality, which gives a bound in the other direction.