Thread: Chebyshev inequality

Hi all,
I would appreciate if someone could help me with this question.

How I can ,using Chebyshev inequality, prove that a least of all bitstrings of length n have hamming weight that could satisfy the following relation . wt(x) is hamming wieght.

Thanks in advance

Regards,

I think you have to make the assumption that all the bitstrings are equally likely. With that assumption, the hamming weight has a Binomial(n, p) distribution with p = 1/2. From this you can get the mean and standard deviation and apply Chebyshev's inequality.