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.