Influence minimale attendue d'une fonction booléenne aléatoire

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

Étant donné un paramètre $p\in[0,1]$ , nous choisissons une fonction $p$ aléatoire $f$ en choisissant sa valeur sur chacune des $2^n$ entrées indépendamment au hasard pour être $1$ avec la probabilité $p$ , et $-1$ avec la probabilité $1-p$ . Ensuite, il est facile de voir que, pour chaque $i\in[n]$

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

$\mathbb{E}_{f}[\operatorname{Inf}_i[f]] = 2p(1-p)$ et a 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).$

Ma question est:

Existe-t-il une expression serrée asymptotiquement (par rapport à $n$ ) pour ? Même pour , pouvons-nous obtenir une telle expression? $I_n(p)$ $p=\frac{1}{2}$

Plus précisément, je me soucie des termes d'ordre bas, c'est-à-dire que je serais intéressé par un équivalent asymptotique pour la quantité $2p(1-p)-I_n(p)$ .

(La question suivante, mais qui est subordonnée à la première, est de savoir si l'on peut également obtenir de bonnes limites de concentration autour de cette attente.)

Par les limites de Chernoff, on peut également montrer que chaque a une bonne concentration, de sorte que par une union, nous obtenons (si je ne me trompe pas trop) mais c'est très probablement lâche sur la limite inférieure (en raison de la liaison d'union) et certainement sur la limite supérieure. (Je recherche en particulier une borne supérieure strictement inférieure au 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}$

Notez que l'un des problèmes en faisant cela, en plus de prendre le minimum de variables aléatoires identiquement distribuées (les influences), est que ces variables aléatoires ne sont pas indépendantes ... bien que je m'attende à ce que leur corrélation se désintègre "assez rapidement" avec . $n$ $n$

(Pour ce que ça vaut, j'ai calculé explicitement les premiers $I_n(1/2)$ jusqu'à , et j'ai exécuté des simulations pour estimer les suivantes, jusqu'à environ. Je ne sais pas à quel point cela est utile pourrait l'être, mais je peux l'inclure une fois que je serai de retour à mon bureau.) $n=4$ $n=20$

reference-request pr.probability boolean-functions Clement C.
la source

Voici les premiers (seuls les 4 premiers sont exacts, les autres proviennent d'un échantillonnage aléatoire (pour estimer les influences) en moyenne sur 10 ^ 5 fonctions générées aléatoirement): (remarque: pour les simulations, pas sûr que le 4ème chiffre soit vraiment significatif)

\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

Réponses:

Voici un pas dans la bonne direction ...

Je dirai que pour , vous avez $p=1/2$ $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$ .

(Ce n'est pas aussi fort qu'il devrait l'être. Peut-être que quelqu'un peut renforcer l'argument pour montrer $\Omega(\sqrt{n/2^n})$ .) Voici un croquis de preuve.

Il suffit de montrer $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$ . C'est ce que nous faisons.

Notez que si et $\text{Inf}_1[f]$ $\text{Inf}_2[f]$ étaient complètement indépendants, nous aurions terminé parce que l'espérance du minimum des deux sommes indépendantes est . Tout d'abord, nous allons argumenter soigneusement que les deux sommes sont presque indépendantes. $1/2-\Omega(\sqrt{1/2^n})$

Considérons l'univers des points . Appelez et dans voisins s'ils diffèrent uniquement par la ème coordonnée. Supposons que les deux voisins contribuent (à ) si . (Donc est le nombre de voisins contributeurs , divisé par .) Notez que, si et sont des voisins, et et sont voisins, alors soit $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'\}$ ou . $\{x,x'\}\cap\{y,y'\}=\emptyset$ . Par conséquent, le nombre de voisins contributeurs est la somme de variables aléatoires indépendantes, chacune avec une attente $i$ $2^{n-1}$ $1/2$

Divisez l'univers en groupes de taille quatre, où et sont dans le même groupe si et sont accord sur toutes les coordonnées sauf leurs deux premières. Alors pour chaque paire de 1-voisins, et chaque paire de 2-voisins, et sont dans le même groupe. Pour un groupe et , soit rv le nombre de voisins contributeurs en . Ensuite, par exemple, le nombre total de voisins 1 contributeurs est $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$ , une somme de variables aléatoires indépendantes, chacune dans . $2^{n-2}$ $\{0,1,2\}$

Notez que et sont indépendants si . Par une analyse de cas, si , la distribution conjointe de et est $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}$

Soit rv l'ensemble des groupes neutres . (Ils contribuent exactement leur quantité attendue à l'influence 1 et à l'influence 2.) Le nombre de voisins 1 contributeurs est alors $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.$

Conditionné sur , pour chaque rv's et sont indépendants (en examinant leur distribution conjointe ci-dessus), donc (conditionnés sur ) tous les rv sont iid uniformément sur donc, $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|}).$

Enfin, notez que chaque groupe est neutre avec une probabilité 1/2, donc est extrêmement petit, disons (et même dans ce cas, le côté gauche ci-dessus est au moins ) . Il en découle la limite inférieure revendiquée ... $\Pr[|\overline N| \le 2^{n-2}/3]$ $\exp(-\Omega(2^n))$ $-2^n$

Neal Young
la source

Je vous remercie! Je vais essayer de voir s'il existe un moyen d'adapter votre approche obtenir un

supplémentaire sous la racine ...

n

$n$

Clement C.