= Solution
<Harris' inequality> states that, for a <product measure> on $\{0,1\}^n$ with independent <Bernoulli random variables> of parameters $p_i\in[0,1]$, <increasing events> $E,F$ satisfy
$$
\boxed{\mathbb P(E\cap F)\geq\mathbb P(E)\mathbb P(F).}
$$
In particular, the uniform <probability measure> on the <Boolean lattice> gives $|E\cap F|\geq|E||F|/2^n$. We give a direct <mathematical induction> proof, so no stronger correlation theorem is assumed.
Prove more generally that $\mathbb E[fg]\geq\mathbb E[f]\mathbb E[g]$ for real coordinatewise increasing <functions> $f,g$ on the finite cube. For $n=0$ both are constant and equality holds. For the inductive step let $p=p_n$, and let $f_j,g_j$ be the restrictions obtained by setting the last coordinate equal to $j\in\{0,1\}$. Write $a_j=\mathbb E[f_j]$, $b_j=\mathbb E[g_j]$, using the <product measure> on the other coordinates. Monotonicity gives $a_0\leq a_1$, $b_0\leq b_1$. By the inductive hypothesis and <conditional expectation>,
$$
\begin{aligned}
\mathbb E[fg]&\geq(1-p)a_0b_0+pa_1b_1\\
&=((1-p)a_0+pa_1)((1-p)b_0+pb_1)+p(1-p)(a_1-a_0)(b_1-b_0)\\
&\geq\mathbb E[f]\mathbb E[g].
\end{aligned}
$$
The nonnegative correction term also handles $p=0$ and $p=1$. Taking <indicator functions> $f=\mathbf1_E$, $g=\mathbf1_F$ proves <Harris' inequality>.
For later use, an <increasing event> $E$ and a <decreasing event> $G$ have <negative correlation of increasing and decreasing events>. The complement $G^c$ is an <increasing event>, so
$$
\mathbb P(E\cap G)=\mathbb P(E)-\mathbb P(E\cap G^c)\leq\mathbb P(E)(1-\mathbb P(G^c))=\mathbb P(E)\mathbb P(G).
$$
Back to article page
