It is well known that the majority function is stable under random flipping of bits. That is, if $v$ is a random binary vector, and then we re-sample each bit of $v$ with probability $\delta$ and get $v^{'}$, then $\Pr[Maj(v) = Maj(v^{'})] = 1 - \frac{arccos(\delta)}{\pi}$

However, how will the majority function behave under addition or substruction of entries? Say we delete t random bits of v and add s random bits to get $v^{'}$. Is there any similar connection between $Maj(v)$ and $Maj(v^{'})$ in this scenario?

I conjecture that yes because the two cases are of course equivalent when s=t, however, I'm not sure how the connection behaves as a function of s,t, nor how to formally start to prove such connection.




Your Answer

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