Return to Question

Edit/Update: 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

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

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

I should have read the paper more carefully, instead of assuming I obviously knew what the terms used meant.

Edit/Update: 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

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?

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

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).