# Bound on the probability that noise changes the majority value of random bits

I have the following problem. I have a vector of size $N$ in $\mathbb{F}_2$ containing exactly $m$ zeros and $n$ ones with $m>n$. Then, a random noise is applied on each bit independently such that with probability $p$ the value of a bit is changed.

I'm trying to bound the probability that the majority value changes, i.e. that after applying the noise we get more ones than zeros.

What I did is the following: I created a random variable $X$ denoting the number of zeros that are modified by the noise and $Y$ the number of ones that are modified. I was then able to bound the probability by summing over all $\Pr[X>k \cap Y < N/2-m+k]$ such that $n+X-Y > N/2$.

However, this bound is rather complicated and I'm looking for simpler one. Any idea?

-

Center everything by introducing $U=X-mp$ and $V=Y-np$. Then $U-V$ is the sum of $n+m$ independent random variables with different distributions (if $p\ne\frac12$) but each centered and with variance $p(1-p)$. Furthermore, the event $A=[X-Y\geqslant\frac12(m-n)]$ is also $[U-V\geqslant\frac12(1-2p)(m-n)]$.
Hence, at least for $p<\frac12$, Bienaymé-Chebychev inequality yields $$\mathrm P(A)\leqslant\frac{4(m+n)p(1-p)}{(m-n)^2(1-2p)^2}.$$ The RHS is small if $m-n$ and $m+n$ are of the same order and large and if $p$ is small. For example, if $m\sim(1-\theta) N$ and $n\sim\theta N$ for a given $\theta<\frac12$ with $N\to\infty$ and if $p\to0$, the RHS is equivalent to $$\frac{4}{(1-2\theta)^2}\frac{p}N.$$ To go further, you could precise what regime of $n$, $m$ and $p$ interests you.