Для булевой функции влияние й переменной определяется как где строка, полученная путем переключения го бита . Тогда минимальное влияние - это
Учитывая параметр , мы выбираем случайную функцию , выбирая ее значение на каждом из входов независимо друг от друга случайным образом равным с вероятностью и с вероятностью , Тогда легко увидеть, что для каждого и тем болеер е 2 п 1 р - 1 1 - р я ∈ [ п ] Е F [ Инф я [ е ] ] = 2 р ( 1 - р )
Мой вопрос:
Существует ли асимптотически (относительно ) плотное выражение для ? Можем ли мы получить такое выражение даже для ?p = 1
В частности, я забочусь о младших членах, то есть меня заинтересовал бы асимптотический эквивалент для величины .
(Следующий вопрос, который подчиняется первому, заключается в том, можно ли также получить хорошие границы концентрации вокруг этого ожидания.)
По границам Черноффа можно также показать, что каждое имеет хорошую концентрацию, так что по границе объединения мы получаем (если я не слишком плохо испортил) но это скорее всего потеря на нижней границе (из-за границы объединения) и определенно на верхней границе. (В частности, я ищу верхнюю границу, строго меньшую, чем тривиальная ).1
Обратите внимание, что одной из проблем в этом, помимо принятия минимума из одинаково распределенных случайных величин (влияний), является то, что эти случайные переменные не являются независимыми ... хотя я ожидаю, что их корреляция "довольно быстро" затухает с ,
(Для чего это стоит, я явно вычислил первые несколько до , и запустил симуляции для оценки следующих, до или около того. Не уверен, насколько это полезно может быть, но я могу включить это, как только я вернусь в свой офис.)
источник
Ответы:
Вот шаг в правильном направлении ...
Я буду утверждать , что при , то есть 1 / 2 - I п ( 1 / 2 ) = Q , ( √p=1/2 .1/2−In(1/2)=Ω(1/2n−−−−√)
(Это не так сильно, как следовало бы. Может быть, кто-то может усилить аргумент, чтобы показать .) Вот набросок доказательства.Ω(n/2n−−−−√)
Достаточно показать , . Мы делаем это.1/2−Ef[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}n x x′ X i i Infi[f] f(x)≠f(x′) Infi[f] i -соседи, разделенные на ) Обратите внимание, что если x и x ′ являются i- соседями, а y и y ′ являются i- соседями, то либо { x , x ′ } = { y , y ′ }, либо { x , x ′ } ∩ { y , y ′ } = ∅ . Следовательно, количество способствующих я2n−1 x x′ i y y′ i {x,x′}={y,y′} {x,x′}∩{y,y′}=∅ i -neighbors является суммой независимых случайных величин, каждая с ожиданием 1 / 2 .2n−1 1/2
Разбейте вселенную на 2 n - 2 группы четвертого размера, где x и x ' находятся в одной группе, если x и x ' согласны по всем, кроме их первых двух координат. Тогда для каждой пары ( x , x ′ ) 1-соседей и каждой пары ( x , x ′ ) 2-соседей x и x ′ находятся в одной группе. Для данной группы g и i ∈ { 1X 2n−2 x x′ x x′ (x,x′) (x,x′) x x′ g , пусть rv c g i будет числом способствующих i- соседей в g . Тогда, например, число вклад 1-соседейцелом является Σ г с г 1 , сумма 2 п - 2 независимых случайных величин, каждая в { 0 , 1 , 2 } .i∈{1,2} cgi i g ∑gcg1 2n−2 {0,1,2}
Следует отметить , что и с г ' 2 являются независимыми , если г ≠ г ' . По анализу случае, если г = г ' , совместное распределение с г 1 и с г 2 являетсяcg1 cg′2 g≠g′ g=g′ cg1 cg2
Let r.v.N={g:cg1=cg2=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
Conditioned onN , for each g∈N¯¯¯¯¯ r.v.'s cg1 and cg2 are independent (by inspection of their joint distribution above), so (conditioned on N ) all r.v.'s {cgi:i∈{1,2},g∈N¯¯¯¯¯} are i.i.d. uniformly over {0,2} so,
Finally, note that each group is neutral with probability 1/2, soPr[|N¯¯¯¯¯|≤2n−2/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...
источник