# Bounding the estimation error of flipped bit-vector sum using Chernoff bound

In a paper Distributed Private Data Analysis: On Simultaneously Solving How and What, a bit vector $x=(x_1,\dots,x_n)$ is given, whose sum $f=\sum_i x_i$. Each bit $x_i$ is independently flipped with probability $p=\frac{1}{2+\epsilon}$ for fixed $\epsilon>0$. That is, let $z_i=x_i$ with probability $1-p$ and $z_i=1-x_i$ otherwise. Then given the flipped bit vector $\mathrm{flip}(x)=(z_1,\dots,z_n)$, the original sum $f$ has an unbiased estimator: $$\hat{f}=\epsilon^{-1}((2+\epsilon)\sum_i z_i) - \epsilon^{-1}n$$ The paper then claims that this estimator has error $\mathcal{O}(\sqrt{n}/\epsilon)$ with constant probability. That is, for all bit vectors $x$: $$\Pr[|\hat{f}(x) - f(x)| > \mathcal{O}(\sqrt{n}/\epsilon)] \leq \mathcal{O}(1)$$ They say they got it via Chernoff bound. So I tried to work my way, using the definition of Chernoff bound from the book "The Probabilistic Method" (note: the absolute is missing): $$\Pr[\hat{f} - f > \ell] \leq \mathbb{E}[e^{\lambda(\hat{f} - f)}] e^{-\lambda \ell} = \mathbb{E}[e^{\lambda \hat{f} }] e^{-\lambda (\ell+ f)}$$ Then $$\mathbb{E}[e^{\lambda \hat{f} }] = \mathbb{E}[e^{2 \frac{\lambda}{\epsilon} \sum_i z_i+ \lambda \sum_i z_i - \frac{\lambda}{\epsilon}n }] = \mathbb{E}[e^{2 \frac{\lambda}{\epsilon} \sum_i z_i} ] \mathbb{E}[ e^ { \lambda \sum_i z_i } ] e ^ {- \frac{\lambda}{\epsilon} n }$$

$$= (\prod_i \mathbb{E}[e^{2 \frac{\lambda}{\epsilon} z_i} ] ) (\prod_i \mathbb{E}[ e^ { \lambda z_i } ] ) e ^ {- \frac{\lambda}{\epsilon} n }$$

When I expand $\mathbb{E}[ e^ { \lambda z_i } ]$ to $p e^ { \lambda (1-x_i) } + (1-p) e^ { \lambda x_i }$, I collect in two groups to get rid of $x_i$'s; a group evaluated at $x_i=1$ and raised to power $f$ (number of ones in the bit vector) and similarly for $x_i=0$.

I end up with a big ugly equation that I have no hope of setting $\lambda$ to get a constant probability (in $n$) as the paper claims (remember $\ell = \mathcal{O}(\sqrt{n}/\epsilon)$).

I am not sure how to proceed or whether I am doing things wrong. I've spend a lot of time on this (several weeks!) and tried to read about Chernoff bound from different sources. Any feedback is welcome, hints or directions are also great. Thank you.

-

The original binomial random variable has variance $\Theta(n)$, and so $\hat{f}-f$ has zero mean and variance $\Theta(n/\epsilon^2)$. The standard deviation is $\Theta(\sqrt{n}/\epsilon)$, and the central limit theorem implies that the probability that you're more than a constant number of standard deviations off is some constant.
The version you're quoting from the book is part of the proof of the bound. The proof already optimizes $\lambda$ and estimates the resulting bound. If you use a more streamlined version (which must be available even in the book), you should just "plug the numbers" and get your result.
@Yuval Filmus: Thanks for quick reply. I've traced through calculating the variance of $\hat{f}-f$, it turned out to exactly $n/\epsilon ^2 + n / \epsilon$. I am not sure how this is $\Theta(n/\epsilon^2)$ ? – M. Alaggan Jun 30 '11 at 2:38
$\epsilon$ is a small number, so $1/\epsilon$ is much smaller than $1/\epsilon^2$. Think of $\epsilon$ as $10^{-6}$, so $1/\epsilon = 10^6$ while $1/\epsilon^2 = 10^{12}$. So $n/\epsilon^2 + n/\epsilon \approx n/\epsilon^2$. – Yuval Filmus Jun 30 '11 at 2:50
@Yuval Filmus: Actually $\epsilon$ here is the $\epsilon$-differential privacy parameter which is typically between 0.1 and 1.5. We could regard $n/\epsilon^2 + n/\epsilon$ as $n(1+\epsilon)/\epsilon^2$ and discard $(1+\epsilon)$ as a constant but this doesn't make sense since the denominator is also a constant... I am confused here – M. Alaggan Jun 30 '11 at 3:05
If $\epsilon$ is between $0.1$ and $1.5$ then the $\Theta(1/\epsilon^2)$ and $\Theta(1/\epsilon)$ terms are not interesting, since they are both $\Theta(1)$. In other words, you can just ignore $\epsilon$. – Yuval Filmus Jun 30 '11 at 3:52