Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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$. –  Tom 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. –  Tom Sep 25 '11 at 13:36

1 Answer 1

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.

share|improve this answer
    
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 ? –  Tom 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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.