<p>You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n y_i -\epsilon q(x_i) - \frac{1-\epsilon}2\right| \geq \lambda\right] \leq 2 \cdot e^{-2\lambda^2 n}$$
for all $\lambda&gt;0$. Multiply through by $1/\varepsilon$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x_i)\right| \geq \frac{\lambda}{\epsilon}\right] \leq 2 \cdot e^{-2\lambda^2 n}.$$
Set $\lambda=\sqrt{\log(2/\delta)/2n}$ and substitute in $q(x)=\frac{1}{n}\sum_{i=1}^n q(x_i)$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x)\right| \geq \frac{\sqrt{\log(2/\delta)}}{\epsilon\sqrt{2n}}\right] \leq \delta.$$
Now "suppress" the $\delta$ parameter using big-O notation to get
$$\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x)\right| \leq O\left(\frac{1}{\epsilon\sqrt{n}}\right)$$ with high probability, as required.</p>

CC BY-SA 3.0
2016-05-18T05:43:17.897Z
Somehow I assumed I would need to use the bound directly on on the value of q(x) and the expected value of the randomized response, but this way I guess it also gives me a bound on the error, since, when n goes to inf the error goes to 0. Is that the reasoning here or are there some more subtle points I'm missing?
Cryptonaut
CC BY-SA 3.0
2016-05-16T22:26:22.807Z
2016-05-16T22:37:01.710Z
2016-05-16T22:37:01.710Z
Thomas Steinke
<p>I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the calculations. </p>

<p>The randomized response mechanism works as follows:</p>

<p>Let's call $q(x) = \frac{1}{n} \sum_{i=1}^{n}q(x_i)$ a counting query for a database $x$ with $n$ entries $x_i$.
Each $q(x_i)$ maps into ${0,1}$.</p>

<p>Now define a mechanism $M$ that works as follows:</p>

<p>$M(x_1, \dots, x_n) = (y_1, \dots, y_n)$, where each $y_i$ is computed as follows:</p>

<p>$ y_i = 
\begin{array}{cc}
  \{ &amp; 
    \begin{array}{cc}
      q(x_i) &amp; \textrm{with probability } \frac{1+\epsilon}{2} \\
      \neg q(x_i) &amp; \textrm{with probability } \frac{1-\epsilon}{2}
    \end{array}
\end{array}
$</p>

<p>Now we can use the value of $M$ to estimate the value of the counting query $q(x)$.</p>

<p>The expected value of $y_i$ is $\mathbb{E}[y_i] = \epsilon q(x_i) + \frac{1-\epsilon}{2}$.</p>

<p><strong>Now the bit that I do not understand</strong></p>

<p>By Chernoff bound,</p>

<p>$$ \left| \frac{1}{n}\sum_i\frac{1}{\epsilon} \cdot (y_i - \frac{(1-\epsilon)}{2}) - q(x) \right| \lt \mathcal{O}\left(\frac{1}{\sqrt{n}\cdot\epsilon}\right) $$</p>

<p>I assume they used the additive Chernoff bound $ \Pr[X \gt \mu + \epsilon] \leq e^{-2n\epsilon^2}$.</p>

<p>It's not clear to me how they got the last part, since it's also not exactly clear to me how they apply the Chernoff bound. 
In particular how they use the expected value of $y_i$ in combination with $x_i$ and the bound.</p>

<p>Could somebody maybe give me a more detailed calculation of how the last statement was calculated?</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2016-05-17T19:20:56.933Z
for what it's worth, what you describe only satisfies differential privacy if the query $q(x_i) \in \{0, 1\}$ rather than $[0,1]$.
Sasho Nikolov
<chernoff-bound><privacy>
Differential Privacy and Randomized Responses for Counting Queries
Cryptonaut
# Differential Privacy and Randomized Responses for Counting Queries

(Asked by: username_0 on 2016-05-16)

I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the calculations.

The randomized response mechanism works as follows:

Let's call $q(x) = \frac{1}{n} \sum\_{i=1}^{n}q(x\_i)$ a counting query for a database $x$ with $n$ entries $x\_i$.
Each $q(x\_i)$ maps into ${0,1}$.

Now define a mechanism $M$ that works as follows:

$M(x\_1, \dots, x\_n) = (y\_1, \dots, y\_n)$, where each $y\_i$ is computed as follows:

$ y\_i =
\begin{array}{cc}
\{ &
\begin{array}{cc}
q(x\_i) & \textrm{with probability } \frac{1+\epsilon}{2} \\
\neg q(x\_i) & \textrm{with probability } \frac{1-\epsilon}{2}
\end{array}
\end{array}
$

Now we can use the value of $M$ to estimate the value of the counting query $q(x)$.

The expected value of $y\_i$ is $\mathbb{E}[y\_i] = \epsilon q(x\_i) + \frac{1-\epsilon}{2}$.

**Now the bit that I do not understand**

By Chernoff bound,

$$ \left| \frac{1}{n}\sum\_i\frac{1}{\epsilon} \cdot (y\_i - \frac{(1-\epsilon)}{2}) - q(x) \right| \lt \mathcal{O}\left(\frac{1}{\sqrt{n}\cdot\epsilon}\right) $$

I assume they used the additive Chernoff bound $ \Pr[X \gt \mu + \epsilon] \leq e^{-2n\epsilon^2}$.

It's not clear to me how they got the last part, since it's also not exactly clear to me how they apply the Chernoff bound.
In particular how they use the expected value of $y\_i$ in combination with $x\_i$ and the bound.

Could somebody maybe give me a more detailed calculation of how the last statement was calculated?

Thanks in advance!

**Tags:** chernoff-bound, privacy

> **Comments:**
> **username_1**: for what it's worth, what you describe only satisfies differential privacy if the query $q(x_i) \in \{0, 1\}$ rather than $[0,1]$.  

---

## 1 answers

### Answer by username_2 on 2016-05-16. Score: 4 | Accepted answer

You have $\mathbb{E}[y\_i]=\epsilon q(x\_i) + (1-\epsilon)/2$ and $0 \leq y\_i \leq 1$, with all they $y\_i$s being independent. Thus the Chernoff-Hoeffding bound gives
$$\mathbb{P}\left[\left|\frac{1}{n} \sum\_{i=1}^n y\_i -\epsilon q(x\_i) - \frac{1-\epsilon}2\right| \geq \lambda\right] \leq 2 \cdot e^{-2\lambda^2 n}$$
for all $\lambda>0$. Multiply through by $1/\varepsilon$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum\_{i=1}^n \frac{1}{\epsilon}\left(y\_i - \frac{1-\epsilon}2\right)-q(x\_i)\right| \geq \frac{\lambda}{\epsilon}\right] \leq 2 \cdot e^{-2\lambda^2 n}.$$
Set $\lambda=\sqrt{\log(2/\delta)/2n}$ and substitute in $q(x)=\frac{1}{n}\sum\_{i=1}^n q(x\_i)$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum\_{i=1}^n \frac{1}{\epsilon}\left(y\_i - \frac{1-\epsilon}2\right)-q(x)\right| \geq \frac{\sqrt{\log(2/\delta)}}{\epsilon\sqrt{2n}}\right] \leq \delta.$$
Now "suppress" the $\delta$ parameter using big-O notation to get
$$\left|\frac{1}{n} \sum\_{i=1}^n \frac{1}{\epsilon}\left(y\_i - \frac{1-\epsilon}2\right)-q(x)\right| \leq O\left(\frac{1}{\epsilon\sqrt{n}}\right)$$ with high probability, as required.

> **Comments:**
> **username_0**: Somehow I assumed I would need to use the bound directly on on the value of q(x) and the expected value of the randomized response, but this way I guess it also gives me a bound on the error, since, when n goes to inf the error goes to 0. Is that the reasoning here or are there some more subtle points I'm missing?  

---

