An extension of the birthday problem

I have no idea for your main question, but I know how you got, for the uniform distribution case, a formula distinct from that of Wikipedia -- because I did the same mistake earlier today.

You select $n$ values out of a space of size $d$, each selection being uniformly random. We assume that $n \ll d$ (but not necessarily that $n^2 \ll d$, which is the crucial point). The probability of there being no collision is:

$$ p(n,d) = \frac{d!}{d^n(d-n)!} $$

(there are $\frac{d!}{(d-n)!}$ possible selections with no collisions, out of $d^n$ if we allow collisions).

Using Stirling's formula ($k! \approx \sqrt{2\pi k}(\frac{k}{e})^k)$, we get:

$$ p(n, d) \approx d^{-n} \sqrt{\frac{d}{d-n}} \left(\frac{d}{e}\right)^d\left(\frac{d-n}{e}\right)^{n-d} $$

Since $n \ll d$, the part with the square root is very close to $1$, so we ignore it. The expression then becomes:

$$ p(n, d) \approx e^{-n} \left(1-\frac{n}{d}\right)^{n-d} = e^{-n + (n-d)\ln (1-\frac{n}{d})}$$

No we replace the log with its Taylor approximation, and, that's the tricky point, you have to use degree 2. This means that:

\begin{eqnarray} -n + (n-d)\ln (1-\frac{n}{d}) &=& -n + (n-d)\left(-\frac{n}{d} - \frac{n^2}{2d^2} + O\left(\frac{n^3}{d^3}\right)\right) \\ &=& -\frac{n^2}{d} - \frac{n^3}{2d^2} + \frac{n^2}{2d} + O\left(\frac{n^3}{d^2}\right) \\ &=& -\frac{n^2}{2d} + O\left(\frac{n^3}{d^2}\right) \end{eqnarray}

Hence the result:

$$ p(n,d) \approx e^{-\frac{n^2}{2d}} $$

which is the formula given in the Wikipedia page on the birthday "paradox". In the expression above, when we replace the log with its approximation, the degree 1 terms cancel out, which is why we have to go to degree 2. Stopping at degree 1 was my mistake and, I presume, yours too.

Let's rephrase the problem:

There are $m$ bins, and $n$ items placed independently into a random bin with probability $p_k$ of going into bin $k\in\{1,\ldots,m\}$. What is the likelihood that no to items go into the same bin?

Let's start with an approximate solution which is good for giving some intuition about the problem and works well as long as $n\ll m$.

For any to items, the probability of them going into the same bin is $q=\sum_{k=1}^m p_k^2$. Hence, the probability that they do not go into the same bin is $1-q$. Since there are $n(n-1)/2$ different pairs of item, if we make the approximation that any two pairs of items are independent (true if pairs have no items in common and almost true if the two pairs have one item in common), we find the likelihood that no pair go into the same bin to be $\approx(1-q)^{n(n-1)/2}\approx e^{qn(n-1)/2}$.

Now, let's do this a bit more formally. If we define the polynomial $$F(x)=\prod_{k=1}^m (1+p_kx)=\sum_{j=0}^m \frac{f_j x^j}{j!},$$ the coefficient $f_n$ is the likelihood that that $n$ items go into $n$ distinct bins: sums over all different ways to pick $n$ bins and the likelihood that the $n$ items be placed into these bins in any order (the factor $n!$).

We can now make an approximation: $$ \begin{split} F(x) =&\prod_{k=1}^m (1+p_kx) = \exp\left\{\sum_{j=1}^m\ln(1+p_jx)\right\}\\ =&\exp\left\{\sum_{j=1}^m p_jx-\frac{p_j^2x^2}{2}+\frac{p_j^3x^3}{3}-\cdots\right\}\\ =&\exp\left\{x-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right\}\\ =&e^x\cdot e^{-q_2x^2/2}\cdot e^{q_3x^3/3}\cdot e^{-q_4x^4/4}\cdots\\ \end{split} $$ where $q_r=\sum_{k=1}^m p_k^r$ (so the above $q=q_2$ while $q_1=1$). We can show that $q_k\le q_2^{k-1}$ (e.g. from $q_r^2\ge q_{r-1}q_{r+1}$) which tells us $q_2$ is the dominant adjustment.

If we make the expansion $$ \begin{split} \exp\left\{-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right\} =&\sum_{k=0}^\infty\frac{1}{k!} \left(-\frac{q_2x^2}{2}+\frac{q_3x^3}{3}-\cdots\right)^k\\ =&1-a_2x^2+a_3x^3-a_4x^3+\cdots\\ \end{split} $$ we get $a_2=q_2/2$, $a_3=q_3/3$, $a_4=q_4/4-q_2^2/8$, etc. Entering these into the power expansion for $F(x)$, we get $$ \begin{split} F(x)=&e^x\cdot\left(1-a_2x^2+a_3x^3-a_4x^3+\cdots\right)\\ =&\sum_{n=0}^\infty\left(\frac{1}{n!} -\frac{a_2}{(n-2)!}-\frac{a_3}{(n-3)!}-\cdots\right)\cdot x^n\\ =&\sum_{n=1}^\infty\big(1-a_2n(n-1)+a_3n(n-1)(n-2)-\cdots\big)\cdot\frac{x^n}{n!}\\ \end{split} $$ so the effect of $a_rx^r$ is an adjustment $a_rn(n-1)\cdots(n-r+1)$ which for $r\ll n$ has the same magnitude as $a_rn^2$.

If we ignore $q_r$ for $r>2$ and take the effect of $a_{2r}x^{2r}$ to be $\approx a_{2r}[n(n-1)]^r$ (which is true for $r=1$ but only approximate for $r>1$, we get the original approximation: $e^{-q_2n(n-1)/2}$.