Restrições aleatórias e a conexão com a influência total das funções booleanas

Digamos que temos uma função booleana $f:\{-1,1\}^n\rightarrow \{-1,1\}$ e aplicamos a restrição aleatória $\delta$ em $f$ . Além disso, diga que a árvore de decisão $T$ que calcula $f$ diminui para o tamanho $O(1)$ como resultado da restrição aleatória. Isso implica que $f$ tem uma influência total muito baixa?

Reivindicação: Se a restrição aleatória de f tem uma árvore de decisão do tamanho O ( 1 ) (em expectativa), então a influência total de tal f é O ( δ - 1 ) .$\delta$$f$$O(1)$$f$$O(\delta^{-1})$

Esboço prova: Por definição de influência que temos . Vamos limite superior Pr x , i [ f ( x ) ≠ f ( x + e i ) ] em primeiro lugar, aplicando uma δ -restriction, em seguida, escolhendo i $Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)]$$\Pr_{x,i}[f(x) \neq f(x+e_i)]$$\delta$ entre as coordenadas restantes, e corrigindo aleatoriamente tudo, exceto x i .$i \in [n]$$x_i$

Agora, se a restrição de reduz a árvore de decisão de f para o tamanho O ( 1 ) , em particular a restrição de δ de f depende de r = O ( 1 ) coordenado. Vamos agora escolher uma coordenada não fixa aleatória (entre δ n ) e corrigir todas as outras aleatoriamente. Como a restrição de δ de f depende de no máximo r coordenadas, obtemos uma função (em um bit) que não é constante com probabilidade no máximo $\delta$$f$$O(1)$$\delta$$f$$r = O(1)$$\delta n$$\delta$$f$$r$ . PortantoInf(f)=n⋅Prx,i[f(x)≠f(x+ei)]≤$\frac{r}{\delta n}$ , conforme necessário.$Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)] \leq \frac{r}{\delta}$

Observação: a reivindicação acima é rigorosa ao assumir uma função de paridade nos bits .$O(1/\delta)$