Influencia mínima esperada de una función booleana aleatoria

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

Dado un parámetro $p\in[0,1]$ , elegimos una función $p$ aleatoria $f$ eligiendo su valor en cada una de las $2^n$ entradas independientemente al azar para que sea $1$ con probabilidad $p$ , y $-1$ con probabilidad $1-p$ . Entonces, es fácil ver que, por cada $i\in[n]$

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

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

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

Mi pregunta es:

¿Existe una expresión apretada asintóticamente (con respecto a ) para ? Incluso para , ¿podemos obtener tal expresión? $n$ $I_n(p)$ $p=\frac{1}{2}$

Específicamente, me importan los términos de orden inferior, es decir, me interesaría un equivalente asintótico para la cantidad . $2p(1-p)-I_n(p)$

(La siguiente pregunta, pero que está subordinada a la primera, es si uno también puede obtener buenos límites de concentración en torno a esta expectativa).

Según los límites de Chernoff, también se puede mostrar que cada tiene buena concentración, de modo que por un límite de unión obtenemos (si no me equivoqué demasiado) pero esto es Lo más probable es que se suelte en el límite inferior (debido a la unión) y definitivamente en el límite superior. (En particular, estoy buscando un límite superior estrictamente menor que el trivial ). $\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}$

Tenga en cuenta que uno de los problemas al hacer eso, además de tomar el mínimo de variables aleatorias distribuidas de forma idéntica (las influencias), es que estas variables aleatorias no son independientes ... aunque sí espero que su correlación decaiga "bastante rápido" con . $n$ $n$

(Para lo que vale, he calculado explícitamente los primeros hasta , y he realizado simulaciones para estimar los siguientes, hasta o menos. No estoy seguro de qué tan útil es esto podría ser, pero puedo incluir eso una vez que vuelva a mi oficina). $I_n(1/2)$ $n=4$ $n=20$

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

Aquí están los primeros pocos (solo los primeros 4 son exactos, los otros son de muestreo aleatorio (para estimar las influencias) promediados sobre 10 ^ 5 funciones generadas aleatoriamente): (nota: para las simulaciones, no estoy seguro de que el cuarto dígito sea 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}$

Clemente C.

Respuestas:

Aquí hay un paso en la dirección correcta ...

Voy a argumentar que para , tiene $p=1/2$ . $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$

(Esto no es tan fuerte como debería ser. Quizás alguien pueda fortalecer el argumento para mostrar .) Aquí hay un bosquejo de prueba. $\Omega(\sqrt{n/2^n})$

Es suficiente para mostrar . Nosotros hacemos eso. $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$

Tenga en cuenta que si y son completamente independientes, nos gustaría hacer porque la expectativa del mínimo de las dos sumas independientes es $\text{Inf}_1[f]$ $\text{Inf}_2[f]$ . Primero, discutiremos cuidadosamente que las dos sumas son casi independientes. $1/2-\Omega(\sqrt{1/2^n})$

Considere el universo de puntos . Llame y en -neighbours si difieren solo en la ésima coordenada. Digamos que los dos vecinos contribuyen (a ) si . (Entonces es el número de contribuyentes $X=\{-1,1\}^n$ $x$ $x'$ $X$ $i$ $i$ $\text{Inf}_i[f]$ $f(x) \ne f(x')$ $\text{Inf}_i[f]$ $i$ -vecinos, dividido por ) Tenga en cuenta que, si y son vecinos, y e son vecinos, entonces o . Por lo tanto, el número de contribuyentes $2^{n-1}$ $x$ $x'$ $i$ $y$ $y'$ $i$ $\{x,x'\}=\{y,y'\}$ $\{x,x'\}\cap\{y,y'\}=\emptyset$ $i$ -neighbors es la suma de variables aleatorias independientes, cada uno con expectativa de . $2^{n-1}$ $1/2$

Particione el universo en grupos de tamaño cuatro, donde y están en el mismo grupo si y están de acuerdo en todas menos sus dos primeras coordenadas. Luego, para cada par de 1 vecino, y cada par de 2 vecinos, y están en el mismo grupo. Para un grupo dado e $X$ $2^{n-2}$ $x$ $x'$ $x$ $x'$ $(x,x')$ $(x,x')$ $x$ $x'$ $g$ , vamos rv ser el número de contribuir -neighbors en . Entonces, por ejemplo, el número total de vecinos 1 contribuyentes es , una suma de variables aleatorias independientes, cada una en . $i\in\{1,2\}$ $c^g_i$ $i$ $g$ $\sum_g c^g_1$ $2^{n-2}$ $\{0,1,2\}$

Tenga en cuenta que y son independientes si . Por un análisis de caso, si , la distribución conjunta de y es $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
fuente

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.