7

Let $\{X_1,\ldots,X_n\}$ be independent identically distributed discrete random variables. I am interested in computing the probability of the event that the sample is duplicate free: $$ \mathbb{P}\left( \bigcap_{i<j} \{ X_i \not= X_j\}\right) $$ in terms of $p_2 = \mathbb{P}\left(X_1 = X_2\right)$, $p_3=\mathbb{P}\left(X_1 = X_2 = X_3\right)$, ..., $p_n = \mathbb{P}\left(X_1 = X_2 = X_3=\ldots=X_n\right)$.

Special case
If $X_k$ are uniformly distributed with the size of the sample space being $d$, this is a classic birthday problem with the answer: $$ \mathbb{P}\left( \bigcap_{i<j} \{ X_i \not= X_j\}\right) = \frac{n!}{d^n} \binom{d}{n} = \sum_{k=1}^n \frac{s(n,k)}{d^{n-k}} $$ where $s(n,k)$ denotes the Stirling number of the first kind.

Motivation
Consider IEEE floating point number with mantissa $m$ encoded as $d$-tuple of significant binary digits (i.e. the first bit is always 1), and integer binary exponent $e$. For a random real $0<x<1$, bits are iid Bernoulli(1/2) random variables, and $-e$ is a Geometric(1/2) random variable. I am interested in computing the probability of the size $n$ sample having a duplicate.

My approach
Applying inclusion-exclusion principle, the complementary probability is $$ \sum_{i<j} \mathbb{P}\left(X_i = X_j\right) - \sum_{i<j,i<p<q} \mathbb{P}\left(X_i = X_j, X_p=X_q\right)+\ldots = \\ \binom{n}{2} p_2 - 3 \binom{n}{4} p_2^2 - 2 \binom{n}{3} p_3 + \ldots $$

Solutions, ideas, references are welcome.

Sasha
  • 70,631

1 Answers1

2

The reference solving the birthday problem for arbitrary distribution of birthdays is

Shigeru Mase, "Approximations to the birthday problem with unequal occurrence probabilities and their application to the surname problem in Japan," Ann. Inst. Statist. Math., vol. 44, no. 3, pp. 379-499 (1992).

It uses quite a neat argument involving generating functions. First, note that $$ r_n := \mathbb{P}\left(\bigcap_{1\leqslant i<j \leqslant n} \{X_i \not= X_j\}\right) = n! \sum_{1 \leqslant i_1 < i_2 < \ldots < i_{n-1} < i_n \leqslant n} \pi_{i_1} \pi_{i_2} \cdots \pi_{i_{n}} = n! [t^n] \prod_{k \geqslant 1} \left(1 + \pi_k t\right) $$ where $\pi_k = \mathbb{P}(X=k)$. Therefore $$ 1 + \sum_{n=1}^\infty \frac{r_n}{n!} t^n = \prod_{k \geqslant 1} \left(1 + \pi_k t\right) = \exp\left( \sum_{k \geqslant 1} \log\left(1+\pi_k t\right)\right) = \exp\left( \sum_{s=1}^\infty \frac{(-1)^{s-1}}{s} t^s \sum_{k \geqslant 1} \pi_k^s\right) = \exp\left( 1 + \sum_{s=2}^\infty \frac{(-1)^{s-1}}{s} t^s p_s\right) $$ This gives the expression for $r_n$ as the complete Bell polynomial: $$ r_n = B_n\left(1, -p_2, \ldots, (-1)^{n-1} (n-1)! p_n\right) \tag{1} $$ In particular, assuming $r_0 =1$ the above result implies the recurrence equation for the non-occurrence probabilities $r_n$: $$ r_n = \sum_{k=1}^n (-1)^{k-1} \frac{(n-1)!}{(n-k)!} p_k r_{n-k} \tag{2} $$

Large $n$ asymptotics (with $n \cdot \max\limits_{k \geqslant 1} \pi_k$ being small) is also worked out in the article: $$ r_n \approx \exp\left(-\binom{n}{2} p_2 - \binom{n}{3}\left( 3 p_2^2 - 2 p_3 \right) + \cdots \right) $$

Sasha
  • 70,631