# Birthday problem for non-uniform probabilities

Consider birthday problem generalization to non-uniform day probabilities:

Draw $$k$$ IID samples from multinomial distribution $$\mathcal{P}$$ over $$d$$ outcomes, $$n=1$$ trials and outcome probability vector $$\mathbf{p}$$ $$\mathbf{p}=p_1,p_2,\ldots,p_d$$

Let $$s_1,\ldots,s_k$$ represent $$k$$ IID draws from $$\mathcal{P}$$. What is the smallest $$k$$ such that the probability of having a collision in $$s_1,\ldots,s_k$$ is at least 50%?

$$s_1,\ldots,s_k$$ is considered to have a collision iff $$\exists m>n$$ such that $$s_m=s_n$$

In numerical simulations, the following appears to be a good fit $$k\approx \sqrt{\frac{\pi}{2\|\mathbf{p}\|^2}}$$ Why?

The formula looks equivalent to Robert Israel's formula of numbers of draws until collision where $$R=\frac{1}{\|\mathbf{p}\|^2}$$ plays the role of $$d$$

Here's the simulation, I take distributions of the form $$p_i=c_1 i^{c_2}$$ with varying $$c_2$$ and plot the smallest group size at which half the trials get a collision against the value of $$R=\frac{1}{\|\mathbf{p}\|^2}$$.

(crossposted on crossvalidated.SE)

• What do you mean by "the same class"? Commented May 4, 2023 at 14:09
• I mean -- "landing in the same bucket", where you have $d$ buckets with corresponding probabilities $p_1,\ldots,p_d$ and sampling IID with replacement Commented May 4, 2023 at 14:10
• Can you just give a formal statement of the problem, without buckets, classes, etc.? Commented May 4, 2023 at 14:11
• It also looks like your "multinomial" distribution corresponds to just one trial ($n=1$ on Wikipedia). Commented May 4, 2023 at 14:16
• When the $p_j$'s are all the same, the constant factor is, not $\sqrt{\pi/2}=1.253\dots$, but $\sqrt{2\ln2}=1.177\dots$. Commented May 4, 2023 at 14:36

$$\newcommand{\PP}{\mathcal P}\newcommand{\np}{\|\mathbf p\|}\newcommand{\pmax}{p_{\max}}\newcommand{\X}[2]{X_{\{#1,#2\}}}\newcommand{\sub}[3]{#1_{\{#2,#3\}}}\newcommand{\Ga}{\Gamma}\newcommand\la\lambda$$The correct constant factor is, not $$\sqrt{\pi/2}=1.253\ldots$$, but $$\begin{equation*} c_*:=\sqrt{2\ln2}=1.177\ldots. \tag{10}\label{10} \end{equation*}$$

Indeed, let $$Y_1,\dots,Y_d$$ be independent random variables (r.v.'s) such that $$P(Y_a=j)=p_j$$ for all $$a\in[k]:=\{1,\dots,k\}$$ and $$j\in[d]$$. Let $$\PP_k$$ denote the set of all subsets of $$[k]$$ of cardinality $$2$$. For each set $$\{a,b\}\in\PP_k$$, let $$\begin{equation*} \X ab:=1(Y_a=Y_b). \end{equation*}$$ Let $$\begin{equation*} \np:=\sqrt{\sum_{j\in[d]}p_j^2}\quad\text{and}\quad \pmax:=\max_{j\in[d]}p_j. \end{equation*}$$ Let $$\begin{equation*} P_k:=P(S_k=0),\quad\text{where}\quad S_k:=\sum_{\{a,b\}\in\PP_k}\X ab. \tag{20}\label{20} \end{equation*}$$

Theorem 1. If $$\begin{equation*} \np\to0, \tag{25}\label{25} \end{equation*}$$ $$\begin{equation*} \pmax=o(\np), \tag{30}\label{30} \end{equation*}$$ and $$\begin{equation*} k\sim\frac c\np \tag{40}\label{40} \end{equation*}$$ for some real $$c>0$$, then $$\begin{equation*} P_k\to e^{-c^2/2}. \tag{50}\label{50} \end{equation*}$$ In particular, if $$c=c_*$$ (with $$c_*$$ as in \eqref{10}), then $$\begin{equation*} P_k\to1/2. \end{equation*}$$

Remark: Condition \eqref{30} means that the effective number, $$\np^2/\pmax^2$$, of "calendar dates" in this non-uniform version of the birthday "paradox" is large. In particular, if $$p_1=\cdots=p_d=1/d$$, then this effective number of "calendar dates" is $$d$$, the actual number of "calendar dates" in the usual, uniform version of the birthday "paradox".

Remark: The probability $$P_k$$ can be interpreted as the probability of not having the same birthday for any two of the $$k$$ i.i.d. individuals given that, for each $$j\in[d]$$, the probability of a birthday on day $$j$$ is $$p_j$$.

The proof of Theorem 1 is a direct application of a result on Stein's method for Poisson approximation. Such an application is possible because the random indicators $$\X ab$$ are almost independent. Specifically, in Theorem 2.5 on p.70, let $$\Ga:=\PP_k$$, $$\sub\Ga ab^s:=\{\{c,d\}\in\Ga\colon|\{c,d\}\cap\{a,b\}|=1\}$$, and $$\sub\Ga ab^w:=\{\{c,d\}\in\Ga\colon|\{c,d\}\cap\{a,b\}|=0\}$$, where $$|\cdot|$$ denotes the cardinality.

Note that for each $$i\in\Ga$$ we have $$EX_i=\np^2=E(X_i|W_i)$$ (since $$X_i$$ is independent of $$W_i=\sum_{j\in\Ga_i^w}X_j$$) and hence $$\begin{equation*} \la=\binom k2\np^2\sim k^2\np^2/2\to c^2/2; \tag{60}\label{60} \end{equation*}$$ $$EZ_i\le2k\np^2$$; and $$EX_iZ_i\le2k\np^2\pmax$$. Also, $$k_2(\la)\le1$$ (and also $$k_1(\la)\le1$$, but in this case $$k_1(\la)$$ will get multiplied by $$0$$ anyway). We thus conclude that $$\begin{equation*} |P_k-e^{-\la}|\le\frac{k^2}2\,(\np^2(\np^2+2k\np^2)+2k\np^2\pmax)\to0, \end{equation*}$$ in view of the conditions \eqref{25}, \eqref{30}, and \eqref{40}. So, in view of \eqref{60}, we get \eqref{50}. $$\quad\Box$$

Relation \eqref{50} is illustrated in this Mathematica notebook. At the end of the notebook, one can see graphs $$\{(c,\tilde P_k/e^{-c^2/2})\colon c\in\frac{c_*}5\,\{1,\dots,10\}\}$$ for simulated values $$\tilde P_k$$ of $$P_k$$, $$p_j=j/\sum_{i\in[d]}i$$ for $$j\in d$$, $$k=\lceil c/\np\rceil$$, $$d=500$$ with $$1000$$ simulations (penultimate graph), and $$d=1000$$ with $$2000$$ simulations (last graph). We see good agreement with \eqref{50} for values of $$c$$ around and/or to the left of $$c_*$$, but this agreement seems worse for larger values of $$c$$ -- which may be caused by relatively small values of the limit probability $$e^{-c^2/2}$$, which is therefore harder to simulate.

Added: A result more general than Theorem 1 above is Theorem 4 by Camarri and Pitman, which states the following (in terms of the present answer):

Suppose that $$\pmax\to0$$ (which of course implies $$d\to\infty$$ and is equivalent to \eqref{25}). Suppose also that for each $$j=1,2,\dots$$ and some $$t_j$$ we have $$$$p_j/\np\to t_j. \tag{70}\label{70}$$$$ (So, necessarily $$t_j\in[0,1]$$ for all $$j$$.) Then, for $$k$$ as in \eqref{40},
$$\begin{equation*} P_k\to Q(c):=e^{-c^2(1-\sum_j t_j^2)/2}\prod_j(1+t_j c)e^{-t_j c}. \tag{80}\label{80} \end{equation*}$$ Moreover, condition \eqref{70} is necessary for $$P_k$$ to converge for all real $$c>0$$.

(Thanks to kodlu for the link to a question containing a reference to the paper by Camarri and Pitman.)

Clearly, Theorem 1 in this answer is a special case of the just stated theorem by Camarri and Pitman: specifically, our Theorem 1 corresponds to the case when $$t_j=0$$ for all $$j$$. However, the proof of Theorem 1 presented above seems much simpler than the proof of the theorem by Camarri and Pitman. Also, the equation $$e^{-c^2/2}=1/2$$ is much easier to solve (to get the solution $$c=c_*$$ as in \eqref{10}) than the equation $$Q(c)=1/2$$ in general, with $$Q(c)$$ as defined in \eqref{80}.

• more general, related: mathoverflow.net/questions/263368/… Commented May 4, 2023 at 20:51
• @kodlu : Thank you for your comment. I did suspect that this result should be known, and (at least to me) this is a case when it is easier to prove a result than to find it in the literature. Commented May 4, 2023 at 21:09
• yes, your answer is nice, and of course the $\ell_2$ norm of the probability vector is the collision probability and is related to the Renyi entropy of order 2 which comes up in some cryptographic brute force computations Commented May 4, 2023 at 21:11
• @kodlu : Thank you for your further comment. Commented May 4, 2023 at 21:17