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.

  • $\begingroup$ 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. $\endgroup$ – user44191 Sep 17 at 23:08

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.

  • $\begingroup$ 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. $\endgroup$ – gidi Sep 21 at 11:58

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.