Losowe ograniczenia i związek z całkowitym wpływem funkcji boolowskich

Powiedzmy, że mamy funkcję boolowską $f:\{-1,1\}^n\rightarrow \{-1,1\}$ i aplikujemy $\delta$-losowe ograniczenie na $f$. Ponadto powiedz, że drzewo decyzyjne$T$ to oblicza $f$ zmniejsza się $O(1)$w wyniku losowego ograniczenia. Czy to implikuje to$f$ ma bardzo niski wpływ całkowity?

Roszczenie: Jeśli$\delta$-losowe ograniczenie $f$ ma drzewo decyzyjne wielkości $O(1)$ (w oczekiwaniu), a następnie całkowity wpływ takich $f$ jest $O(\delta^{-1})$.

Szkic dowodu: z definicji mamy wpływ $Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)]$. Przyjmijmy górną granicę , stosując najpierw ograniczenie , a następnie wybierając spośród pozostałych współrzędnych i ustawiając na losowo wszystko oprócz .$\Pr_{x,i}[f(x) \neq f(x+e_i)]$$\delta$$i \in [n]$$x_i$

Otóż, jeśli -ograniczenie ogranicza drzewo decyzyjne do rozmiaru , to w szczególności ograniczenie zależy od skoordynowanego . Wybierzmy teraz jedną losową nieusuniętą współrzędną (między ) i naprawmy wszystkie pozostałe losowo. Ponieważ -ograniczenie zależy w większości współrzędnych, otrzymujemy funkcję (na jeden bit), który nie jest stały w prawdopodobieństwa najwyżej . Dlatego , zgodnie z wymaganiami.$\delta$$f$$O(1)$$\delta$$f$$r = O(1)$$\delta n$$\delta$$f$$r$$\frac{r}{\delta n}$$Inf(f) = n \cdot \Pr_{x,i}[f(x) \neq f(x+e_i)] \leq \frac{r}{\delta}$

Uwaga: Powyższe twierdzenie jest ścisłe, biorąc funkcję parzystości na bitach .$O(1/\delta)$