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 [AGK16] 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 then 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 a coupling of $C(b, n)$ with its size biased version $C'(b, n)$, for which $0\leq C'−C\leq 2$.

(Note: in the journal version of [AGK16], $C'−C\in\{0,1,2\}$ is also part of the proposition statement.)

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

[AGK16] Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process. Arratia, R., Garibaldi, S. and Kilian, J. (2016), Random Struct. Alg., 48: 480-502. https://doi.org/10.1002/rsa.20591, 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