I'm reading a paper which states: "By the Chernoff Bound:
$$ \Pr\big[\big||x|-\frac{n}{2}\big|>3\sqrt{n}\big]< 0.03 $$
Where:
$x$ is a binary vector of length n (each index is either 0 or 1 with probability $\frac{1}{2}$).
and
$|x|$ is the Hamming weight of $x$, i.e. no. of $1$s.
I have tried obtaining this through the following procedure, unsuccessfully of course... and would appreciate any help:
$$ \Pr\big[\big||x|-\frac{n}{2}\big|>3\sqrt{n}\big] = \Pr\big[|x|-\frac{n}{2}>3\sqrt{n}\big]+ \Pr\big[|x|-\frac{n}{2}<-3\sqrt{n}\big] $$
Starting with the first term after "=", by Chernoff Bound, we have for all $t>0$:
$$ \Pr\big[|x|-\frac{n}{2}>3\sqrt{n}\big]= \Pr\big[e^{t(|x|-\frac{n}{2})}> e^{3t\sqrt{n}}\big]< \frac{E\big[e^{t(|x|-\frac{n}{2})}\big]}{e^{3t\sqrt{n}}} $$
So far, my first problem here is that the Chernoff Bound should have $\geq$ and $\leq$, at least according to its wikipedia page, but assuming there's some simple solution to that, I continue by tying to compute the expectation term:
$$ E\big[e^{t(|x|-\frac{n}{2})}\big]=e^{-t\frac{n}{2}}E\big[e^{t|x|}\big] $$
My intuition here is that $E\big[e^{t|x|}\big]$ will end up cancelling out the other term somehow (e.g. if it equals $e^{t\frac{n}{2}}$), so during my next step, that's what I'm looking for, but so far have been unsuccessful:
$$ E\big[e^{t|x|}\big] = \Pr(|x|=0)e^0 +\Pr(|x|=1)e^t+\dots+\Pr(|x|=n)e^{nt} \leq e^{nt}\frac{\sum_{k=0}^n {n\choose k}}{2^n}=e^{nt}\frac{2^n}{2^n} = e^{nt} $$
As you can see, this does not cancel out that term and I'm not getting the tight lower bound obtained in the paper. Obviously, taking the highest exponent in the sum is not helping. Maybe there's a better way of bounding this sum, say with a term depending on $e^{tn/2}$? Or using some other version of Chernoff?
Any help much appreciated!
So basically you have a vector $y$ of $n$ signs with sum $s$ and you want to show $P(|s| \geq 6\sqrt{n}) < 0.03$.
By symmetry, it’s clearly enough to show $P(s \geq 6\sqrt{n}) < 0.015$.
Now, if $t > 0$, $e^{ts}=(\cosh{t})^n$, so $P(s \geq 6\sqrt{n})\leq e^{-6t\sqrt{n}}(\cosh{t})^n$. With $t=1/\sqrt{n}$, you get something smaller than $e^{-6}(1+(\cosh{1})/2n)^n=e^{-6+0.5\cosh{1}} < e^{-4.4} < 0.015$.
(NB: if $0 \leq x \leq y$, $\cosh{x} \leq 1+0.5x^2\cosh{y}$. That follows from the Taylor integral formula with second derivative in the integral).