Skip to main content

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.

gidi
  • 61
  • 2