# Probability of duplicate free sample of iid discrete random sample

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.

-

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