# Birthday inequality for non-uniform distributions for fixed collision probability (random allocation, collision probability)

Question: Consider a distribution $D$, and $n$ i.i.d. random variables $X_i$, all distributed according to $D$. Let $p^D_2:=\Pr[X_1=X_2]$. What is a lower bound for $p^D_n:=\Pr[\exists i\neq j. X_i=X_j]$ (as a function of $p^D_2$)?

Conjecture: $p^D_n \geq 1-\bigl(1-p^D_2\bigr)^{n\choose 2}$. [EDIT: This particular bound is wrong. Counterexample by Will Perkins: $D(1)=0.8$, $D(2)=0.1$, $D(3)=0.1$, $n=3$.]

What bounds would I like: Tight bounds are preferred, of course. The conjecture above would be sufficient. But any bound that allows me to show the following is fine: For some $n\in O\bigl(\sqrt{1/p_2^D}\bigr)$, we have that $p^D_n\geq\frac12$.

Relation to uniform birthday inequality: If $D$ is the uniform distribution on $N$ elements, then $p^D_2=1/N$, and $p^D_n\leq \bigl(1-\tfrac1N\bigr)^{n\choose 2}$ . Thus the conjecture holds for uniform $D$.

Approaches I tried:

Approach 1: I tried to show that, for fixed $q$, we have that $p_n^D \geq p_n^U$ where $U$ is the uniform distribution on $1/q$ elements. (Assuming that $1/q$ is an integer.) Then I would just have to find a formula for $p_n^U$ which is the uniform birthday inequality. Unfortunately, it turns out that this approach cannot work: Consider the distribution $D$ on three elements with probabilities $2/3,1/6,1/6$. Then $p_2^D=1/2$. And $p_3^D<1$. (Because there is a nonzero chance of picking three different elements.) But for $U$ being the uniform distribution on $2$ elements, we have $p^U_3=1$. Thus $p_n^D \ngeq p_n^U$ for $n=3$.

Approach 2: [EDIT: This approach cannot work because it would show the conjecture above which is wrong.] Perkins  shows implicitly in his introduction that the conjecture above (Definition 1 in ) is true for any distribution $D$ that satisfies the "repulsion inequality" (Definition 2 in ). This repulsion inequality says, in our special case and our notation: $$\Pr[X_{N+1}\in\{X_1,\dots,X_N\}|X_1,\dots,X_N\text{ all distinct}] \geq \Pr[X_{N+1}\in\{X_1,\dots,X_N\}].$$ (Here $X_1,\dots,X_{N+1}$ are i.i.d. according to $D$.) Thus, showing the repulsion property would answer my question. But I have not been able to prove the repulsion property.

Related work: I have found many references considering the Birthday inequality for non-uniform distributions, e.g., . However, in all those cases, it was only shown that $p_n^D\geq p_n^U$ where $U$ is the uniform distribution on the support of $D$ (note that the support of $D$ can be very large if $D$ has a large number of low probability events). Or they contained exact formulas for the probability $p_n^D$ from which I did not manage to derive a bound in terms of $p_2^D$. There is one question on MathOverflow that asks for the same thing (in somewhat different words), but it gives much less details and has only an incorrect answer.

 Will Perkins, Birthday Inequalities, Repulsion, and Hard Spheres, http://arxiv.org/abs/1506.02700v2

 Clevenson, M. Lawrence, and William Watkins. "Majorization and the birthday inequality." Mathematics Magazine 64.3 (1991): 183-188. http://www.jstor.org/stable/2691301

You are considering a sequence $X_1,X_2,\ldots$ of (discrete) i.i.d random variables and want an upper bound for the probability $\mathbb{P}(R>n)$ in terms of $\sqrt{\beta}$, where $\beta:= {1 \over \mathbb{P}(X_1=X_2)}$, and $R:=\inf\{ n\geq 2\,:\,X_n\in\{X_1,\ldots,X_{n-1}\}\}$ is the first time a value is repeated.

(Note that $\{ R> n\}=\{ X_1,\ldots , X_n \mbox{ are mutually distinct }\}$. Note also that you use the notation $p_n^D$ in opposite ways above: $p_n^D=\mathbb{P}(R\leq n)$ in the question, and (for the uniform distribution) $p_n^D=\mathbb{P}(R>n)$ $=\mathbb{P}(E_n)$ of the paper of Perkins.)

This view allows to use Markov's inequality: for $a>0$

$$\mathbb{P} (R\geq a)\leq \frac{\mathbb{E}(R)}{a}$$

Here (Thm. 4) it is proved that $\mathbb{E}(R)\leq 2\sqrt{\beta}$. Thus for $a>0$ $$\mathbb{P} (R\geq a\sqrt{\beta})\leq \frac{2}{a}$$ entailing the desired claim.

Remarks:

(1) the inequality for $\mathbb{E}(R)$ can be sharpened,
e.g. to $$\sqrt{\frac{\pi}{2}\beta}\leq \mathbb{E}(R)\leq \sqrt{\frac{\pi}{2}\beta} + \max_i( p_i)\, \beta\;\;,$$ but this doesn't improve the bound qualitatively.

(2) the bound is far from tight. The possible limiting distributions of ${R_n \over \sqrt{\beta_n}}$ (for a sequence $(R_n)$ with corresponding $\beta_n\longrightarrow \infty$) are known - tighter bounds must be compatible with all possible limiting shapes (your conjectured bound isn't).

• That solves my question. In fact, Theorem 3 from eprint.iacr.org/2005/318 also answers the question. Thanks. Dec 16, 2016 at 10:51

Let $X_i$ take values $x_1,x_2,\dots$ with probabilities $p_1,p_2,\dots$

Define the events $$A_i = \{\exists j\neq i: X_i = X_j\}$$ By the Chung-Erdős inequality, $$p^D_n = P\left(\bigcup_{i=1}^n A_i\right) \ge \frac{\big(\sum_{i=1}^n P(A_i)\big)^2}{\sum_{i=1}^n P(A_i) + \sum_{i\neq j}P(A_i\cap A_j)}\\ = \frac{n^2P(A_1)^2}{nP(A_1) + n(n-1)P(A_1\cap A_2)}.$$ Now $$P(A_i) = 1- \sum_{m\ge 1} p_m (1-p_m)^{n-1} \approx 1-\sum_{m\ge 1} (p_m - (n-1) p_m^2)= (n-1)p^D_2 .$$ Further, $$P(A_1\cap A_2)\le \sum_{m\ge 1} p_m^2 + (n-2)(n-3)\sum_{m'\neq m''}(p_{m'})^2(p_{m''})^2\\\le p_2^D +n(n-1)(p_2^D)^2.$$ Therefore, $$p_n^D \gtrsim \frac{n^2(n-1)^2(p_2^D)^2}{2n(n-1)p_2^D + n^2(n-1)^2(p_2^D)^2}.$$ Taking now $n\sim C(p_2^D)^{-1/2}$ with $C>1$, we get $$p_n^D \gtrsim \frac{C^4}{2C^2 + C^4}>\frac13.$$

Though this is quite on a sketchy side, but may be useful. My point is that the Chung-Erdős inequality should do the trick.

• Using the Chung-Erdős inequality is a nice approach, but I don't see how to fill in the details (i.e., the $\approx$'s). For a rigorous analysis, we need to lower bound $P(A_1)$ by something close to $(n-1)p_2^D$ (upper bound is easy using Bernouilli inequality). The best I seem to be able to come up with is $P(A_1)\leq \sum_m p_me^{-n/p_m}$ which does not seem to help... Dec 16, 2016 at 10:38
• @DominiqueUnruh, I agree. The problem arises once the distribution is away from the uniform. Then one needs better estimates for $\sum_{i\neq j} P(A_i\cap A_j)$. Dec 16, 2016 at 14:26