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

Question

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

Answer 1

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

Answer 2

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.