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!