Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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