Question: Consider a distribution D, and n i.i.d. random variables Xi, all distributed according to D. Let pD2:=Pr[X1=X2]. What is a lower bound for pDn:=Pr[∃i≠j.Xi=Xj] (as a function of pD2)?
Conjecture: pDn≥1−(1−pD2)(n2). [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∈O(√1/pD2), we have that pDn≥12.
Relation to uniform birthday inequality: If D is the uniform distribution on N elements, then pD2=1/N, and pDn≤(1−1N)(n2) [1]. Thus the conjecture holds for uniform D.
Approaches I tried:
Approach 1: I tried to show that, for fixed q, we have that pDn≥pUn 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 pUn 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 pD2=1/2. And pD3<1. (Because there is a nonzero chance of picking three different elements.) But for U being the uniform distribution on 2 elements, we have pU3=1. Thus pDn≱ 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