**Edit:** I was indeed missing something quite obvious, indeed. 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.

---
**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