2
$\begingroup$

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?

1 Answers 1

0

Let us first center every random variable of interest by considering $U=X-mp\qquad V=Y-np$ Then $U-V$ is the sum of $n+m$ independent random variables, with different distributions when $p\ne\frac12$, but always centered and with comon variance $p(1-p)$.

Furthermore, the event $A=[X-Y\geqslant\frac12(m-n)]$ is also $A=[U-V\geqslant\frac12(1-2p)(m-n)]$.

Hence, for every $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 $p$ is small and $m-n$ and $m+n$ are of the same order and large. For example, if $p\to0$ and $m\sim(1-\theta) N$ and $n\sim\theta N$ for a given $\theta<\frac12$ with $N\to\infty$, then 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.