This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say that $\mathbb{E}[g] = 0$, $\operatorname{Inf}_{i}(g) \leq \operatorname{Inf}_{i}(f)$ for all $i$, and $S_{\rho}(f) \geq S_{\rho}(g) = -S_{-\rho}(g)$.

So, applying MIS on $g$, we get

$S_{\rho}(g) \leq 1 - \frac{2}{\pi}\arccos(\rho) + \epsilon$ for $\rho$ from 0 to 1.

which implies

$-S_{-\rho}(g) \geq -\left(1 - \frac{2}{\pi}\arccos(-\rho) + \epsilon\right)$ for $\rho$ from -1 to 0.


$$S_{\rho}(f) \geq -1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$$

But in the statement of the proposition, authors have written $S_{\rho}(f) \geq 1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$. Is it really an error? Or I am missing something?


1 Answer 1


"So, applying MIS on $g$"

To apply the Majority is Stablest theorem, you need to apply it to a non-negative parameter $\rho'\in[0,1)$ (read the statement of the theorem). Since in Proposition 7.3 the parameter $\rho\in(-1,0]$ is non-positive, this means you here apply it to $\rho' \stackrel{\rm def}{=} -\rho\in[0,1)$, giving $$\mathbb{S}_{-\rho}(g) \leq 1-\frac{2}{\pi}\arccos(-\rho)+\epsilon = -1+\frac{2}{\pi}\arccos(\rho)+\epsilon$$ using that $\arccos x+\arccos(-x) = \pi$ for all $x$ (This may very well be the part you are missing. $\arccos$ is not an odd function). Then $$\mathbb{S}_{\rho}(f) \geq -\mathbb{S}_{-\rho}(g) \geq -\left(-1+\frac{2}{\pi}\arccos(\rho)+\epsilon\right) = 1-\frac{2}{\pi}\arccos(\rho)-\epsilon$$ as stated.

  • $\begingroup$ Thanks. You are right, I was considering arccos odd function. Stupid mistake. $\endgroup$ Dec 15, 2017 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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