# The fraction of k-juntas with low influences in all of the coordinates

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]=?$$

-
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$? – joriki Sep 25 '11 at 9:11
@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$. – User1234 Sep 25 '11 at 13:31
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. – User1234 Sep 25 '11 at 13:36

I'm afraid the marginal distribution for the influence of a single coordinate is the easier part :-) I gave up on this problem because the interrelations between the influences of different coordinates seem too complicated. But if you're interested in the marginal distribution, here's why it's binomial: A given influence for the $i$-th coordinate corresponds to a given number $m$ of pairs of points differing only in the $i$-th coordinate that have different function values. There are $2^{k-1}\choose m$ different ways of choosing the remaining $k-1$ coordinates for these $m$ pairs. For each pair with different function values, there are $2$ possibilities, $(-1,1)$ and $(1,-1)$, and for each pair with the same function values, there are also $2$ possibilities, $(-1,-1)$ and $(1,1)$. Thus the factor $2^{2^{k-1}}$ arising from these possibilities is independent of $m$ and cancels out in the probabilities, which are therefore completely determined by the number $2^{k-1}\choose m$ of choices for the coordinates for the pairs.

Here's another idea I tried: We can write the influence of the $i$-th coordinate as

$$\operatorname{Inf}_i(f)=\Pr_{x}[f(x)\neq f(\hat x_i)]=\frac{1-2^{-n}\sum_xf(x)f(\hat x_i)}2\;.$$

With the Walsh–Fourier transform of $f$,

$$f(x)=\sum_j a_jf_j(x)\;,$$

this becomes

\begin{align} \operatorname{Inf}_i(f) &=\frac{1-2^{-n}\sum_x(\sum_j a_jf_j(x))(\sum_{j'} a_{j'}f_{j'}(\hat x_i))}2\\ &=\frac{1-2^{-n}\sum_j\sum_{j'}a_ja_{j'}\sum_xf_j(x)f_{j'}(\hat x_i)}2\\ &=\frac{1-2^{-n}\sum_j\sum_{j'}a_ja_{j'}\sum_xf_j(x)(\pm f_{j'}(x))}2\\ &=\frac{1-\sum_j(\pm a_j^2)}2\;,\\ \end{align}

where the sign depends on whether $f_j$ changes sign with $x_i$.

Unfortunately I think this doesn't get us much closer to solving the problem, because although the $a_j$ are linearly uncorrelated, they're not independent and their squares are highly correlated.

-
Thanks for the explanation of the marginal distribution ! I actually tried something very similar to your Fourier approach, but I keep getting stuck. Do you think that finding a (somewhat) tight bound might be significantly easier ? – User1234 Sep 26 '11 at 6:00
@Tom: I don't know -- I don't have any idea how to find one -- it all seems rather complicated. – joriki Sep 26 '11 at 6:05