Differential Privacy and Randomized Responses for Counting Queries
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.