A maximum conditional edge influence bound for finite FK measures

We first establish two conditional comparisons. Fix some coordinates and change one prescribed value from zero to one. The resulting laws ${\mu }_0,{\mu }_1$ on the unprescribed coordinates are strictly positive and associated by [F1]. For $z\le z^{\mathrm{\prime }}$, apply log-supermodularity to the incomparable configurations $(z^{\mathrm{\prime }},0)$ and $(z,1)$ to obtain ${\mu }_1(z^{\mathrm{\prime }}){\mu }_0(z)\ge {\mu }_0(z^{\mathrm{\prime }}){\mu }_1(z)$; normalizing constants cancel. Thus $R={\mu }_1\mathrm{/}{\mu }_0$ is increasing, ${\mathbb{E}}_{{\mu }_0}R=1$, and association gives ${\mathbb{E}}_{{\mu }_1}h={\mathbb{E}}_{{\mu }_0}(hR)\ge {\mathbb{E}}_{{\mu }_0}h$ for every increasing $h$. Successively changing prescribed coordinates proves conditional monotonicity for ordered assignments on the same prescribed set. Separately, in any fixed-prefix conditional law, association gives $\mathrm{Cov}(h,X_j)\ge 0$, whence $\mathbb{E}[h\mid X_j=0]\le \mathbb{E}h\le \mathbb{E}[h\mid X_j=1]$ for increasing $h$. Strict positivity makes both conditional expectations defined. This second comparison allows an additional coordinate to be prescribed.

Label the edges $1,\dots ,n$. For a prefix $\eta$ put $a_r(\eta )=\varphi (X_r=1\mid X_s={\eta }_s,s<r)$ and $t_r(\eta )=1-a_r(\eta )$; positivity gives $0<t_r<1$. For $U\in [0,1{]}^n$ define recursively ${\mathrm{\Phi }}_r(U)={\mathbf{1}}_{\{U_r>t_r({\mathrm{\Phi }}_{<r}(U))\}}$. The first comparison in step 1.1 makes each $a_r$ increasing, so induction makes $\mathrm{\Phi }$ coordinatewise increasing. For every $\omega \in \{0,1{\}}^n$, its exact inverse image is the box $Q_{\omega }={\prod }_r{I}_r(\omega )$, where $I_r(\omega )=(t_r({\omega }_{<r}),1]$ if ${\omega }_r=1$ and $I_r(\omega )=[0,t_r({\omega }_{<r})]$ if ${\omega }_r=0$. Indeed membership in these intervals recursively forces exactly the prefix ${\omega }_{<r}$ and then bit ${\omega }_r$. These boxes form a disjoint partition of the entire cube, including all threshold values and endpoint faces. Their elementary volumes are $v_n(Q_{\omega })={\prod }_r{a}_r({\omega }_{<r}{)}^{{\omega }_r}(1-a_r({\omega }_{<r}){)}^{1-{\omega }_r}=\varphi (\omega )$ by the finite chain rule. Consequently $C={\mathrm{\Phi }}^{-1}(A)={\bigcup }_{\omega \in A}{Q}_{\omega }$ is an increasing finite-box set of elementary volume $\varphi (A)$.

Fix $j$ and use the same uniforms attached to the same edge labels to construct $\mathrm{\Psi }$ in order $j,1,\dots ,j-1,j+1,\dots ,n$. First set $U_j=1$. Both outputs have $j$th bit one. For $r<j$, suppose inductively ${\mathrm{\Psi }}_{<r}\ge {\mathrm{\Phi }}_{<r}$. The two comparisons in step 1.1 give $\varphi (X_r=1\mid X_{<r}={\mathrm{\Psi }}_{<r},X_j=1)\ge \varphi (X_r=1\mid X_{<r}={\mathrm{\Phi }}_{<r},X_j=1)\ge \varphi (X_r=1\mid X_{<r}={\mathrm{\Phi }}_{<r})\mathrm{.}$ The common $U_r$ therefore gives ${\mathrm{\Psi }}_r\ge {\mathrm{\Phi }}_r$. After coordinate $j$, both constructions condition on the same set of previous labels, including $j=1$, with ordered values, so the first comparison alone continues the induction for $r>j$. Thus $\mathrm{\Psi }(U_{-j},1)\ge \mathrm{\Phi }(U_{-j},1)$ pointwise. With $U_j=0$, both $j$th bits are zero. For $r<j$, induction and the same two comparisons instead give $\varphi (X_r=1\mid X_{<r}={\mathrm{\Psi }}_{<r},X_j=0)\le \varphi (X_r=1\mid X_{<r}={\mathrm{\Phi }}_{<r},X_j=0)\le \varphi (X_r=1\mid X_{<r}={\mathrm{\Phi }}_{<r}),$ provided ${\mathrm{\Psi }}_{<r}\le {\mathrm{\Phi }}_{<r}$. For $r>j$ the first comparison continues this reversed order. Hence $\mathrm{\Psi }(U_{-j},0)\le \mathrm{\Phi }(U_{-j},0)$ pointwise as well.

Since $A$ is increasing, the pointwise comparisons in step 3.1 imply, by elementary $(n-1)$-dimensional box integration, $F_j(C)\le \int {\mathbf{1}}_A(\mathrm{\Psi }(U_{-j},1))d{U}_{-j}-\int {\mathbf{1}}_A(\mathrm{\Psi }(U_{-j},0))d{U}_{-j}=I_A(j)\mathrm{.}$ The equality follows from the finite conditional chain rule: after the first, forced bit $j$, the reordered algorithm samples the successive conditional probabilities given that bit. Its output inverse images and their sections are finite boxes, exactly as in step 2.1, so the displayed integrals are finite volume sums. These are literal endpoint evaluations of the defined maps, not conditioning a uniform variable on a null-probability event.

Apply [F3] to $C$ from step 2.1, with $n=\mathrm{\mid }E\mathrm{\mid }\ge 2$ and $a=\varphi (A)$. For some $j$ its endpoint influence is at least $\varphi (A)(1-\varphi (A))\log n\mathrm{/}(4n)$. Step 4.1 bounds that influence above by $I_A(j)$, proving the stated inequality with $c(q,\epsilon )=1\mathrm{/}4$. All conditional laws used exist for every real $q\ge 1$ and $p\in [\epsilon ,1-\epsilon ]\subset (0,1)$.