Let $C(b,n)$ be the number of collisions when throwing $b$ balls into $n$ bins (where the bin probabilities are not necessarily uniform).

Proposition 15 of [AGK13] states that there exists a size-biased coupling $C'(b,n)$ such that $C'(b,n)-C(b,n) \in \{-1,0,1,2\}$ a.s. Moreover, the proof of this proposition athen states that this implies the existence of a size-biased coupling $C'(b,n)$ such that $C'(b,n)-C(b,n) \in [0,2]$ a.s.:
> A general principle relating bounded couplings, monotone couplings, and bounded monotone couplings, [AB13, Prop. 7.1], now implies that there exists acoupling of $C(b, n)$ with its size biased version $C'(b, n)$, for which $0\leq C'−C\leq 2$.

Then, combining this with the main result of [GG11], as pointed out in [AGK13] (just after the proof of Proposition 15, but for the general coupling, not the uniform-bins they focus on) this then implies that, for every $t>0$,
$$\begin{align}
 \mathbb{P}\{ C(b,n) &\leq \mathbb{E}[C(b,n)] - t \} \leq e^{-\frac{t^2}{4\mathbb{E}[C(b,n)]}} \tag{1} \\
\mathbb{P}\{ C(b,n) &\geq \mathbb{E}[C(b,n)] + t \} \leq e^{-\frac{t^2}{4(\mathbb{E}[C(b,n)]+t/2)}} \tag{2} 
\end{align}$$ 
This a priori looks great; however, letting $p$ be the (arbitrary) distribution over the $n$ bins, we have $\mathbb{E}[C(b,n)] = \binom{b}{2}\|p\|_2^2$, and taking $t := \varepsilon \mathbb{E}[C(b,n)]$ this implies that we can get (with high constant probability) an estimate of $\|p\|_2^2$, correct within a factor $(1\pm\varepsilon)$, using only $b = O(1/(\varepsilon\|p||_2))$ samples.

Which is **not true** in general: there exist some distributions $p$ for which $b = \Omega(1/(\varepsilon^2\|p||_2))$ samples are necessary. (Cf. Theorem 16 of [AOST16], for $\alpha=2$).

> What am I missing here? 



---
[AOST16] *Estimating Renyi Entropy of Discrete Distributions.* J. Acharya, A. Orlitsky, A. T. Suresh and H. Tyagi. IEEE Transactions on Information Theory (2017), vol. 63, no. 1, pp. 38-56, doi: 10.1109/TIT.2016.2620435. https://arxiv.org/abs/1408.1000

[AGK13] *Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process.* R. Arratia, S. Garibaldi, J. Kilian, 2013. https://arxiv.org/abs/1310.7055

[AB13]  *Bounded size bias coupling:  a gamma function bound, and universal Dickman-function behavior.* R. Arratia and P. Baxendale, 2013, https://arxiv.org/abs/1306.0157.

[GG11] *Concentration of measures via size-biased couplings.* Subhankar Ghosh and Larry Goldstein,Probab. Theory Related Fields 149 (2011), no. 1-2, 271–278. https://arxiv.org/abs/0906.3886