Oczekiwany minimalny wpływ losowej funkcji boolowskiej

$f\colon\{-1,1\}^n \to \{-1,1\}$ $i$

{Inf}_{i} [f] \overset{d e f}{=} \underset{x \sim {- 1, 1}^{n}}{Pr} [f (x) \neq f (x^{\oplus i})]

$\operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})]$

x^{\oplus i}

$x^{\oplus i}$

i

$i$

x

$x$

f

$f$

MinInf [f] \overset{d e f}{=} min_{i \in [n]} {Inf}_{i} [f] .

$\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f].$

Biorąc pod uwagę parametr $p\in[0,1]$ , wybieramy funkcję $p$ losową $f$ , wybierając jej wartość na każdym z $2^n$ wejść niezależnie losowo, aby była równa $1$ z prawdopodobieństwem $p$ , a $-1$ z prawdopodobieństwem $1-p$ . Łatwo więc zauważyć, że dla każdego $i\in[n]$ nazwa

E_{f} [{Inf}_{i} [f]] = 2 p (1 - p)

$\mathbb{E}_{f}[\operatorname{Inf}_i[f]] = 2p(1-p)$ i tym bardziej

I_{n} (p) \overset{d e f}{=} E_{f} [MinInf [f]] \leq 2 p (1 - p) .

$I_n(p) \stackrel{\rm def}{=}\mathbb{E}_{f}[\operatorname{MinInf}[f]] \leq 2p(1-p).$

Moje pytanie brzmi:

Czy istnieje asymptotycznie (w odniesieniu do $n$ ) ścisłe wyrażenie dla $I_n(p)$ ? Nawet dla $p=\frac{1}{2}$ , czy możemy uzyskać takie wyrażenie?

W szczególności dbam o warunki niskiego rzędu, tj. Byłbym zainteresowany asymptotycznym odpowiednikiem dla ilości $2p(1-p)-I_n(p)$ .

(Kolejne pytanie, ale podporządkowane pierwszemu, dotyczy tego, czy można uzyskać dobre granice koncentracji wokół tego oczekiwania).

Przez granice Chernoffa można również pokazać, że każda nazwa ma dobrą koncentrację, dzięki czemu otrzymujemy granicę związkową (jeśli nie zepsułem zbyt mocno) ale to jest najprawdopodobniej luźno w dolnej granicy (z powodu związkowej granicy) i zdecydowanie w górnej granicy. (W szczególności szukam górnej granicy ściśle mniejszej niż trywialna ). $\operatorname{Inf}_i[f]$

\frac{1}{2} - O (\sqrt{\frac{n}{2^{n}}}) \leq I_{n} (\frac{1}{2}) \leq \frac{1}{2}

$\frac{1}{2} - O\left(\sqrt{\frac{n}{2^n}}\right) \leq I_n\left(\frac{1}{2}\right) \leq \frac{1}{2}$

\frac{1}{2}

$\frac{1}{2}$

Zauważ, że jednym z problemów przy tym, oprócz przyjęcia minimum identycznie rozmieszczonych zmiennych losowych (wpływów), jest to, że te zmienne losowe nie są niezależne ... chociaż spodziewam się, że ich korelacja zaniknie „dość szybko” z . $n$ $n$

(Dla tego, co jest warte, obliczyłem jawnie kilka pierwszych do i uruchomiłem symulacje, aby oszacować kolejne, do lub więcej. Nie jestem pewien, jak pomocne jest to może być, ale mogę to uwzględnić, gdy wrócę do mojego biura). $I_n(1/2)$ $n=4$ $n=20$

reference-request pr.probability boolean-functions Klemens C.
źródło

Oto kilka pierwszych (tylko pierwsze 4 są dokładne, pozostałe pochodzą z losowego próbkowania (w celu oszacowania wpływów) uśrednionych z 10 ^ 5 losowo wygenerowanych funkcji): (uwaga: w przypadku symulacji nie jestem pewien, czy 4. cyfra jest naprawdę znaczące)

\begin{aligned} 1 & 0.500 \\ 2 & 0.375 \\ 3 & 0.3359375 \\ 4 & 0.339141845703125 \\ 5 & 0.3623 \\ 6 & 0.3907 \\ 7 & 0.4166 \\ 8 & 0.4373 \\ 9 & 0.4535 \\ 10 & 0.4659 \\ 11 & 0.4751 \\ 19 & 0.4965 \\ 20 & 0.4967 \end{aligned}

$\begin{align}1 &\qquad 0.500\\ 2 &\qquad 0.375\\ 3 &\qquad 0.3359375\\ 4 &\qquad 0.339141845703125\\ 5 &\qquad 0.3623\\ 6 &\qquad 0.3907\\ 7 &\qquad 0.4166\\ 8 &\qquad 0.4373\\ 9 &\qquad 0.4535\\ 10 &\qquad 0.4659\\ 11 &\qquad 0.4751\\ 19 &\qquad 0.4965\\ 20 &\qquad 0.4967\\ \end{align}$

Clement C.

Odpowiedzi:

Oto krok we właściwym kierunku ...

Będę argumentować, że dla masz . $p=1/2$ $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$

(To nie jest tak silne, jak powinno być. Może ktoś może wzmocnić argument, aby pokazać .) Oto szkic dowodu. $\Omega(\sqrt{n/2^n})$

Wystarczy pokazać . My to robimy. $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$

Zauważ, że gdyby i były całkowicie niezależne, zrobilibyśmy to, ponieważ oczekiwanie minimum dwóch niezależnych sum wynosi . Po pierwsze, będziemy argumentować ostrożnie, że te dwie kwoty są prawie niezależne. $\text{Inf}_1[f]$ $\text{Inf}_2[f]$ $1/2-\Omega(\sqrt{1/2^n})$

Rozważ wszechświat punktów . Wywołaj i w sąsiadach, jeśli różnią się tylko tą współrzędną. Powiedz, że dwaj sąsiedzi przyczyniają się (do ), jeśli . (Więc to liczba współpracujących sąsiadów, podzielona przez ). Zauważ, że jeśli i są sąsiadami, i są -siedzi, a więc albo $X=\{-1,1\}^n$ $x$ $x'$ $X$ $i$ $i$ $\text{Inf}_i[f]$ $f(x) \ne f(x')$ $\text{Inf}_i[f]$ $i$ $2^{n-1}$ $x$ $x'$ $i$ $y$ $y'$ $i$ $\{x,x'\}=\{y,y'\}$ lub . Stąd liczba uczestniczących sąsiadów jest sumą niezależnych zmiennych losowych, każda z oczekiwaniami . $\{x,x'\}\cap\{y,y'\}=\emptyset$ $i$ $2^{n-1}$ $1/2$

Podziel wszechświat na grupy o rozmiarze czwartym, gdzie i są w tej samej grupie, iff i zgadzają się na wszystkich oprócz dwóch pierwszych współrzędnych. Następnie dla każdej pary 1-sąsiadów i każdej pary 2-sąsiadów i należą do tej samej grupy. Dla danej grupy i , niech rv być liczba przyczynia -neighbors w . Zatem na przykład liczba wszystkich 1-sąsiadów ogółem wynosi $X$ $2^{n-2}$ $x$ $x'$ $x$ $x'$ $(x,x')$ $(x,x')$ $x$ $x'$ $g$ $i\in\{1,2\}$ $c^g_i$ $i$ $g$ $\sum_g c^g_1$ , suma niezależnych zmiennych losowych, każda w . $2^{n-2}$ $\{0,1,2\}$

Zauważ, że i są niezależne, jeśli . Analiza przypadku, jeśli , wspólny rozkład i wynosi $c^g_1$ $c^{g'}_2$ $g\ne g'$ $g=g'$ $c^g_1$ $c^g_2$

\begin{array}{cccc} 0 & 1 & 2 \\ 0 & 1 / 8 & 0 & 1 / 8 \\ 1 & 0 & 1 / 2 & 0 \\ 2 & 1 / 8 & 0 & 1 / 8 \end{array}

$\begin{array}{c|ccc} & 0 & 1 & 2 \\ \hline 0 & 1/8 & 0 & 1/8 \\ 1 & 0 & 1/2 & 0 \\ 2 & 1/8 & 0 & 1/8 \\ \end{array}$

Niech rv oznacza zbiór grup neutralnych . (Wkładają dokładnie swoją oczekiwaną kwotę do wpływu 1 i wpływu 2). Liczba wnoszących 1 sąsiada wynosi wtedy $N=\{ g : c^g_1=c^g_2=1\}$

| N | + \sum_{g \in \bar{N}} c_{1}^{g} .

$|N| + \sum_{g\in \overline{N}} c^g_1.$

Uwarunkowane na , dla każdego rv i są niezależne (poprzez sprawdzenie ich wspólnego rozkładu powyżej), więc (uwarunkowane na ) wszystkie rv znajdują się równomiernie powyżej więc $N$ $g\in \overline N$ $c^g_1$ $c^g_2$ $N$ $\{c^g_i : i\in\{1,2\}, g\in\overline N\}$ $\{0,2\}$

E [| \bar{N} | - min (\sum_{g \in \bar{N}} c_{1}^{g}, \sum_{g \in \bar{N}} c_{2}^{g}) | N] \geq Θ (\sqrt{| \bar{N} |}) .

$\textstyle E\Big[|\overline N|- \min\big(\sum_{g\in \overline N} c^g_1, \sum_{g\in \overline N} c^g_2\big) ~\Big|~ N\Big] \ge \Theta(\sqrt{|\overline N|}).$

Na koniec zauważ, że każda grupa jest neutralna z prawdopodobieństwem 1/2, więc jest bardzo mały, powiedzmy (i nawet w takim przypadku lewa strona powyżej wynosi co najmniej ) . Z tego wynika twierdzona dolna granica ... $\Pr[|\overline N| \le 2^{n-2}/3]$ $\exp(-\Omega(2^n))$ $-2^n$

Neal Young
źródło

Dziękuję Ci! Spróbuję sprawdzić, czy istnieje sposób na dostosowanie twojego podejścia, aby uzyskać dodatkowe pod rootem ...

n

$n$

Clement C.