Скажем, у нас есть булева функция и мы применяем случайное ограничение на , Кроме того, скажем, что дерево решений это вычисляет сжимается до размера в результате случайного ограничения. Означает ли это, что имеет очень низкое общее влияние?
9
Ответы:
Претензия: еслиδ случайное ограничение f имеет размер дерева решений O(1) (в ожидании), то общее влияние таких f является O(δ−1) ,
Эскиз доказательства: по определению влияния мы имеемInf(f)=n⋅Prx,i[f(x)≠f(x+ei)] , Давайте верхнюю границу , сначала применив ограничение, затем выбрав среди оставшихся координат и зафиксировав в случайным образом все, кроме .Prx,i[f(x)≠f(x+ei)] δ i∈[n] xi
Теперь, если -restrain уменьшает дерево решений до размера , то, в частности, -restrain зависит от скоординированного . Теперь давайте выберем одну случайную нефиксированную координату (среди ) и исправим все остальные случайным образом. Поскольку ограничение зависит не более чем от координат, мы получаем функцию (в один бит), которая не является постоянной с вероятностью не более . Поэтому , как требуется.δ f O(1) δ f r=O(1) δn δ f r rδn Inf(f)=n⋅Prx,i[f(x)≠f(x+ei)]≤rδ
Примечание: приведенное выше утверждение является строгим, принимая функцию четности для битов.O(1/δ)
источник