1
$\begingroup$

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a boolean function. Define the influence of the $i$'th coordinate of $f$ as follows: $$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]$$ where $x$ is uniformly picked from $\{-1,1\}^n$, and $\hat x_i$ is $x$ with its $i$'th coordinate flipped (e.g., say $x=(1,1,1,1,-1)$, then $\hat x_3=(1,1,-1,1,-1)$).

Denote by $J_k$ the set of all the k-juntas for which the influencing variables are the first $k$ variables. That is, for each $f\in J_k$, the function $f$ is a boolean function that holds $Inf_i(f)>0$ for $1\leq i\leq k$ and $Inf_i(f)=0$ for $i>k$.

Let $0\leq \epsilon \leq 1$. What is the probability (over uniformly selecting such a k-junta) that the influence in each influencing coordinate of the junta will be less than $\epsilon$ ? Formally: $$\Pr_{f\in J_k}[\forall i\quad Inf_i(f)< \epsilon]=?$$

  • 0
    Why do you even mention the remaining $n-k$ variables? If I understand the problem correctly, they don't change the influences, and the question is equivalent to simply asking about the probability of a random function of $k$ coordinates having all $k$ influences below $\epsilon$?2011-09-25
  • 0
    @joriki Just for clarity. It is indeed equivalent to asking about the probability of a random function of k coordinates having all $k$ influences below $\epsilon$.2011-09-25
  • 0
    After playing with some examples, I tend to believe that the probability for each coordinate behaves like a binomial R.V. up to normalization. That is, for every $i$ holds $\Pr_{f\in J_k}[Inf_i(f)<\epsilon]=\Pr[\frac{B(2^{k-1},0.5)}{2^{k-1}}<\epsilon]$. But I can't seem to prove it.2011-09-25

1 Answers 1