$$

Adapted from Sections 2.2-2.4 of “Analysis of Boolean Functions” by Ryan O’Donnell.

See also: Influences of decision trees

Influence

Intuition

Influences measure how much a function changes depending on its variables. Higher amplitude and higher degree make the total influence bigger.

TODO: #figure of low-frequency high-amplitude, high frequency low amplitude, high degree high influence

Definition

For a boolean-valued function $f:{\{\pm 1\}}^n\to \{\pm 1\}$, the influence of $i$ is the probability that flipping the $i^{\text{th}}$ coordinate changes the output:

$${\mathrm{Inf}}_i[f]:=\mathrm{Pr}[f({\mathit{x}}^{\oplus i})\ne f(\mathit{x})].$$

More generally, for a real-valued $f:{\{\pm 1\}}^n\to \mathbb{R}$, we can define the derivative

$${\mathrm{D}}_{i}f(x):=\frac{f(x^{i\leftarrow 1})-f(x^{i\leftarrow -1})}{2}$$

(where $x^{i\leftarrow b}$ means $x$ with its $i^{\text{th}}$ coordinate set to $b$), and let¹

$${\mathrm{Inf}}_i[f]:={\Vert {\mathrm{D}}_{i}f\Vert }_2^2=\mathrm{E}[{\mathrm{D}}_{i}f(\mathit{x}{)}^2].$$

The influence of $i$ is the sum of the Fourier weights involving $i$:

$${\mathrm{Inf}}_i[f]=\sum _{S\ni i}\hat{f}(S{)}^2.$$

Total influence

The total influence is the sum of the individual influences, and is equal to the average sensitivity (when $f$ is boolean-valued):

$$\mathrm{I}[f]:=\sum {\mathrm{Inf}}_i[f]=\mathrm{E}\left[\mathrm{\#}\{i\mid f({\mathit{x}}^{\oplus i})\ne f(\mathit{x})\}\right].$$

Monomials contribute to the total influence in proportion to their degree:

$$\mathrm{I}[f]=\sum |S|\hat{f}(S{)}^2=\sum k\cdot {\mathbf{W}}^k[f].$$

Properties

Let $f$ be boolean-valued, and let $\alpha =\mathrm{Pr}[f=1]$.

• Poincaré’s inequality lower bounds the total influence by the variance $\mathrm{Var}[f]=4\alpha (1-\alpha )$.
• The edge-isoperimetric inequality gives a tighter bound $\mathrm{I}[f]\ge 2\alpha \log \frac{1}{\alpha }$ when $\alpha \le 1/2$.

Stable influence

Intuition

Stable influences are influences that can survive noise. Influences due to low-degree are fairly stable under noise.

TODO: #figure of periodic function with low frequency not being hit too hard by noise

On the other hand, influences due to high-degree will get completely destroyed by noise.

TODO: same #figure but with high frequence

Definition

The $\rho$-stable influence of $i$ is given by the stability of the derivative, instead of its weight $\mathrm{E}[{\mathrm{D}}_i{f}^2]$. It is proportional to the influence of the smoothed ${\mathrm{T}}_{\rho }f$:

$${\mathrm{Inf}}_i^{(\rho )}[f]:={\mathrm{Stab}}_{\rho }[{\mathrm{D}}_{i}f]=\frac{{\mathrm{Inf}}_i[{\mathrm{T}}_{\rho }f]}{\rho }.$$

It is also the sum of the Fourier weights involving $i$, but with an exponential penalty on degree:

$${\mathrm{Inf}}_i^{(\rho )}[f]=\sum _{S\ni i}{\rho }^{|S|-1}\hat{f}(S{)}^2.$$

Intuitively, we’ll say “the influence of $i$ is stable” if the noise didn’t dicrease its influence too much; that is, the ratio $\frac{{\mathrm{Inf}}_i^{(\rho )}[f]}{{\mathrm{Inf}}_i[f]}$ is not too small. This is the case if $i$’s influence was mostly due to low degree: most of the weight of $S\ni i$ was from small $|S|$.

Total stable influence

The total stable influence is proportional to the total influence of the smoothed ${\mathrm{T}}_{\rho }f$:

$$\stackrel{(\rho )}{\mathrm{I}}[f]:=\sum {\mathrm{Inf}}_i^{(\rho )}[f]=\frac{\mathrm{I}[{\mathrm{T}}_{\rho }f]}{\rho }.$$

It has a similar formula as total influence, but again with an exponential penalty on degree:

$$\stackrel{(\rho )}{\mathrm{I}}[f]=\sum {\rho }^{|S|-1}|S|\hat{f}(S{)}^2=\sum {\rho }^{k-1}k\cdot {\mathbf{W}}^k[f].$$

Properties

Total stable influence is small

The total stable influence of a boolean-valued function can never be too large:

$$\stackrel{(1-\delta )}{\mathrm{I}}[f]\le \frac{\mathrm{Var}[f]}{\delta }\le \frac{1}{\delta }.$$

This is because the noise will dampen any weight on degrees bigger than $1/\delta$. As a result, there are never too many variables with large stable influence:

$$\mathrm{\#}\left\{i\right|{\mathrm{Inf}}_i^{(1-\delta )}[f]\ge ϵ\}\le \frac{\mathrm{Var}[f]}{\delta ϵ}.$$

In other words, after applying smoothing noise $\delta$, there are few remaining variables with significant influence.

Small influences are unstable

If $f$ is boolean-valued, then by applying small-set expansion on the derivative ${\mathrm{D}}_{i}f$, we can show that small influences are unstable:

$${\mathrm{Inf}}_i^{(\rho )}[f]\le {\mathrm{Inf}}_i[f{]}^{\frac{2}{1+\rho }}\Rightarrow \underset{\text{``stability of }{i}^{\text{th}}\text{ influence''}}{\underbrace{\frac{{\mathrm{Inf}}_i^{(1-\delta )}[f]}{{\mathrm{Inf}}_i[f]}}}\le {\mathrm{Inf}}_i[f{]}^{\mathrm{\Omega }(\delta )}.$$

And summing this up over $i$,

$$\underset{\text{``stability of total influence''}}{\underbrace{\frac{{\mathrm{I}}^{(1-\delta )}[f]}{\mathrm{I}[f]}}}\le \underset{i}{max}{\mathrm{Inf}}_i[f{]}^{\mathrm{\Omega }(\delta )}.$$

This is used in the proof of the Kahn–Kalai–Linial theorem to show that at least one of the influences must be large.

1. Note that if we define a function with outputs in $\{0,1\}$, then the boolean-output definition of $\mathrm{Pr}[f({\mathit{x}}^{\oplus i})\ne f(\mathit{x})]$ is four times bigger than the real-output definition $\mathrm{E}[{\mathrm{D}}_{i}f(\mathit{x}{)}^2]$. Let’s cheerily sweep this issue under the rug. ↩