13
$\begingroup$

For a Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$, the influence of the $i$th variable is defined as $$ \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})] $$ where $x^{\oplus i}$ is the string obtained by flipping the $i$th bit of $x$. The minimum influence of $f$ is then $$\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f].$$

Given a parameter $p\in[0,1]$, we choose a $p$-random function $f$ by choosing its value on each of the $2^n$ inputs independently at random to be $1$ with probability $p$, and $-1$ with probability $1-p$. Then, it is easy to see that, for every $i\in[n]$ $$ \mathbb{E}_{f}[\operatorname{Inf}_i[f]] = 2p(1-p) $$ and a fortiori $$ I_n(p) \stackrel{\rm def}{=}\mathbb{E}_{f}[\operatorname{MinInf}[f]] \leq 2p(1-p). $$

My question is:

Is there an asymptotically (with regard to $n$) tight expression for $I_n(p)$? Even for $p=\frac{1}{2}$, can we get such an expression?

Specifically, I do care about the low order terms, i.e. I'd be interested in an asymptotic equivalent for the quantity $2p(1-p)-I_n(p)$.

(The next question, but which is subordinate to the first, is whether one can also get good concentration bounds around this expectation.)


By Chernoff bounds one can also show that each $\operatorname{Inf}_i[f]$ has good concentration, so that by a union bound we get (if I did not mess up too badly) $$ \frac{1}{2} - O\left(\sqrt{\frac{n}{2^n}}\right) \leq I_n\left(\frac{1}{2}\right) \leq \frac{1}{2} $$ but this is most likely loose on the lower bound (due to the union bound) and definitely on the upper bound. (I am in particular looking for an upper bound strictly less than the trivial $\frac{1}{2}$).


Note that one of the issues in doing that, besides taking the minimum of $n$ identically distributed random variables (the influences), is that these random variables are not independent... although I do expect their correlation to decay "pretty fast" with $n$.

(For what it's worth, I have computed explicitly the first few $I_n(1/2)$'s up to $n=4$, and have run simulations to estimate the following ones, up to $n=20$ or so. Not sure how helpful this could be, but I can include that once I am back to my office.)

$\endgroup$
  • $\begingroup$ Here are the first few (only the first 4 are exact, the others are from random sampling (to estimate the influences) averaged over 10^5 randomly generated functions): $$\begin{align}1 &\qquad 0.500\\ 2 &\qquad 0.375\\ 3 &\qquad 0.3359375\\ 4 &\qquad 0.339141845703125\\ 5 &\qquad 0.3623\\ 6 &\qquad 0.3907\\ 7 &\qquad 0.4166\\ 8 &\qquad 0.4373\\ 9 &\qquad 0.4535\\ 10 &\qquad 0.4659\\ 11 &\qquad 0.4751\\ 19 &\qquad 0.4965\\ 20 &\qquad 0.4967\\ \end{align}$$ (note: for the simulations, not sure the 4th digit is really significant) $\endgroup$ – Clement C. Mar 20 '16 at 22:36
3
+50
$\begingroup$

Here's a step in the right direction...

I'll argue that for $p=1/2$, you have $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$.

(This is not quite as strong as it should be. Maybe someone can strengthen the argument to show $\Omega(\sqrt{n/2^n})$.) Here's a proof sketch.

It suffices to show $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$. We do that.

Note that if $\text{Inf}_1[f]$ and $\text{Inf}_2[f]$ were completely independent, we'd be done because the expectation of the minimum of the two independent sums is $1/2-\Omega(\sqrt{1/2^n})$. First, we'll argue carefully that the two sums are almost independent.

Consider the universe of points $X=\{-1,1\}^n$. Call $x$ and $x'$ in $X$ $i$-neighbors if they differ in just the $i$th coordinate. Say the two neighbors contribute (to $\text{Inf}_i[f]$) if $f(x) \ne f(x')$. (So $\text{Inf}_i[f]$ is the number of contributing $i$-neighbors, divided by $2^{n-1}$.) Note that, if $x$ and $x'$ are $i$-neighbors, and $y$ and $y'$ are $i$-neighbors, then either $\{x,x'\}=\{y,y'\}$ or $\{x,x'\}\cap\{y,y'\}=\emptyset$. Hence, the number of contributing $i$-neighbors is the sum of $2^{n-1}$ independent random variables, each with expectation $1/2$.

Partition the universe $X$ into $2^{n-2}$ groups of size four, where $x$ and $x'$ are in the same group iff $x$ and $x'$ agree on all but their first two coordinates. Then for each pair $(x,x')$ of 1-neighbors, and each pair $(x,x')$ of 2-neighbors, $x$ and $x'$ are in the same group. For a given group $g$ and $i\in\{1,2\}$, let r.v. $c^g_i$ be the number of contributing $i$-neighbors in $g$. Then, for example, the number of contributing 1-neighbors overall is $\sum_g c^g_1$, a sum of $2^{n-2}$ independent random variables, each in $\{0,1,2\}$.

Note that $c^g_1$ and $c^{g'}_2$ are independent if $g\ne g'$. By a case analysis, if $g=g'$, the joint distribution of $c^g_1$ and $c^g_2$ is $$\begin{array}{c|ccc} & 0 & 1 & 2 \\ \hline 0 & 1/8 & 0 & 1/8 \\ 1 & 0 & 1/2 & 0 \\ 2 & 1/8 & 0 & 1/8 \\ \end{array}$$

Let r.v. $N=\{ g : c^g_1=c^g_2=1\}$ denote the set of neutral groups. (They contribute exactly their expected amount to the 1-influence and the 2-influence.) The number of contributing 1-neighbors is then $$|N| + \sum_{g\in \overline{N}} c^g_1.$$

Conditioned on $N$, for each $g\in \overline N$ r.v.'s $c^g_1$ and $c^g_2$ are independent (by inspection of their joint distribution above), so (conditioned on $N$) all r.v.'s $\{c^g_i : i\in\{1,2\}, g\in\overline N\}$ are i.i.d. uniformly over $\{0,2\}$ so, $$\textstyle E\Big[|\overline N|- \min\big(\sum_{g\in \overline N} c^g_1, \sum_{g\in \overline N} c^g_2\big) ~\Big|~ N\Big] \ge \Theta(\sqrt{|\overline N|}).$$

Finally, note that each group is neutral with probability 1/2, so $\Pr[|\overline N| \le 2^{n-2}/3]$ is extremely small, say $\exp(-\Omega(2^n))$ (and even in that case the left-hand-side above is at least $-2^n$). From this the claimed lower bound follows...

$\endgroup$
  • $\begingroup$ Thank you! I'll try and see if there is a way to adapt your approach get an additional $n$ under the root... $\endgroup$ – Clement C. Mar 31 '16 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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