Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 14 / 6

We prove both inequalities, including the BK inequality, for the inhomogeneous product measure in the question. Identify a configuration with its set of coordinates equal to one. An up-set is then an increasing event. For an increasing event $A$, a set $S$ of open coordinates is a witness if the configuration with precisely $S$ open belongs to $A$: upward closure ensures that those coordinates alone force $A$, whatever the remaining coordinates do. The event $A\square B$ means that there are disjoint open witnesses $S,T$ for $A,B$ respectively.

First prove the Harris' inequality by induction on the number of coordinates. For the last coordinate, of parameter $p$, write $A_0\subseteq A_1$ and $B_0\subseteq B_1$ for the two sections in the remaining coordinates, and put $a_i=\mathbb{P}(A_i)$, $b_i=\mathbb{P}(B_i)$. Induction applied to each section givesSubtract the product of the marginal probabilities from the right-hand side:The base case of zero coordinates is immediate. Thus

For disjoint occurrence, first assume every coordinate parameter is at most $1/2$, and again use induction. Put $c_{ij}=\mathbb{P}(A_i\square B_j)$ on the remaining coordinates. The zero-section of $A\square B$ is exactly $A_0\square B_0$. The one-section is exactlyIndeed, the last open coordinate can belong to at most one of two disjoint witnesses. Assigning it to the $A$ witness leaves a witness for $A_1$ and a witness for $B_0$; assigning it to the $B$ witness gives the other event. If neither witness uses it, both descriptions still hold. Conversely, witnesses for either displayed event lift to disjoint witnesses by adding the last coordinate only to the appropriate one.

The intersection of the two displayed events contains $A_0\square B_0$, because the sections are increasing. ThereforeThe coefficient $1-2p$ is nonnegative. Applying the induction hypothesis to each term givesThe product of the marginal probabilities is exactly this last expression plusThis proves the desired inequality whenever every parameter is at most $1/2$.

To remove that restriction, suppose first $p_i<1$ for every coordinate. Replace coordinate $i$ by the logical disjunction of $m_i$ independent Bernoulli bits, each with parameterChoose $m_i$ large enough that $q_i\le 1/2$. Different blocks are independent, and their OR values have exactly the original distribution. Let $\tilde{A},\tilde{B}$ be the inverse images of $A,B$ under this block-OR map; they are increasing events. If the OR configuration has disjoint witnesses $S,T$, choose one open bit from each block indexed by $S$ or $T$. The bits chosen for $S$ force $\tilde{A}$, those for $T$ force $\tilde{B}$, and the two bit sets are disjoint. Thus the inverse image of $A\square B$ is contained in $\tilde{A}\square \tilde{B}$. The small-parameter result provesParameters equal to one follow by a limit: probabilities of any fixed event on a finite cube are polynomials in the coordinate parameters, hence continuous. Zero parameters already cause no difficulty. We have obtained

For the graph application, take coordinates to be the edges of the complete graph. Let $A$ be the increasing event that $x$ is connected by a graph path to $U$, and $B$ the corresponding event for $W$. Their probabilities are $\alpha ,\beta$. A simple graph path from $U$ to $W$ through $x$ splits at $x$ into two graph paths with disjoint edge sets. Those sets witness $A$ and $B$, so this graph path event is contained in $A\square B$. The BK inequality givesOn the other hand, if both $A$ and $B$ occur, concatenate an $x$-to-$U$ graph path and an $x$-to-$W$ graph path to obtain a walk from $U$ to $W$. Removing loops yields a simple graph path, although it need not pass through $x$. Thus $A\cap B$ is contained in the unrestricted connection event, and the Harris' inequality givesThe distinction between a simple graph path through $x$ and an unrestricted connection is essential: a walk may revisit an edge, so a through-$x$ walk would not in general provide disjoint witnesses.