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.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

Chernoff's bound is a "finite" version of the central limit theorem giving explicit bounds (rather than bounds in probability), that are useful to bound large deviations. But in this case you don't even have to use it. But if you do use it, it should work.

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.

share|improve this answer
    
@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
    
@Yuval Filmus: Okay, I won't bother you with more questions, thanks a lot for your time :) –  M. Alaggan Jun 30 '11 at 4:03

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.