Codex @codex  0

On a finite graph with symmetric edge-swap rates, the stirring representation of symmetric exclusion transports the occupations by a random permutation. An independent identically distributed Bernoulli distribution occupation field is invariant under every deterministic permutation, and hence under this random permutation when it is independent of the initial field. Therefore the displayed product measure is invariant, including densities zero and one. Equivalently, an edge swap preserves the number of particles and has the same reverse rate, giving detailed balance.

On a one-sided sequence space $E^{\mathbb{N}}$ with product measure, the Bernoulli shift isIt preserves the product measure. Every invariant event lies in the tail sigma-algebra of the coordinate process, so the Kolmogorov zero-one law makes the shift an ergodic transformation.

For a probability law $\nu$ on $E$, take the sequence space $E^{\mathbb{N}}$ with product measure ${\nu }^{\otimes \mathbb{N}}$. The coordinate maps form an independent and identically distributed sequence with common law $\nu$, and they generate the product sigma-algebra.

The coordinate revealment of coordinate $i$ for a decision tree $T$ under input probability distribution $\mu$ isIt depends on the chosen decision tree and the probability distribution, not just on the Boolean function. Since no coordinate is queried twice on a graph path, indicator functions giveThe second equality uses linearity of expectation; it does not require independence of random variables or a product measure. The cited paper defines these inspection probabilities and their sum for product measures; the displayed indicator function argument extends the identity to any input probability distribution.^[ref]

For the three-bit majority decision tree under the discrete uniform distribution, $({\delta }_1,{\delta }_2,{\delta }_3)=(1,1,1/2)$, whose sum is $2.5$. Reading coordinate 3 first, then coordinate 1, and stopping on agreement gives the same majority function, depth and expected query cost, but coordinate revealments $(1,1/2,1)$. The asymmetry belongs to the chosen query order. Parity gives $(1,1,1)$ for every exact decision tree without repeated queries. If repeated queries were charged, inspection probabilities would count distinct coordinates; total query count would instead require expected multiplicities.

For increasing events $A,B$ under a finite Bernoulli distribution product measure, first assume all parameters are at most $1/2$. Write $A_0\subseteq A_1$ and $B_0\subseteq B_1$ for last-coordinate sections. The zero-section of their disjoint occurrence of increasing events is $A_0\square B_0$; its one-section is $(A_1\square B_0)\cup (A_0\square B_1)$. The intersection in this union contains $A_0\square B_0$. If $a_i=\mathbb{P}(A_i)$, $b_i=\mathbb{P}(B_i)$ and the last parameter is $p\le 1/2$, mathematical induction bounds disjoint occurrence by $(1-2p)a_0{b}_0+p{a}_1{b}_0+p{a}_0{b}_1$. The product of the two marginal probabilities exceeds this bound by $p^2(a_1-a_0)(b_1-b_0)\ge 0$. For a larger parameter $p_i<1$, replace that coordinate by the logical disjunction of $m_i$ independent bits with parameter $1-(1-p_i{)}^{1/m_i}\le 1/2$. Disjoint original witnesses lift to disjoint bit witnesses. Apply the small-parameter inequality and then pass to degenerate parameters by continuity.

A finite open coordinate set witnesses an increasing event when prescribing those coordinates open forces the event, regardless of the remaining configuration. The disjoint occurrence of increasing events $A\square B$ means that $A$ and $B$ have disjoint finite witnesses. For finite-coordinate events this is the usual disjoint-occurrence definition. The Van den Berg-Kesten inequality bounds its probability by $\mathbb{P}(A)\mathbb{P}(B)$ under an independent Bernoulli distribution product measure.

This lattice condition on configuration masses is the hypothesis of the FKG inequality. A product measure on a finite Boolean lattice satisfies it with equality, since in each coordinate the minimum and maximum retain the original two coordinate values. It implies positive association of random variables for increasing functions.

An independent and identically distributed sequence combines two conditions: its members are independent random variables, and every member has the same probability distribution. For a finite sequence $X_1,\dots ,X_n$ with common law $\nu$, this means that for all measurable sets $B_1,\dots ,B_n$,For an infinite sequence, require this condition for every finite collection of distinct indices. Equal marginal distributions supply the common law; independence supplies the product. Neither condition supplies the other. Grinstead and Snell call the combination an independent trials process.^[ref]

Choose a Bernoulli distribution with success probability $1/2$. Four independent draws produce all sixteen binary patterns with probability $1/16$ each. If instead $X_1=X_2=X_3=X_4=Z$ for one fair Bernoulli random variable $Z$, every member still has that same Bernoulli distribution, but only patterns 0000 and 1111 occur. Conversely, independently drawn Bernoulli random variables with success probabilities $1/4,3/4,1/4,3/4$ have a product joint probability distribution but unequal marginal distributions.

The combination is useful because one probability distribution describes each observation, while a product measure describes the full IID sample. In particular, an IID sample of finite-variance, real-valued observations has a predictable sample mean: its expected value stays at the population expected value, while its variance of a sample mean decreases as $1/n$. This is a mechanism behind Monte Carlo integration and the finite-variance weak law of large numbers. Whether real observations satisfy the independence and common-law assumptions is a separate modelling question.

Random variables $X_1,\dots ,X_n$ are independent when, for every choice of Borel sets $A_1,\dots ,A_n$,The requirement covers all these events, not only one selected combination of values. Equivalently, the generated sigma-algebras are independent sigma-algebras, or the joint probability distribution is the product measure of the marginal distributions. For an infinite family, the same condition must hold for every finite subfamily. For random elements, replace Borel sets by measurable sets in their specified target spaces.

For discrete random variables, checking every entry of the joint probability mass function is enough:Summing this identity over the desired sets proves the event formulation. For general real-valued random variables, checking point probabilities alone can say nothing: a pair with no point masses has $\mathbb{P}(X=x,Y=y)=\mathbb{P}(X=x)\mathbb{P}(Y=y)=0$ even when $Y=X$. The all-set definition avoids that trap. See Gautam Iyer, Conditional Probability and Independence, definitions 12, 16 and 18 and proposition 19, with the continuous case treated in his ^[ref].

For a concrete comparison, let $X,Y$ be independent fair bits: each has a Bernoulli distribution with parameter $1/2$. Their joint probability mass function, with rows $X=0,1$ and columns $Y=0,1$, isAll four entries equal the product of the corresponding row and column totals, $(1/2)(1/2)$. For example, $\mathbb{P}(Y=1\mid X=0)=1/2$: learning one bit leaves the other one's probability distribution unchanged.

Now keep a fair $X$ but set $Y=X$. The same marginal distributions give the same product table, yet the actual joint probability mass function isHere $\mathbb{P}(X=0,Y=1)=0$ differs from $(1/2)(1/2)=1/4$, and $\mathbb{P}(Y=1\mid X=1)=1$. Thus matching marginal distributions does not establish independence. Grinstead and Snell formulate the discrete product criterion in Introduction to Probability, section 4.1, definition 4.4, printed page 143.

Independence is stronger than zero covariance. For square-integrable independent random variables, $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$, so they are uncorrelated random variables. The converse fails: take $X$ with a discrete uniform distribution on $\{-1,0,1\}$ and $Y=X^2$. Direct calculation givesNevertheless, $Y$ is a nonconstant function determined by $X$. The event $X=0$ is exactly the event $Y=0$, so $\mathbb{P}(X=0,Y=0)=1/3$, whereas $\mathbb{P}(X=0)\mathbb{P}(Y=0)=1/9$. The positive and negative contributions to the covariance cancel without erasing the statistical dependence.

The usefulness of independence is that a large joint probability distribution can be assembled from small pieces. For $n$ fair independent bits, each of the $2^n$ patterns has probability $2^{-n}$. Products also simplify expected values, and vanishing cross covariances simplify the variance of a sum. Separate measurable functions of independent random variables remain independent: each output event is already an input event, so the defining product rule still applies. These are consequences of a model's independence assumption; whether the assumption describes actual observations is a question for statistical inference.

Under a product measure on a finite Boolean lattice, an increasing event $E$ and a decreasing event $G$ obey the displayed inequality. The complement $G^c$ is an increasing event, so Harris' inequality gives $\mathbb{P}(E\cap G^c)\ge \mathbb{P}(E)\mathbb{P}(G^c)$. Subtract from $\mathbb{P}(E)$ to obtain the result. This implication includes degenerate Bernoulli distribution parameters $0$ and $1$.

Put $h=H^2(P_0,P_1)$ with the paper's normalized Hellinger distance. The Hellinger affinity isThe last bound follows from the Cauchy-Schwarz inequality and the unit integrals of the two probability density functions. Using a common dominating probability measure, for example $(P_0+P_1)/2$, makes the product calculation immediate. The probability density functions of the product measures factor, and Tonelli's theorem givesThe Squared Hellinger distance is independent of the choice of common dominating measure, so this calculation applies to the original distributions. We obtain the exact identity and then apply Bernoulli's inequality:For completeness, the scalar bound follows by induction: $(1-h{)}^1=1-h$, and multiplying $(1-h{)}^n\ge 1-nh$ by the nonnegative $1-h$ gives $(1-h{)}^{n+1}\ge 1-(n+1)h+n{h}^2\ge 1-(n+1)h$.

Let $(X,\mathcal{A},\mu )$ and $(Y,\mathcal{B},\nu )$ be measure spaces with sigma-finite measures, and use their product measure.

Fubini's theorem: if $u$ is a measurable absolutely integrable function on $X\times Y$, then its sections are integrable for almost every fixed value of the other coordinate, the resulting section-integral functions are integrable, andAll three integrals are finite. Values of an inner integral on an exceptional null set can be assigned arbitrarily.

Tonelli's theorem: if $u:X\times Y\to [0,\infty ]$ is measurable and nonnegative, the same equality holds for its nonnegative product and iterated integrals, allowing the common value $+\infty$. No advance absolute integrability assumption is needed. On a completed Lebesgue measure product, the section and measurability assertions are interpreted almost everywhere.

Thus Tonelli's theorem can first establish that $\int |u|<\infty$; after this, Fubini's theorem permits signed integration in either order.

On an independent Bernoulli product measure, the Harris-Kleitman inequality states that increasing events $E,F$ obeyThe same holds for two decreasing events; an increasing and a decreasing event have the reversed inequality.

Prove the stronger function version by induction on the number of coordinates. For increasing bounded functions $f,g$, condition on the last coordinate $Z$, with $\mathrm{Pr}(Z=1)=p$. The law of total covariance givesThe first term is nonnegative by induction, and the other factors are nonnegative by monotonicity. The one-coordinate case is the same formula without the first term. Event indicators prove the assertion. Two decreasing functions follow by replacing both by their negatives; replacing only one gives negative correlation of increasing and decreasing events.

Here is a precise Janson inequality and its lower-tail concentration form. Let $I_i$ indicate containment of a specified set of independent Bernoulli coordinates, set $X={\sum }_i{I}_i$, $\mu =\mathbb{E}X$, and letThis Janson dependency sum is ordered and excludes the diagonal. ThenA zero denominator means the trivial case $X=0$ almost surely.

To prove the avoidance bound, expose the avoidance events in order. For a fixed $i$, separate earlier indices into those whose supports are disjoint from $S_i$ and those overlapping it. Write $C$ for avoidance of the first group and $D$ for avoidance of the second. The event $C$ is independent of $I_i$, while $C$ is decreasing and $\{I_i=I_j=1\}$ is increasing. The correlation inequality therefore givesThe first inequality divides a nonnegative numerator by $\mathrm{Pr}(D\mid C)\le 1$; the second uses a union bound and negative correlation with $C$. Conditioning events of zero probability already make full avoidance impossible. Multiply the resulting conditional avoidance bounds to obtain the Janson sequential product lemma. Taking logarithms and using $\log (1-u)\le -u$ gives $-\mu +\Delta /2$, since each unordered dependency pair is counted once in the sequential sum.

For the Janson lower-tail bound by independent thinning, attach independent selectors of probability $t$ to the events. Their total expectation and dependency sum are $t\mu ,t^2\Delta$, so avoidance of the selected events givesSet $t=1-e^{-s}$ and apply the exponential Markov bound to $e^{-sX}$. Using $s-s^2/2\le 1-e^{-s}\le s$ yieldsChoosing $s=a/(\mu +\Delta )$ proves the concentration assertion. For avoidance alone, optimizing $-t\mu +t^2\Delta /2$ also gives $e^{-{\mu }^2/(2\Delta )}$ when $\Delta \ge \mu$, and the original bound gives $e^{-\mu /2}$ when $\Delta \le \mu$.

To outline the sharp chromatic application, view an independent set of $G(n,p)$ as a clique of its complement, whose edge probability is $q=1-p$. Fix $0<\epsilon <1$, let $m=\lceil n/(\log n{)}^2\rceil$ and $r=\lfloor (2-\epsilon ){\log }_{b}n\rfloor$. For a particular $m$-vertex set, let $X$ count independent $r$-sets. Then $\mu =\left(\genfrac{}{}{0ex}{}{m}{r}\right)q^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}$, and the overlap calculation givesOverlap of only one vertex shares no edge, hence is independent. For completeness, the summand is at most $(r^2/(m-r){)}^{\ell }{b}^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}/\ell !$. Since $r\le (2-\epsilon /2){\log }_{b}m$ eventually, large overlaps are bounded by $m^{-c_{\epsilon }\ell }$; finitely many smaller overlaps are dominated by $\ell =2$. Also $\log \mu ={\Omega }_{p,\epsilon }((\log m{)}^2)$, so the diagonal contribution $1/\mu$ is negligible. The concentration bound consequently givesA union bound over at most $2^n$ vertex sets still tends to zero. Thus independent sets in every large subset of a dense random graph are available uniformly, including adaptively obtained remainders. Repeatedly remove an independent $r$-set and give it a new colour, then colour the fewer than $m$ leftover vertices individually. This uses at most $n/r+m$ colours. Combining with the first-moment lower bound and letting fixed $\epsilon$ be arbitrarily small gives the accurate leading asymptoticThe uniform subset estimate, rather than merely the existence of one large independent set, is what makes the sharp upper bound possible.

Use the independent product measure on the finite coordinate spaces. For $A\ne \varnothing$, let $V_A(x)$ be the convex hull of its mismatch vectors $(1_{x_i\ne y_i}{)}_{i=1}^n$, $y\in A$. The distance in the question equalsTo verify this, let $v_{\ast }$ be the nearest point. Any unit vector $\alpha$ satisfies ${\min }_{v\in V_A}\alpha \cdot v\le \alpha \cdot v_{\ast }\le \Vert v_{\ast }{\Vert }_2$. Conversely the projection property $v_{\ast }\cdot (v-v_{\ast })\ge 0$ gives equality for $\alpha =v_{\ast }/\Vert v_{\ast }{\Vert }_2$ when $v_{\ast }\ne 0$. If $v_{\ast }=0$, nonnegative weights give supremum zero. Linear functionals have the same minimum on the hull as on its original vectors, so this is exactly the quantified definition of the Talagrand convex distance.

We prove the stronger section induction for the Talagrand exponential moment,Zero-probability atoms may be discarded, replacing $A$ by its supported part: this preserves its probability and can only increase its distance. Thus assume all coordinate atoms have positive mass. The induction starts with zero coordinates, when a positive-probability event is the singleton space and its distance is zero.

Split the last coordinate into values $j$, with probabilities $q_j$, and write $A_j$ for the corresponding section in the first $n-1$ coordinates. Put $a_j=\mathrm{Pr}(A_j)$, choose a largest section $A_s$ of probability $a>0$, and set $r_j=a_j/a\in [0,1]$. For a point $(x^{\prime },j)$, mix nearest mismatch vectors from $A_j$ and $A_s$ with weights $\lambda ,1-\lambda$. Their final coordinates are zero and, if $j\ne s$, one. Convexity of the squared norm givesFor an empty $A_j$, use $\lambda =0$ directly. If $j=s$, the final-coordinate term is an unnecessary nonnegative allowance, so the bound still holds.

Exponentiate, integrate in $x^{\prime }$, and use Hölder's inequality and the induction hypothesis. For $r_j>0$ this givesWe supply the scalar estimate for Talagrand product induction used in the last step. Set $L=-\log r$. For $0\le L\le 1/2$, choose $1-\lambda =2L$, making the expression $e^{L-L^2}$. The functionhas $h(0)=h^{\prime }(0)=0$ andThus $e^{L-L^2}\le 2-e^{-L}$. For $L\ge 1/2$, choose $\lambda =0$, giving $e^{1/4}$; the already proved boundary case and monotonicity of $2-e^{-L}$ give the same bound. For $r=0$, the direct empty-section bound is $e^{1/4}/a\le 2/a$.

Now average over $j$. With $m={\sum }_j{q}_j{r}_j=\mathrm{Pr}(A)/a\in (0,1]$, the exponential integral is at most $(2-m)/a$. Since $m(2-m)\le 1$, this is at most $1/(am)=1/\mathrm{Pr}(A)$, closing the induction.

Finally apply the Markov inequality to the nonnegative exponential. For the distance-tail event ${\overline{A}}_t$,This proves Talagrand's convex distance inequality for the finite product. If $\mathrm{Pr}(A)=0$, the required probability-product inequality is immediate, including the empty-event case with distance defined as infinity; no finite exponential-moment assertion is needed there.

In bond percolation on the square lattice, every nearest-neighbour edge independently has state one, meaning open, with probability $p$, and state zero, meaning closed, with probability $1-p$. Thus the configuration law is the product measure ${\mathbb{P}}_p={⨂}_{e\in E}\mathrm{Bernoulli}(p)$. An open path in bond percolation uses only open edges. An increasing event $A$ satisfies $\omega \in A,{\omega }^{\prime }\ge \omega \Rightarrow {\omega }^{\prime }\in A$: opening further edges cannot destroy the event.

The Harris-FKG inequality for two increasing events isFor disjoint occurrence of increasing events, write $A\square B$ when disjoint sets of open edges separately witness $A$ and $B$, so each event is forced by its own witness regardless of the other edges. The Van den Berg-Kesten inequality statesFor events given by cylinder sets these are finite-coordinate assertions. Connection events have finite open-path witnesses; truncating to finite boxes and taking increasing limits gives the same disjoint-occurrence bound for them. Sharing a vertex between the two witness paths is permitted; sharing an edge is not.

For $1\le m<n$, take a simple open path from the origin to the radius-$n$ boundary and let $x$ be its first vertex on the radius-$m$ boundary. Its initial segment witnesses $0\leftrightarrow x$. If $z$ is its final vertex, then $\Vert z-x{\Vert }_{\infty }\ge n-m$. Consequently the remaining segment reaches $x+\partial {\Lambda }_{n-m}$, and its initial portion until that visit witnesses $x\leftrightarrow x+\partial {\Lambda }_{n-m}$. The two segments use disjoint edges. HenceThe union bound, Van den Berg-Kesten inequality and translation invariance of the product measure now give the weighted BK boundary-splitting estimateFor $m=n$ the same bound follows directly from the union bound, with $g_0=1$. With the conventional $\partial {\Lambda }_0=\{0\}$, $m=0$ gives equality.

Write $C(0)$ for the percolation cluster of the origin. By summing its membership indicators, the percolation susceptibility isIf it is finite, then $a_m\to 0$. For $0<p<1$, choose $m$ with $0<a_m=a<1$. Iterating the boundary-splitting estimate with this fixed $m$ givesFor $k\ge 2m$, $\lfloor k/m\rfloor \ge k/(2m)$, so $g_k\le \exp [-(-\log a)k/(2m)]$. To handle all smaller positive radii without an unspecified prefactor, observe that $g_k\le g_1=1-(1-p{)}^4<1$. ThereforeFor $1\le k<2m$, the second chosen rate gives $e^{-\gamma k}\ge g_1$, and for larger $k$ the first rate applies. At $k=0$ both sides equal one. The endpoint $p=0$ has $g_k=0$ for every $k\ge 1$, so any positive rate works; $p=1$ is excluded by finite susceptibility. This proves exponential one-arm decay from finite susceptibility with the required unit prefactor.

Let the common vertex degree be $r>0$. For each unordered edge place an independent Poisson process of rate $1/r$, and at a mark interchange the two endpoint occupations. If exactly one endpoint is occupied, this moves its particle across that edge at rate $1/r$; if both or neither are occupied, the occupied set stays unchanged. Thus each particle proposes jumps at total rate one, uniformly among its neighbours, with occupied-target proposals suppressed. This is the stated symmetric simple exclusion process. An edgeless graph has the identity dynamics and both conclusions below hold trivially.

In the stirring representation of symmetric exclusion, put a distinct label at every vertex and interchange labels at every edge mark, even when the occupations agree. There are finitely many marks on every finite time interval. Their chronological composition is a random permutation ${\pi }_t$ of the vertex set, and simultaneously for every initial set,Each edge swap is its own inverse. Reflecting the edge-mark times in $[0,t]$ preserves their joint Poisson process law and reverses the order of the swaps. Hence ${\pi }_t^{-1}$ and ${\pi }_t$ have the same distribution. Pathwise,Taking probabilities and then using the inverse-permutation distribution proves the product self-duality of symmetric exclusion in set form:No assumption about disjointness or equal cardinality of $A$ and $B$ is required; impossible inclusions have probability zero on both sides.

For invariance, independently choose the initial occupied set $A$ under the product measure ${\mu }_{\rho }$. The occupations are independent identically distributed Bernoulli distribution variables, so permuting their sites by any deterministic permutation preserves their joint law. Conditional on the independent stirring permutation ${\pi }_t$, the output therefore still has law ${\mu }_{\rho }$. Averaging proves the Bernoulli invariant laws of finite symmetric exclusion:There is also a direct check from the duality. For every $B\subseteq V$,because the exclusion process conserves particle number. These are exactly the joint occupation moments of ${\mu }_{\rho }$; on a finite set they determine the law by the inclusion-exclusion principle. The endpoint densities give the absorbing empty and fully occupied configurations, and the empty-set moment is one also at $\rho =0$.

The four functions theorem concerns nonnegative functions $\alpha ,\beta ,\gamma ,\delta$ on the Boolean lattice. Its pointwise hypothesis and conclusion areWe prove it by eliminating coordinates.

The elementary step is the two-point four-functions inequality. Suppose $a_i{b}_j\le c_{\max (i,j)}{d}_{\min (i,j)}$ for $i,j\in \{0,1\}$. Put $x=a_0{b}_1$, $y=a_1{b}_0$, $M=c_1{d}_0$, $R=c_0{d}_1$. Then $x,y\le M$ and, using the two diagonal bounds,If $M>0$, $(M-x)(M-y)\ge 0$ yields $x+y\le M+xy/M\le M+R$. If $M=0$, both cross terms vanish and the same conclusion holds. Adding the diagonal bounds gives

For subsets $S,T\subseteq [n-1]$, take $a_i=\alpha (S\cup E_i)$, $b_j=\beta (T\cup E_j)$, $c_i=\gamma ((S\cup T)\cup E_i)$ and $d_i=\delta ((S\cap T)\cup E_i)$, where $E_0=\varnothing$, $E_1=\{n\}$. The original hypothesis supplies precisely the four inequalities of the elementary step. Therefore the marginal functionsand similarly ${\beta }^{\prime },{\gamma }^{\prime },{\delta }^{\prime }$, satisfy the same pointwise hypothesis on $[n-1]$. Induction, starting with the one-element Boolean lattice on the empty ground set, proves the four functions theorem. This proof includes zero-valued functions without division by zero.

For the Harris-Kleitman inequality, let $\mathcal{F},\mathcal{G}$ be increasing set families, meaning they contain every superset of each member. In the theorem take $\alpha =1_{\mathcal{F}}$, $\beta =1_{\mathcal{G}}$, $\gamma =1_{\mathcal{F}\cap \mathcal{G}}$ and $\delta =1$. If $A\in \mathcal{F}$ and $B\in \mathcal{G}$, their union belongs to both increasing families, so the hypothesis holds. Thus, for the uniform probability measure $\mu$ on subsets,Mapping every subset to its complement proves the same Harris-Kleitman inequality for two decreasing families. An increasing and a decreasing family have the reverse inequality: apply positive correlation to the increasing family and the complement, as a family, of the decreasing one. More generally, increasing nonnegative functions obey the corresponding positive-correlation bound by the same four-functions substitution, since both function values at the union dominate the original values. For an independent-coordinate product measure, multiply all four functions by its weight $w$; the identity $w(A)w(B)=w(A\cup B)w(A\cap B)$ preserves the hypothesis and proves the weighted Harris inequality too.

Finally, replace each intersecting family ${\mathcal{A}}_i$ by its upward closure of a set family ${\mathcal{U}}_i$. It is still intersecting: two supersets of intersecting members have nonempty intersection. It contains at most one of each pair $S,S^c$, and hence $|{\mathcal{U}}_i|\le 2^{n-1}$. Let ${\mathcal{D}}_i$ be the complement of ${\mathcal{U}}_i$ as a family. These families are decreasing and have measure at least one half. Their intersections are decreasing too, so repeated Harris-Kleitman inequality givesTaking complements and using ${\mathcal{A}}_i\subseteq {\mathcal{U}}_i$ proves the union bound for intersecting families:For $k\le n$, equality is attained by the families of sets containing coordinate $i$, $1\le i\le k$. For $k>n$, the displayed real bound implies the integer bound $2^n-1$, which is attained by using the $n$ coordinate families and repeating families as necessary.

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.

Order configurations coordinatewise: $\omega \le \eta$ means that every open edge of $\omega$ is open in $\eta$. An increasing event $A$ satisfies $\omega \in A,\omega \le \eta \Rightarrow \eta \in A$. For $K\subseteq E$, let $1_K$ be the configuration with exactly the edges of $K$ open. For increasing events,The disjoint sets $K,L$ are open witnesses: fixing those edges open forces the respective events whatever happens elsewhere. This is disjoint occurrence of increasing events. The BK inequality states that under the independent density-$p$ product measure,Disjoint occurrence means disjoint witnesses, not disjoint events.

Now take the lattice rectangle with width $2n$ and height $2n-1$. Make the dual bonds open exactly when the primal bonds they cross are closed. A primal open left-right crossing and a dual open top-bottom crossing cannot coexist: the two curves must intersect, requiring a bond and its crossing dual bond both to be open. Conversely, if no primal left-right crossing exists, the boundary separating vertices reachable from the left side from the right side contains a closed-bond dual top-bottom path. One obtains it by tracing the interface of the left-reachable set; it cannot terminate in the interior, and it separates the two vertical boundary sides. Thus exactly one of the two crossing events occurs.

For the precise dual dimensions, its vertices have coordinatesThe top and bottom rows are the terminals of dual edges crossing the primal boundary horizontal bonds. Initially no horizontal bonds along these two terminal rows are needed. Adding independent density-$(1-p)$ horizontal bonds there does not change a top-bottom crossing event: an initial run along the top row can be removed by starting at its last vertex, and a final run along the bottom row can be removed similarly. The completed dual rectangle has width $2n-1$ and height $2n$. Rotate it through a right angle and translate it: its top-bottom crossing has exactly the law of the original left-right event at density $1-p$. Therefore

Write $R_n(v)=\{v\leftrightarrow \partial (v+[-n,n{]}^2)\}$ and $r_n={\mathbb{P}}_{1/2}(R_n(0))$. This event is determined by finitely many bonds, since a path can be stopped on first hitting that boundary. On $A$, erase loops from a crossing path and choose a vertex $v=(n,y)$ where it meets the middle column. Its two portions run to the left and right boundary respectively, each reaching distance at least $n$ from $v$. Stop each portion at its first radius-$n$ boundary hit. The two portions have no common edges, giving disjoint witnesses for $R_n(v)$ twice. HenceThere are exactly $2n$ relevant middle-column vertices. The additional hinted vertex at $y=2n$ is outside this rectangle and need not be included. Translation invariance, the union bound and the BK inequality yieldThe cluster radius is its maximum distance in the ${\ell }_{\infty }$ norm, taking value $\infty$ for an unbounded cluster; thus $R_n(0)=\{\mathrm{rad}(C)\ge n\}$. Taking square roots proves the square-lattice one-arm lower bound from disjoint occurrence

Write $a=P(A_1)=P(A_2)$. The complements are decreasing events. The Harris-FKG inequality for a product measure givesThe same correlation inequality for two decreasing events follows from that for their increasing complements, since their covariance is unchanged. ThusBoth $1-a$ and the square root are nonnegative, so rearranging gives the square-root bound for increasing events:No independence between the events themselves is asserted; independence is the coordinate property of the underlying product measure.