Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$

Question

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

Answer 1

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