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

13

f:{1,1}n{1,1}i

Infi[f]=defPrx{1,1}n[f(x)f(xi)]
xiixf
MinInf[f]=defmini[n]Infi[f].

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

Ef[Infi[f]]=2p(1p)
et a fortiori
In(p)=defEf[MinInf[f]]2p(1p).

Ma question est:

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

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(1p)In(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 ).Infi[f] 1

12O(n2n)In(12)12
12

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

(Pour ce que ça vaut, j'ai calculé explicitement les premiers n = 4 n = 20In(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=4n=20

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)
10.50020.37530.335937540.33914184570312550.362360.390770.416680.437390.4535100.4659110.4751190.4965200.4967
Clement

Réponses:

3

Voici un pas dans la bonne direction ...

Je dirai que pour , vous avezp=1/21/2In(1/2)=Ω(1/2n) .

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

Il suffit de montrer 1/2Ef[min(Inf1[f],Inf2[f])]=Ω(1/2n) . C'est ce que nous faisons.

Notez que si etInf1[f]Inf2[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Ω(1/2n)

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 soitX={1,1}nxxX iiInfi[f]f(x)f(x)Infi[f]i2n1xxiyyi{x,x}={y,y} ou .{x,x}{y,y}= . Par conséquent, le nombre de voisins contributeurs est la somme de variables aléatoires indépendantes, chacune avec une attentei2n11/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 estX2n2xxxx(x,x)(x,x)xxgi{1,2}cigig 2 n - 2 { 0 , 1 , 2 }gc1g , une somme de variables aléatoires indépendantes, chacune dans .2n2{0,1,2}

Notez que et sont indépendants si . Par une analyse de cas, si , la distribution conjointe de et est c g 2 g g g = g c g 1 c g 2c1gc2gggg=gc1gc2g

01201/801/8101/2021/801/8

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 ¯ N c g 1 .N={g:c1g=c2g=1}

|N|+gN¯c1g.

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, g ¯ N c g 1 c g 2 N { c g i : i { 1 , 2 } , g ¯ N } { 0 , 2 } E [ | ¯ N | - min (g ¯ N c g 1 , g ¯ N c g 2NgN¯c1gc2gN{cig:i{1,2},gN¯}{0,2}

E[|N¯|min(gN¯c1g,gN¯c2g) | N]Θ(|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[|N¯|2n2/3]exp(Ω(2n))2n

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
Clement C.