Maximum endpoint influence for an increasing finite-box set

The elementary integral is well-defined: adjoining an endpoint splits an interval into two whose lengths sum to its original length, so finite common refinement leaves each integral unchanged. Indicators of finite-box sets, their fixed-coordinate sections, and their finite products and differences are rectangular step functions. Common refinement proves linearity, positivity and the integral triangle inequality. It also proves equality of iterated and full integrals, because both sum the same finitely many cell values times products of lengths; outer grid endpoints have zero length. A translation preserves side lengths, so a piecewise translation bijectively exchanging finitely many boxes preserves these integrals. These are all the continuous-cube integration rules used below.

For $1\le p\le 2$ and real $u,v$, we prove $(u^2+(p-1)v^2{)}^{1\mathrm{/}2}\le ((\mathrm{\mid }u+v{\mathrm{\mid }}^p+\mathrm{\mid }u-v{\mathrm{\mid }}^p)\mathrm{/}2{)}^{1\mathrm{/}p}$. At $p=1$ this follows from the triangle inequality, and at $p=2$ it is equality. For $1<p<2$ signs can be removed. If $\mathrm{\mid }v\mathrm{\mid }>\mathrm{\mid }u\mathrm{\mid }$, interchange their absolute values: the right side is unchanged and the squared left side increases by $(2-p)(v^2-u^2)$. It therefore suffices to take $u>0$ and $0\le t=v\mathrm{/}u\le 1$, apart from the trivial zero case. For $t<1$ put $H(t)=((1+t{)}^p+(1-t{)}^p)\mathrm{/}2$. The convexity of $s^{p-2}$, obtained by two differentiations, gives $H^{\mathrm{\prime }\mathrm{\prime }}(t)\ge p(p-1)$. Since $H(0)=1$ and $H^{\mathrm{\prime }}(0)=0$, integration twice gives $H(t)\ge 1+p(p-1)t^2\mathrm{/}2$. Concavity of $s^{p\mathrm{/}2}$ gives $(1+(p-1)t^2{)}^{p\mathrm{/}2}\le 1+p(p-1)t^2\mathrm{/}2$. Multiply by $u^p$ and take the $p$th root; continuity includes $t=1$. This proves the claimed two-point inequality.

On a uniform bit $x\in \{-1,1\}$ define $T_{\rho }(u+vx)=u+\rho vx$, for $0\le \rho \le 1$. Step 1.2 with $p=1+{\rho }^2$ proves $\mathrm{\parallel }{T}_{\rho }h{\mathrm{\parallel }}_2\le \mathrm{\parallel }h{\mathrm{\parallel }}_p$. To extend this to $d$ bits, first note that finite-sum Minkowski gives $\mathrm{\parallel }h{\mathrm{\parallel }}_{L_y^2(L_x^p)}\le \mathrm{\parallel }h{\mathrm{\parallel }}_{L_x^p(L_y^2)}$ for finite probability spaces and $1\le p\le 2$: its $p$th-power form is the triangle inequality for ${\mathbb{E}}_x\mathrm{\mid }h(x,\cdot ){\mathrm{\mid }}^p$ in $L_y^{2\mathrm{/}p}$. For completeness, finite weighted Minkowski at exponent $r>1$ follows by multiplying $\mathrm{\mid }z+w\mathrm{\mid }\le \mathrm{\mid }z\mathrm{\mid }+\mathrm{\mid }w\mathrm{\mid }$ by $\mathrm{\mid }z+w{\mathrm{\mid }}^{r-1}$, summing, applying Hölder and dividing by $\mathrm{\parallel }z+w{\mathrm{\parallel }}_r^{r-1}$ if nonzero. Weighted Hölder follows by normalizing the two norms and summing Young's inequality $ab\le a^r\mathrm{/}r+b^{r^{\mathrm{\prime }}}\mathrm{/}{r}^{\mathrm{\prime }}$, which follows by minimizing $a^r\mathrm{/}r-ab$ in $a\ge 0$; zero norms and $r=1$ are immediate. If $T_X,T_Y$ contract $L^p$ into $L^2$ on two blocks, apply the $X$ contraction pointwise in $y$, the mixed-norm inequality, and then the $Y$ contraction pointwise in $x$ to obtain $\mathrm{\parallel }{T}_X{T}_{Y}h{\mathrm{\parallel }}_2\le \mathrm{\parallel }{T}_{Y}h{\mathrm{\parallel }}_{L_y^2(L_x^p)}\le \mathrm{\parallel }{T}_{Y}h{\mathrm{\parallel }}_{L_x^p(L_y^2)}\le \mathrm{\parallel }h{\mathrm{\parallel }}_p$. Induction therefore gives $\mathrm{\parallel }{T}_{\rho }h{\mathrm{\parallel }}_2\le \mathrm{\parallel }h{\mathrm{\parallel }}_{1+{\rho }^2}$ on every finite Boolean cube, where $T_{\rho }$ applies the one-bit operator in each coordinate.

Put $N=2^m$ for $m\ge 1$ and partition $[0,1{)}^n$ into the dyadic cells $Q_a={\prod }_i[a_i\mathrm{/}N,(a_i+1)\mathrm{/}N)$, with $0\le a_i<N$. On $Q_a$ let ${\mathrm{\ell }}_m=f(a\mathrm{/}N)$, $u_m=f((a+\mathbf{1})\mathrm{/}N)$ and $g_m=N^n{\int }_{Q_a}f$. Faces at coordinate one may be assigned arbitrary values for integration. Monotonicity gives ${\mathrm{\ell }}_m\le f,g_m\le u_m$. Telescope each difference $u_m-{\mathrm{\ell }}_m$ one coordinate at a time. For coordinate $i$, summation over $a_i$ at fixed remaining upper/lower corner coordinates telescopes to a difference of values at coordinate one and zero, at most one. There are $N^{n-1}$ choices of the other indices, hence $\int (u_m-{\mathrm{\ell }}_m)\le n\mathrm{/}N$ and ${\delta }_m:=\int \mathrm{\mid }{g}_m-f\mathrm{\mid }\le n\mathrm{/}N$. Cell averaging gives $\int g_m=\int f=a$, while $\mathrm{\mid }{g}_m^2-f^2\mathrm{\mid }\le 2\mathrm{\mid }{g}_m-f\mathrm{\mid }$. Therefore $\mathrm{\mid }\mathrm{Var}(g_m)-a(1-a)\mathrm{\mid }\le 2{\delta }_m\to 0$. This uses an explicit numerical error bound, not a theorem interchanging a limit and an integral.

On $\{-1,1{\}}^d$ let $x^{(j)}$ flip bit $j$ and set $D_{j}h=(h(x)-h(x^{(j)}))\mathrm{/}2$. Suppose numbers $b_j\in [0,1]$ satisfy $\mathrm{\parallel }{D}_{j}h{\mathrm{\parallel }}_p\le b_j^{1\mathrm{/}p}\mathrm{/}2$ for every $1\le p\le 2$. We will prove $\mathrm{Var}(h)\le {\sum }_j{b}_j\mathrm{/}(1+\log (1\mathrm{/}{b}_j))$, interpreting the summand at zero as zero. For $S\subseteq \{1,\dots ,d\}$ define ${\chi }_S(x)={\prod }_{j\in S}{x}_j$. Independence and zero mean of each bit show these $2^d$ functions are orthonormal. Since the function space has dimension $2^d$, they form a basis; write $h={\sum }_S\widehat{h}(S){\chi }_S$. Then $D_{j}h={\sum }_{S\ni j}\widehat{h}(S){\chi }_S$ and $T_{\rho }{\chi }_S={\rho }^{\mathrm{\mid }S\mathrm{\mid }}{\chi }_S$. Parseval and finite-sum integration yield the exact identity $\mathrm{Var}(h)=2{\sum }_j{\int }_0^1\mathrm{\parallel }{T}_{\rho }{D}_{j}h{\mathrm{\parallel }}_2^2\frac{d\rho }{\rho },$ because the coefficient of each $\widehat{h}(S{)}^2$ for nonempty $S$ is $2\mathrm{\mid }S\mathrm{\mid }{\int }_0^1{\rho }^{2\mathrm{\mid }S\mathrm{\mid }-1}d\rho =1$. These are ordinary one-variable Riemann integrals of finite polynomials after cancellation of the factor $\rho$; no singularity at zero occurs.

Identify each cell index $a_i$ with its $m$ binary digits, most significant first; the uniform distribution of the $nm$ bits is the uniform distribution of the equal-volume cells. Regard $g_m$ as a real function on this finite Boolean cube. For $1\le k\le m$, let $R_{ik}$ flip the $k$th binary digit of coordinate $i$ on $[0,1)$: in every prefix interval of length $2^{1-k}$ translate its lower half up by $2^{-k}$ and its upper half down by $2^{-k}$. Define it arbitrarily at coordinate one. This is a finite piecewise translation preserving elementary integrals, and it pairs the level-$m$ cells with that digit flipped. Let $b_{ik}=\int \mathrm{\mid }f-f\circ R_{ik}\mathrm{\mid }$. The bit derivative of $g_m$ on a cell is the cell average of $(f-f\circ R_{ik})\mathrm{/}2$. For such an average $z=\mathrm{\mid }Q{\mathrm{\mid }}^{-1}{\int }_Q(f-f\circ R_{ik})$, the finite triangle inequality gives $\mathrm{\mid }z\mathrm{\mid }\le \mathrm{\mid }Q{\mathrm{\mid }}^{-1}{\int }_Q\mathrm{\mid }f-f\circ R_{ik}\mathrm{\mid }\le 1$, so $\mathrm{\mid }z{\mathrm{\mid }}^p\le \mathrm{\mid }z\mathrm{\mid }$ for $p\ge 1$. Multiplying by $2^{-p}\mathrm{\mid }Q\mathrm{\mid }$ and summing cells yields $\mathrm{\parallel }{D}_{ik}{g}_m{\mathrm{\parallel }}_p^p\le 2^{-p}{b}_{ik}$, the hypothesis of step 3.1.

Write $D_{j}h=x_j{g}_j(x_{-j})$. The product noise operator gives $T_{\rho }{D}_{j}h=\rho x_j{T}_{\rho }{g}_j$, so step 2.1 and the norm hypothesis in step 3.1 imply $\mathrm{\parallel }{T}_{\rho }{D}_{j}h{\mathrm{\parallel }}_2^2\le {\rho }^2{b}_j^{2\mathrm{/}(1+{\rho }^2)}\mathrm{/}4$. For $b=b_j>0$ put $L=\log (1\mathrm{/}b)$. Its contribution to the integral in step 3.1 is at most $\frac{1}{2}{\int }_0^1\rho b^{2\mathrm{/}(1+{\rho }^2)}d\rho \le \frac{b}{4}{\int }_0^1{e}^{-Ls\mathrm{/}2}ds\le \frac{b}{1+L}\mathrm{.}$ The middle inequality substitutes $s=1-{\rho }^2$ and uses $2\mathrm{/}(1+{\rho }^2)\ge 1+(1-{\rho }^2)\mathrm{/}2$. The last integral is at most one, proving the last inequality when $0\le L\le 1$, and at most $2\mathrm{/}L$, proving it when $L\ge 1$. At $b_j=0$ the norm hypothesis gives $D_{j}h=0$. Summing establishes the variance estimate claimed in step 3.1.

Fix the coordinates other than $i$. The fiber indicator is an increasing zero-one function of one real variable, hence a threshold indicator except possibly at its threshold. If the endpoint values agree it is constant everywhere. Otherwise flipping the $k$th digit can change its value only in the single prefix interval of length $2^{1-k}$ containing the threshold. If the threshold is a prefix endpoint, disagreement at that endpoint has length zero; other intervals are constant. Thus the disagreement length is at most $2^{1-k}(f(x_{-i},1)-f(x_{-i},0))$. All these sections and disagreement sets are finite-box sets. Finite-sum iterated integration from step 1.1 gives $b_{ik}\le 2^{1-k}{F}_i$, and consequently ${\sum }_{k=1}^m{b}_{ik}\le 2F_i$ and $b_{ik}\le M$.

If $M=0$, steps 4.1–5.1 make every bit derivative of every $g_m$ zero, so every $g_m$ is constant, and step 2.2 gives $a(1-a)=0$. If $M>0$, apply the variance bound of step 4.2 to $g_m$, using steps 4.1–5.1. Each nonzero denominator is at least $1+\log (1\mathrm{/}M)$, giving $\mathrm{Var}(g_m)\le 2{\sum }_i{F}_i\mathrm{/}(1+\log (1\mathrm{/}M))$. Taking the limit with the explicit error in step 2.2 proves the first stated inequality.

If $0<M<n^{-1\mathrm{/}2}$, step 6.1 gives $a(1-a)\le 4nM\mathrm{/}\log n$, which is the required lower bound on $M$. If $M\ge n^{-1\mathrm{/}2}$, use $a(1-a)\le 1\mathrm{/}4$ and $\log n\le \sqrt{n}$ to get $a(1-a)\log n\mathrm{/}(4n)\le 1\mathrm{/}(16\sqrt{n})\le M$. The elementary bound $\log t\le \sqrt{t}$ for $t\ge 1$ follows by differentiating $(\log t)\mathrm{/}\sqrt{t}$: its maximum is $2\mathrm{/}e<1$. The case $M=0$ was settled in step 6.1. This proves the stated bound for every integer $n\ge 2$.