# Convexity of the expectation of boolean functions

Let $$f:\{-1,1\}^n \to \{-1,1\}$$ be a monotone, odd ($$f(-x)=-f(x)$$) Boolean function.

Let $$F:[0,1]\to[0,1]$$ denote the probability that $$f(x_1,...,x_n)$$ where $$x_1,...,x_n$$ are i.i.d. $$\pm1$$ R.V. with probability $$p$$ to be 1.

Our question is the following:

Is it true that $$F$$ is convex in $$[0,1/2]$$ for any such monotone odd $$f$$?

(It is easy to see that $$F$$ is symmetric around $$1/2$$.)

Another way to view this is that $$dF/dp$$ is increasing in $$[0,1/2]$$, meaning the bits become more influential as $$p$$ is closer to $$1/2$$.

So far, in the example we worked out (such as majority) this turned out to be the case, and we could not find any references, nor managed to prove it or find a counterexample. A related fact - when I encountered "graphs" of the probability that certain monotone graph properties are satisfied in $$G(n,p)$$ as a function of $$p$$, they were always "drawn" as convex till the threshold and concave afterwards, but I could not find any explicit references to this phenomena.

• It may be useful to think of this as just a question about monotone functions. This isn't hard to do - any monotone function can be turned into an odd monotone function with one more variable. If I haven't done my arithmetic wrong, the condition is that for any monotone $g$, $\frac{d (ln(\frac{d(G(p))}{dp}))}{dp} < \frac{4}{1 - 2p}$ over the entire interval. – user44191 Sep 17 at 23:08

## 1 Answer

By Russo's formula, $$F'(p)$$ coincides with the expected number of pivotal elements at $$p$$ (where a an element $$x_i$$ is pivotal for a configuration in $$\{-1,1\}^n$$ if changing the sign of $$x_i$$ also will change the sign of $$f$$). So if $$F'$$ is increasing on $$[0,1/2]$$, then we expect to see most pivotal elements at $$p = 1/2$$.

I don't think that this is true in general. Instead of 'majority', think of 'weighted majority' where $$x_1$$ has disproportionally large weight. Then intuitively $$x_1$$ will be pivotal for most values of $$p$$, but any other $$x_i$$ is more likely to be pivotal for $$p$$ close to $$0$$ or close to $$1$$, so we'd expect fewer pivotal elements at $$1/2$$ than closer to $$0$$ or $$1$$.

If I'm not mistaken, the following example exhibits this behaviour. Let $$f = \mathrm{sign}(5 x_1 + \sum _{i=2}^7 x_i)$$ Then $$f$$ is $$1$$ exactly when either $$x_1 = 1$$ and at least one of the other $$x_i$$ is $$1$$, or $$x_1 = -1$$ and all other $$x_i$$ are equal to $$1$$. Hence $$F(p) = p(1-(1-p)^6)+ (1-p)p^6$$ whose second derivative assumes negative values.

• Thank you. I was trying to go down the same path but stopped at too-small examples. I wonder if there is a good way to give constraints under which this will still be true. – gidi Sep 21 at 11:58