3

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[ij.Xi=Xj] (as a function of pD2)?

Conjecture: pDn1(1pD2)(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 nO(1/pD2), we have that pDn12.

Relation to uniform birthday inequality: If D is the uniform distribution on N elements, then pD2=1/N, and pDn(11N)(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 pDnpUn 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

\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
  • \begingroup That solves my question. In fact, Theorem 3 from eprint.iacr.org/2005/318 also answers the question. Thanks. \endgroup Commented Dec 16, 2016 at 10:51
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 Commented 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
    Commented Dec 16, 2016 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .