Ожидаемое минимальное влияние случайной булевой функции

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

Учитывая параметр , мы выбираем случайную функцию , выбирая ее значение на каждом из входов независимо друг от друга случайным образом равным с вероятностью и с вероятностью , Тогда легко увидеть, что для каждого и тем болеер е 2 п 1 р - 1 1 - р я [ п ] Е F [ Инф я [ е ] ] = 2 р ( 1 - р )p[0,1]pf2n1p11pi[n]

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

Мой вопрос:

Существует ли асимптотически (относительно ) плотное выражение для ? Можем ли мы получить такое выражение даже для ?np = 1In(p)p=12

В частности, я забочусь о младших членах, то есть меня заинтересовал бы асимптотический эквивалент для величины .2p(1p)In(p)

(Следующий вопрос, который подчиняется первому, заключается в том, можно ли также получить хорошие границы концентрации вокруг этого ожидания.)


По границам Черноффа можно также показать, что каждое имеет хорошую концентрацию, так что по границе объединения мы получаем (если я не слишком плохо испортил) но это скорее всего потеря на нижней границе (из-за границы объединения) и определенно на верхней границе. (В частности, я ищу верхнюю границу, строго меньшую, чем тривиальная ).1Infi[f]

12O(n2n)In(12)12
12

Обратите внимание, что одной из проблем в этом, помимо принятия минимума из одинаково распределенных случайных величин (влияний), является то, что эти случайные переменные не являются независимыми ... хотя я ожидаю, что их корреляция "довольно быстро" затухает с ,nn

(Для чего это стоит, я явно вычислил первые несколько до , и запустил симуляции для оценки следующих, до или около того. Не уверен, насколько это полезно может быть, но я могу включить это, как только я вернусь в свой офис.)In(1/2)n=4n=20

Климент С.
источник
Вот первые несколько (только первые 4 являются точными, остальные взяты из случайной выборки (для оценки влияния), усредненной по 10 ^ 5 случайно сгенерированным функциям): (примечание: для моделирования не уверен, что четвертая цифра действительно значима)
10.50020.37530.335937540.33914184570312550.362360.390770.416680.437390.4535100.4659110.4751190.4965200.4967
Клемент С.

Ответы:

3

Вот шаг в правильном направлении ...

Я буду утверждать , что при , то есть 1 / 2 - I п ( 1 / 2 ) = Q , ( p=1/2.1/2In(1/2)=Ω(1/2n)

(Это не так сильно, как следовало бы. Может быть, кто-то может усилить аргумент, чтобы показать .) Вот набросок доказательства.Ω(n/2n)

Достаточно показать , . Мы делаем это.1/2Ef[min(Inf1[f],Inf2[f])]=Ω(1/2n)

Обратите внимание , что если и Inf 2 [ е ] были полностью независимы, мы бы сделать , потому что ожидание минимум двух независимых сумм 1 / 2 - Ω ( Inf1[f]Inf2[f]. Во-первых, мы будем осторожно утверждать, что две суммы почти независимы.1/2Ω(1/2n)

Рассмотрим вселенную точек . Назовите x и x в X i- соседях, если они отличаются только i- й координатой. Скажем, два соседа вносят вкладInf i [ f ] ), если f ( x ) f ( x ) . (Так что Inf i [ f ] - это число способствующих мнеX={1,1}nxxX iiInfi[f]f(x)f(x)Infi[f]i-соседи, разделенные на ) Обратите внимание, что если x и x являются i- соседями, а y и y являются i- соседями, то либо { x , x } = { y , y }, либо { x , x } { y , y } = . Следовательно, количество способствующих я2n1xxiyyi{x,x}={y,y}{x,x}{y,y}=i-neighbors является суммой независимых случайных величин, каждая с ожиданием 1 / 2 .2n11/2

Разбейте вселенную на 2 n - 2 группы четвертого размера, где x и x ' находятся в одной группе, если x и x ' согласны по всем, кроме их первых двух координат. Тогда для каждой пары ( x , x ) 1-соседей и каждой пары ( x , x ) 2-соседей x и x находятся в одной группе. Для данной группы g и i { 1X2n2xxxx(x,x)(x,x)xxg , пусть rv c g i будет числом способствующих i- соседей в g . Тогда, например, число вклад 1-соседейцелом является Σ г с г 1 , сумма 2 п - 2 независимых случайных величин, каждая в { 0 , 1 , 2 } .i{1,2}cigiggc1g2n2{0,1,2}

Следует отметить , что и с г ' 2 являются независимыми , если г г ' . По анализу случае, если г = г ' , совместное распределение с г 1 и с г 2 является c1gc2gggg=gc1gc2g

01201/801/8101/2021/801/8

Let r.v. N={g:c1g=c2g=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|+gN¯c1g.

Conditioned on N, for each gN¯ r.v.'s c1g and c2g are independent (by inspection of their joint distribution above), so (conditioned on N) all r.v.'s {cig:i{1,2},gN¯} are i.i.d. uniformly over {0,2} so,

E[|N¯|min(gN¯c1g,gN¯c2g) | N]Θ(|N¯|).

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

Neal Young
источник
Thank you! I'll try and see if there is a way to adapt your approach get an additional n under the root...
Clement C.