Influência mínima esperada de uma função booleana aleatória

Para uma função booleana $f\colon\{-1,1\}^n \to \{-1,1\}$ , a influência do $i$ th variável é definida como

{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})]$ onde

x^{\oplus i}

$x^{\oplus i}$ é a string obtida ao virar o

i

$i$ ésimo bit de

x

$x$ . A influência mínima de

f

$f$ é então

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].$

Dado um parâmetro , escolhemos uma função aleatória escolhendo seu valor em cada uma das entradas independentemente aleatoriamente para ser com probabilidade e com probabilidade . Em seguida, é fácil de ver que, para cada $p\in[0,1]$ $p$ $f$ $2^n$ $1$ $p$ $-1$ $1-p$ $i\in[n]$ ea fortiori

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

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

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).$

Minha pergunta é:

Existe uma expressão apertada assintoticamente (em relação a ) para ? Mesmo para $n$ $I_n(p)$ , podemos obter essa expressão? $p=\frac{1}{2}$

Especificamente, eu me preocupo com os termos de ordem baixa, ou seja, eu estaria interessado em um equivalente assintótico para a quantidade . $2p(1-p)-I_n(p)$

(A próxima pergunta, mas subordinada à primeira, é se é possível obter bons limites de concentração em torno dessa expectativa.)

Por Chernoff limita também se pode mostrar que cada tem boa concentração, de modo que por um sindicato ligado obtemos (se não o fiz asneira muito mal) $\operatorname{Inf}_i[f]$ mas isso provavelmente está solto no limite inferior (devido ao limite da união) e definitivamente no limite superior. (Em particular, estou procurando um limite superior estritamente menor que o trivial

\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}$

Observe que um dos problemas ao fazer isso, além de pegar o mínimo de variáveis aleatórias distribuídas de forma idêntica (as influências), é que essas variáveis aleatórias não são independentes ... embora eu espere que a correlação entre elas decaia "muito rápido" com . $n$ $n$

(Por que vale a pena, eu ter calculado explicitamente os primeiros é até , e ter executado simulações para estimar os seguintes, até ou assim. Não sei como útil pode ser, mas posso incluir isso quando voltar ao meu escritório.) $I_n(1/2)$ $n=4$ $n=20$

reference-request pr.probability boolean-functions Clemente C.
fonte

Aqui estão os primeiros (apenas os 4 primeiros são exatos, os outros são de amostragem aleatória (para estimar as influências) com média de 10 ^ 5 funções geradas aleatoriamente):

(nota: para as simulações, não tenho certeza o quarto dígito é realmente significativo)

\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.

Respostas:

Aqui está um passo na direção certa ...

Vou argumentar que para , você tem $p=1/2$ . $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$

(Isso não é tão forte quanto deveria ser. Talvez alguém possa fortalecer o argumento para mostrar .) Aqui está um esboço de prova. $\Omega(\sqrt{n/2^n})$

É suficiente para mostrar . Nós fazemos isso. $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$

Observe que se e $\text{Inf}_1[f]$ eram completamente independentes, teríamos ser feito porque a expectativa do mínimo das duas somas independentes é $\text{Inf}_2[f]$ . Primeiro, discutiremos cuidadosamente que as duas somas são quase independentes. $1/2-\Omega(\sqrt{1/2^n})$

Considere o universo dos pontos . Chamada e em -neighbors se diferirem apenas o th coordenadas. Digamos que os dois vizinhos contribuam (para ) se . (Então é o número de contribuições $X=\{-1,1\}^n$ $x$ $x'$ $X$ $i$ $i$ $\text{Inf}_i[f]$ $f(x) \ne f(x')$ $\text{Inf}_i[f]$ $i$ (vizinhos, dividido por ). Observe que, se e são vizinhos, e e são vizinhos, então ou . Portanto, o número de contribuintes $2^{n-1}$ $x$ $x'$ $i$ $y$ $y'$ $i$ $\{x,x'\}=\{y,y'\}$ $\{x,x'\}\cap\{y,y'\}=\emptyset$ $i$ -neighbors é a soma de variáveis aleatórias independentes, cada um com expectativa . $2^{n-1}$ $1/2$

Divida o universo em grupos de tamanho quatro, onde e estão no mesmo grupo se e concordarem com todas, exceto as duas primeiras coordenadas. Então, para cada par de 1 vizinho e cada par de 2 vizinhos, e estão no mesmo grupo. Para um determinado grupo e $X$ $2^{n-2}$ $x$ $x'$ $x$ $x'$ $(x,x')$ $(x,x')$ $x$ $x'$ $g$ , deixar rv ser o número de contribuir $i\in\{1,2\}$ $c^g_i$ $i$ -neighbors em . Então, por exemplo, o número total de vizinhos 1 contribuintes é , uma soma de variáveis aleatórias independentes, cada uma em . $g$ $\sum_g c^g_1$ $2^{n-2}$ $\{0,1,2\}$

$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}$

Let r.v. $N=\{ g : c^g_1=c^g_2=1\}$ denote the set of neutral groups. (They contribute exactly their expected amount to the 1-influence and the 2-influence.) The number of contributing 1-neighbors is then

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

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

Conditioned on $N$ , for each $g\in \overline N$ r.v.'s $c^g_1$ and $c^g_2$ are independent (by inspection of their joint distribution above), so (conditioned on $N$ ) all r.v.'s $\{c^g_i : i\in\{1,2\}, g\in\overline N\}$ are i.i.d. uniformly over $\{0,2\}$ so,

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|}).$

Finally, note that each group is neutral with probability 1/2, so $\Pr[|\overline N| \le 2^{n-2}/3]$ is extremely small, say $\exp(-\Omega(2^n))$ (and even in that case the left-hand-side above is at least $-2^n$ ). From this the claimed lower bound follows...

Neal Young
fonte

Thank you! I'll try and see if there is a way to adapt your approach get an additional

n

$n$ under the root...

Clement C.