**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}$ [1]. 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 [1] shows implicitly in his introduction that the conjecture above (Definition 1 in [1]) is true for any distribution $D$ that satisfies the "repulsion inequality" (Definition 2 in [1]). 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., [2]. 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.

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

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