Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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