Edit/Update: I was indeed missing something quite obvious. I assumed the notion of collision used was the one I am used to (number of pairwise collisions, so if a bin received $k$ balls then this counts as $\binom{k}{2}$ collisions). While this is the one used in the literature I am familiar with, this is not the one used in this paper, which defines it as
One collision occurs whenever a ball lands in a bin that already contains a ball, so that a bin containing $k$ balls contributes $k−1$ to the total number of collisions.
With this definition, the last part of the question (the contradiction0 is not actually an issue, since this notion of collision does not provide an unbiased estimator for the quantity $\binom{m}{2}\|p\|_2^2$ .
I should have read the paper more carefully, instead of assuming I obviously knew what the terms used meant. The original question (now solved by this) is left at the bottom; I added a new question, since I'd still like to learn more about those couplings, and whether they are applicable to "my" notion of collision.
New question: Does anyone know if a similar idea (size-biased couplings) can lead to concentration bounds for the first notion of collisions above, $$ \hat{C}(b,n) = \sum_{i<j} \mathbf{1}_{X_i=X_j} $$ where $X_1,\dots, X_b$ are the bins where the $b$ i.i.d. balls fall?
Original question: 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