$$

Statement

Say you have some boolean-valued function $f:{\{\pm 1\}}^n\to \{\pm 1\}$ that is is not too biased, i.e. $\mathrm{Var}[f]\ge \mathrm{\Omega }(1)$. What can you say about its influences?

By Poincaré’s inequality, we know that the total influence $\mathrm{I}[f]$ is lower bounded by the variance, so at least one of the influences must be

$$\ge \mathrm{\Omega }\left(\frac{\mathrm{Var}[f]}{n}\right)\ge \mathrm{\Omega }\left(\frac{1}{n}\right).$$

The Kahn–Kalai–Linial theorem improves on this $\mathrm{\Omega }(1/n)$. It shows that when the total influence $\mathrm{I}[f]$ is small, then paradoxically one of the individual influences must be large:

$$\underset{i}{max}{\mathrm{Inf}}_i[f]\ge 2^{-O\left(\frac{\mathrm{I}[f]}{\mathrm{Var}[f]}\right)}\ge 2^{-O(\mathrm{I}[f])}.$$

We can then use this bound when $\mathrm{I}[f]<o(\log n)$ and use the trivial bound $\underset{i}{max}{\mathrm{Inf}}_i[f]\ge \mathrm{\Omega }\left(\frac{\mathrm{I}[f]}{n}\right)$ when $\mathrm{I}[f]\ge \mathrm{\Omega }(\log n)$ to get

$$\underset{i}{max}{\mathrm{Inf}}_i[f]\ge \mathrm{\Omega }\left(\frac{\log n}{n}\right).$$

Low variance

When the variance is very small, we can use the edge-isoperimetric inequality to get a better bound on $max{\mathrm{Inf}}_i[f]$. Say that $\mathrm{Pr}[f=1]=\alpha <1/2$, then $\mathrm{Var}[f]=\mathrm{\Theta }(\alpha )$ and

$$\mathrm{I}[f]\ge 2\alpha \log (1/\alpha ),$$

so

$$max{\mathrm{Inf}}_i[f]\ge \frac{\mathrm{I}[f]}{n}=\mathrm{Var}[f]\cdot \mathrm{\Omega }\left(\frac{\log (1/\alpha )}{n}\right)=\mathrm{Var}[f]\cdot \mathrm{\Omega }\left(\frac{\log \frac{1}{\mathrm{Var}[f]}}{n}\right).$$

This beats KKL when $\mathrm{Var}[f]=n^{-\omega (1)}$. Overall, the “scaled influence” (which corresponds to the average sensitivity over the smaller of the two halves $f^{-1}(1)$ and $f^{-1}(-1)$) is on the order of

$$\frac{\underset{i}{max}{\mathrm{Inf}}_i[f]}{\mathrm{Var}[f]}=\mathrm{\Omega }\left(\frac{max(\log n,\log \frac{1}{\mathrm{Var}[f]})}{n}\right).$$

This is tight for the tribes function.

Proof

We give two proofs, which only differ in the “midpoint” they pick

• the first looks at the stable total influence ${\mathrm{I}}^{(\rho )}[f]$, and is the most intuitive;
• the second goes deeper down to the norms of the derivatives ${\mathrm{D}}_{i}f$, and makes clear exactly where we use the fact that $f$ outputs boolean values.

By stable influence

In summary:

• if the total influence is small, then it must be stable;
• but small influences are unstable under noise;
• so there must be some large influences.

Recall that the total influence is the “expected degree” (weighted by Fourier weight)

$$\mathrm{I}[f]=\sum k\cdot {\mathbf{W}}^k[f],$$

whereas the variance represents the amount of weight at positive degree

$$\mathrm{Var}[f]=\sum _{k=1}^n{\mathbf{W}}^k[f].$$

Intuitively, the fact that $\mathrm{I}[f]$ is not too large but $\mathrm{Var}[f]$ is significant tells us that there must be a lot of weight at low but positive degree, which should make the stable influence not too small.

Concretely, by Markov’s inequality, there can’t be more than $\frac{\mathrm{Var}[f]}{2}$ weight above degree $\frac{2\mathrm{I}[f]}{\mathrm{Var}[f]}$ (otherwise the total influence would be larger). This means that there is at least $\frac{\mathrm{Var}[f]}{2}$ weight between degrees $1$ and $\frac{2\mathrm{I}[f]}{\mathrm{Var}[f]}$, and therefore we can lower bound (say) the $1/3$-stable total influence by

$$\stackrel{(1/3)}{\mathrm{I}}[f]=\sum 3^{-k+1}k\cdot {\mathbf{W}}^k[f]\ge \left(3^{-\frac{2\mathrm{I}[f]}{\mathrm{Var}[f]}+1}\frac{2\mathrm{I}[f]}{\mathrm{Var}[f]}\right)\frac{\mathrm{Var}[f]}{2}\ge 9^{-\frac{\mathrm{I}[f]}{\mathrm{Var}[f]}}\mathrm{I}[f].$$

In particular, as long as $\mathrm{Var}[f]\ge \mathrm{\Omega }(1)$ and $\mathrm{I}[f]\le O(1)$, we have ${\mathrm{I}}^{(1/3)}[f]\ge \mathrm{\Omega }(1)$.

On the other hand, by small-set expansion, we know that small influences are unstable:

$${\mathrm{Inf}}_i^{(1/3)}[f]\le {\mathrm{Inf}}_i[f{]}^{3/2},$$

so if every influence is small, the total stable influence must be small compared to the total influence:

$$\stackrel{(1/3)}{\mathrm{I}}[f]=\sum {\mathrm{Inf}}_i^{(1/3)}[f]\le \sum {\mathrm{Inf}}_i[f{]}^{3/2}\le \mathrm{I}[f]\cdot \underset{i}{max}{\mathrm{Inf}}_i[f{]}^{1/2}.$$

Combining both bounds, we get

$$\underset{i}{max}{\mathrm{Inf}}_i[f]\ge {81}^{-\frac{\mathrm{I}[f]}{\mathrm{Var}[f]}}.$$

By derivative norms

To be completely honest, this turned out less insightful than I’d hoped.

For simplicity, here let’s assume that $\mathrm{Var}[f]\ge \mathrm{\Omega }(1)$ and $\mathrm{I}[f]\le O(1)$, which we already show implies that the stable influence is large: ${\mathrm{I}}^{(1/3)}\ge \mathrm{\Omega }(1)$. We want to show that $\underset{i}{max}{\mathrm{Inf}}_i[f]\ge \mathrm{\Omega }(1)$.

The stable influences are defined as the stability of the corresponding derivative, which by hypercontractivity we can upper bound by a lower-order¹ norm:

$${\mathrm{Inf}}_i^{(1/3)}[f]={\mathrm{Stab}}_{1/3}[{\mathrm{D}}_{i}f]\le {\Vert {\mathrm{D}}_{i}f\Vert }_{4/3}^2=\mathrm{E}{[|{\mathrm{D}}_{i}f(\mathit{x}){|}^{4/3}]}^{3/2},$$

so we overall get

$$\sum \mathrm{E}{[|{\mathrm{D}}_{i}f(\mathit{x}){|}^{4/3}]}^{3/2}\ge \stackrel{(1/3)}{\mathrm{I}}[f]\ge \mathrm{\Omega }(1).$$

On the other hand, the second-order norm of ${\mathrm{D}}_{i}f$ gives the influence:

$${\mathrm{Inf}}_i[f]={\Vert {\mathrm{D}}_{i}f\Vert }_2^2=\mathrm{E}\left[|{\mathrm{D}}_{i}f{|}^2\right],$$

so we have

$$\sum \mathrm{E}{[|{\mathrm{D}}_{i}f(\mathit{x}){|}^2]}^{3/2}\le \mathrm{I}[f]\cdot \underset{i}{max}{\mathrm{Inf}}_i[f{]}^{1/2}\le O(\underset{i}{max}{\mathrm{Inf}}_i[f{]}^{1/2}).$$

So far, everything we’ve said applies equally to real-valued functions. For those, there is nothing contradictory with having $\sum \mathrm{E}{[|{\mathrm{D}}_{i}f(\mathit{x}){|}^2]}^{3/2}$ being much smaller than $\sum \mathrm{E}{[|{\mathrm{D}}_{i}f(\mathit{x}){|}^{4/3}]}^{3/2}$. Indeed, this would be the case if ${\mathrm{D}}_{i}f$ often takes small (but nonzero) values, which get crushed by squaring but not crushed as much by raising to the power $4/3$. And indeed, the last section gives a function for which this is the case.

The key thing is that when $f$ has boolean outputs, then ${\mathrm{D}}_{i}f(x)$ is always in $\{-1,0,1\}$, so it doesn’t matter which power you take:

$$\mathrm{E}[|{\mathrm{D}}_{i}f(\mathit{x}){|}^{4/3}]=\mathrm{E}[|{\mathrm{D}}_{i}f(\mathit{x}){|}^2]=\mathrm{Pr}[{\mathrm{D}}_{i}f(\mathit{x})\ne 0].$$

Therefore, you can combine the two inequalities and get

$$\underset{i}{max}{\mathrm{Inf}}_i[f{]}^{1/2}\ge \mathrm{\Omega }(1).$$

This is false for real-valued functions

Consider $f(x):={(1+\frac{x_i}{\sqrt{n}})}^n$. This is the relative density of $\mathit{X}$ where each ${\mathit{X}}_i$ is an independent Bernoulli of mean $\frac{1+1/\sqrt{n}}{2}$.

It’s clear from its expression that $\hat{f}(S)={\left(\frac{1}{\sqrt{n}}\right)}^{|S|}$, so the influences are

$${\mathrm{Inf}}_i[f]=\sum _{S\ni i}\hat{f}(S{)}^2=\sum _{k=1}^n\frac{(\genfrac{}{}{0ex}{}{n-1}{k-1})}{n^k}\le \sum _{k=1}^n\frac{1}{n}{\left(\frac{e}{k-1}\right)}^{k-1}\le O(1/n),$$

while the variance is

$$\mathrm{Var}[f]=\mathrm{E}[f^2]-\mathrm{E}[f{]}^2=\sum _S\hat{f}(S{)}^2-\hat{f}(\mathrm{\varnothing }{)}^2={(1+\frac{1}{n})}^n-1^2\approx e-1\ge \mathrm{\Omega }(1),$$

so $f$ doesn’t satisfy KKL.

Similarly, by independence, the entropy deficit $\mathrm{D}\left[\mathit{X}\right]$ is $\sum \mathrm{D}\left[{\mathit{X}}_i\right]=\mathrm{\Theta }(1)$ and the influence-like quantities $\mathrm{D}\left[{\mathit{X}}_i\right|{\mathit{X}}_{[n]\setminus \left\{i\right\}}]$ are $\mathrm{D}\left[{\mathit{X}}_i\right]=\mathrm{\Theta }(1/n)$.

1. The stability multiplies the function with (a noisy version) of itself, so we can see it as a kind of squared $2$-norm, whereas $\mathrm{E}{[({\mathrm{D}}_{i}f{)}^{4/3}]}^{3/2}$ is the squared $4/3$-norm. ↩