3
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$ Dec 16, 2016 at 10:38
  • $\begingroup$ @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)$. $\endgroup$
    – zhoraster
    Dec 16, 2016 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.