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)$).

How do I show that if $f$ is balanced ($\mathbb{E}_x[f(x)]=0$ ) and holds $\displaystyle\sum_{i=1}^n{Inf}_i(f)=1$ then $f$ must be a dictatorship function ($dict_i(x_1,\ldots,x_i,\ldots,x_n)=x_i$) up to a sign, i.e., $\pm dict_i$ ?

share|improve this question
2  
Wouldn't $f(x_1,\ldots,x_n)=-x_i$ statisfy the assumptions just as well? –  Henning Makholm Sep 14 '11 at 12:05
    
You are correct, I forgot to mention it - I'm editing accordingly. –  Tom Sep 14 '11 at 12:12
1  
A remark on the terminology. Both the functions $f(x) = x_i$ and $f(x) = -x_i$ are usually called dictatorship functions. So there are $2n$ of those. –  Srivatsan Sep 14 '11 at 12:15
    
Tom, what facts are you allowed to use? I can see one proof using the eigenvalues of the boolean hypercube. I think that is kind of overkill for this problem, but I cannot think of a simpler approach yet... –  Srivatsan Sep 24 '11 at 17:39
    
@SrivatsanNarayanan, I've also managed to prove the claim using the Walsh-Fourier expansion (I believe that's what you mean by using the eigenvalues of the hypercube, right ?), but I agree it's an overkill (that's why I refrained from posting such an answer), and I'm certain it can be easily proved using basic tools from probability theory. –  Tom Sep 25 '11 at 9:13

1 Answer 1

up vote 2 down vote accepted

The influence $\operatorname{Inf}_i(f)$ counts how many of the pairs of input values that differ only in the $i$-th coordinate have different function values:

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

where the bracket is the Iverson bracket and the last sum is over all unordered pairs $\{ x,\hat x_i\}$ that differ only in the $i$-th coordinate. Summing this over $i$ counts the number $\sigma(f)$ of pairs of input values that differ only in a single coordinate and have different function values (let's call such a pair an "influence pair"):

$$\sum_{i=1}^n\operatorname{Inf}_i(f)=2^{1-n}\sum_{i=1}^n\sum_{\{ x,\hat x_i\}}[f(x)\neq f(\hat x_i)]=2^{1-n}\sum_{\{ x,y\}}[f(x)\neq f(y)]=2^{1-n}\sigma(f)\;,$$

where the last sum is over all unordered pairs $\{ x,y\}$ of nearest neighbours, i.e. input values that differ only in a single coordinate.

Intuitively speaking, this function is at a minimum if the $-1$s and $1$s (of which there have to be equal numbers due to the balance constraint) are bunched together and the interface between them is as small as possible. This is the case if the $1$s are all in one hyperplane orthogonal to one of the axes, that is, if $f$ is a dictatorship function. We can show this by generalizing the assertion and then proving it by induction:

If the function value of $f$ which occurs less often occurs $k$ times, then $\sigma(f)\ge k$. Further, $\sigma(f)=k$ if and only if either $k=0$ or $f$ is a dictatorship function.

The assertion holds for $n=1$: In this case, we have $\sigma(f)=0$ for $k=0$ and $\sigma(f)=1$ for $k=1$, and in the latter case $f$ is a dictatorship function.

Now assume the assertion holds for $n-1$, and consider the two hyperplanes with $x_n=\pm1$. The $k$ function values are somehow distributed over these hyperplanes, with $k^-$ values at $x_n=-1$ and $k^+$ values at $x_n=+1$, and $k^-+k^+=k$. Assume without loss of generality that $k^+\ge k^-$.

Let's add up the influence pairs. There are at least $k^+-k^-$ such pairs of points differing only in the $i$-th coordinate. By the induction hypothesis, there are at least $k^-$ influence pairs on the hyperplane $x_n=-1$, since whatever function value is in the minority for $f$ is also in the minority on that hyperplane.

The hyperplane $x_n=+1$ is only slightly more complicated to deal with. If the same function value is in the minority on that hyperplane, then there are at least $k^+$ influence pairs on that hyperplane by the induction hypothesis, and thus at least $k^-$. If the other function value is in the minority on that plane, then there are at least $2^{n-1}-k^+$ influence pairs, and since $k^++k^-=k\le2^{n-1}$, this is also at least $k^-$ influence pairs. Thus, each hyperplane contributes at least another $k^-$ influence pairs, so the sum is at least $k^+-k^-+2k^-=k^++k^-=k$.

For the bound to be attained, it must be attained on both hyperplanes individually. If both hyperplanes have only one function value, then $f$ as a whole either also has only one function value ($k=0$) or is a dictatorship function. If one of the hyperplanes has only one function value and $f$ is a dictatorship function on the other hyperplane, the bound is not attained. If $f$ is a dictatorship function on both hyperplanes, then the bound is only attained if the dictatorships are "aligned", so as not to produce any extra influence pairs between them, and in this case $f$ is also a dictatorship function. In summary, the bound is attained if and only if $k=0$ or $f$ is a dictatorship function. This completes the induction.

The balance condition implies $k=2^{n-1}$, and the influence condition implies $\sigma(f)=2^{n-1}$. By the assertion just proved, this implies that $f$ is a dictatorship function.

share|improve this answer
    
Many thanks @joriki ! That's exactly what I've looked for. –  Tom Sep 25 '11 at 13:28

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.