**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](https://mathoverflow.net/q/255880/101775) 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>



Birthday inequality for non-uniform distributions for fixed collision probability (random allocation, collision probability)
I reformulate slightly, please check.


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](http://eprint.iacr.org/2005/318) (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](http://projecteuclid.org/euclid.ejp/1457376437) - tighter bounds must be compatible with all possible limiting shapes (your conjectured bound isn't).


