Influence, noise, stability - Analysis of Boolean Functions

2 Influence, noise, stability

Definition (Influence). Let $f : {0, 1}^{n} \to {0, 1}$ . The influence of the $i$ -th variable, ${Inf}_{i} f$ , is the probability (for a random $x$ ) that changing $x_{i}$ changes the value of $f$ . The total influence $I (f)$ of $f$ is $\sum_{i} {Inf}_{i} f$ .

Remark. Up to normalisation, the total influence is the edge boundary of the support of $f$ .

Notation. We define $D_{i} f (x) = f (x_{1}, \dots, x_{i - 1} 1, x_{i + 1}, \dots, x_{n}) - f (x_{1}, \dots, x_{i - 1}, 0, x_{i + 1}, \dots, x_{n})$ . We shall write $x_{i \to t}$ for $(x_{1}, \dots, x_{i - 1}, t, x_{i + 1}, \dots, x_{n})$ .

If $f : {0, 1}^{n} \to {0, 1}$ , then

{Inf}_{i} f = 𝔼_{x} D_{i} f {(x)}^{2} = ∥ D_{i} f ∥_{2}^{2} .

If $f : {- 1, 1}^{n} \to ℝ$ , then we define

D_{i} f (x) = \frac{1}{2} (f (x_{i \to 1}) - f (x_{i \to - 1})) .

The factor $\frac{1}{2}$ is so that $D_{i} f$ takes values in ${- 1, 0, 1}$ when $f$ takes values in ${- 1, 1}$ .

Again, ${Inf}_{i} f = ∥ D_{i} f ∥_{2}^{2}$ , and $I (f) = \sum_{i} {Inf}_{i} (f)$ .

If $f = x_{A}$ , then

D_{i} f (x) = {\begin{matrix} 0 & i \notin A \\ \frac{x_{A ∖ {i}} - (- x_{A ∖ {i}}}{2} = x_{A ∖ {i}} & i \in A \end{matrix}

So in general,

D_{i} f = D_{i} (\sum_{A} \hat{f} (A) x_{A}) = \sum_{A ∋ i} \hat{f} (A) x_{A ∖ {i}} .

Therefore (by orthogonality),

{Inf}_{i} f = ∥ D_{i} (f) ∥_{2}^{2} = \sum_{A ∋ i} \hat{f} {(A)}^{2}

and

I (f) = \sum_{i} \sum_{A ∋ i} \hat{f} {(A)}^{2} = \sum_{A} | A | \hat{f} {(A)}^{2} .

Definition 2.1. Let $ρ \in [- 1, 1]$ . If $x \in {- 1, 1}^{n}$ , we say that $y \sim N_{ρ} (x)$ if for each $i$ ,

y_{i} = {\begin{matrix} x_{i} & probability \frac{1 + ρ}{2} \\ - x_{i} & probability \frac{1 - ρ}{2} \end{matrix}

(Equivalently: if $ρ \geq 0$ , then with probability $ρ$ take $y_{i} = x_{i}$ and with probability $1 - ρ$ take $y_{i}$ random.)

All choices independent.

If $x$ is uniform and $y \sim N_{ρ} (x)$ , then $y$ is uniform and $x \sim N_{ρ} (y)$ . In this case, we write $x \sim_{ρ} y$ and say that $x$ and $y$ are $ρ$ -correlated.

Definition 2.2. If $ρ \in [- 1, 1]$ , then the noise operator $T_{ρ}$ takes a function $f : {- 1, 1}^{n} \to ℝ$ to $T_{ρ} f$ , defined by $T_{ρ} f = 𝔼_{y \sim N_{ρ} (x)} f (y)$ .

Remark. This is a convolution: $T_{ρ} f$ is a convolution of $f$ with a particular probability measure. So we should expect a nice formula about its Fourier coefficients.

Reminder: $x_{A} = \prod_{i \in A} x_{i}$ .

\begin{array}{l} T_{ρ} & = 𝔼_{y \in N_{ρ} (x)} y_{A} \\ = 𝔼_{y \sim N_{ρ} (x)} \prod_{i \in A} y_{i} \\ = \prod_{i \in A} 𝔼_{y \sim N_{ρ} (x)} y_{i} \\ = \prod_{i \in A} (\frac{1 + ρ}{2} x_{i} + \frac{1 - ρ}{2} (- x_{i})) \\ = \prod_{i \in A} (ρ x_{i}) \\ = \prod^{| A |} x_{A} \end{array}

Therefore, by the inversion formula,

T_{ρ} f = T_{ρ} (\sum_{A} \hat{f} (A) x_{A}) = \sum_{A} ρ^{| A |} \hat{f} (A) x_{A},

\hat{T_{ρ} f} (A) = ρ^{| A |} \hat{f} (A) .

Definition 2.3. Let $ρ \in [- 1, 1]$ and let $f : {- 1, 1}^{n} \to ℝ$ . Then

\begin{array}{l} {Stab}_{ρ} (f) & = 𝔼_{x \sim_{ρ} y} f (x) f (y) \\ = 𝔼_{x} f (x) 𝔼_{y \sim N_{ρ (x)}} f (y) \\ = 𝔼_{x} f (x) T_{ρ} f (x) \\ = ⟨ f, T_{ρ} f ⟩ \\ = ⟨ \hat{f}, \hat{T_{ρ} f} ⟩ \\ = \sum_{A} ρ^{| A |} \hat{f} {(A)}^{2} \end{array}