3
$\begingroup$

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}$.

enter image description here

(crossposted on crossvalidated.SE)

$\endgroup$
19
  • $\begingroup$ What do you mean by "the same class"? $\endgroup$ Commented May 4, 2023 at 14:09
  • $\begingroup$ 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 $\endgroup$ Commented May 4, 2023 at 14:10
  • $\begingroup$ Can you just give a formal statement of the problem, without buckets, classes, etc.? $\endgroup$ Commented May 4, 2023 at 14:11
  • $\begingroup$ It also looks like your "multinomial" distribution corresponds to just one trial ($n=1$ on Wikipedia). $\endgroup$ Commented May 4, 2023 at 14:16
  • $\begingroup$ 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$. $\endgroup$ Commented May 4, 2023 at 14:36

1 Answer 1

4
$\begingroup$

$\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 \begin{equation} p_j/\np\to t_j. \tag{70}\label{70} \end{equation} (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}.

$\endgroup$
4
  • $\begingroup$ more general, related: mathoverflow.net/questions/263368/… $\endgroup$
    – kodlu
    Commented May 4, 2023 at 20:51
  • $\begingroup$ @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. $\endgroup$ Commented May 4, 2023 at 21:09
  • $\begingroup$ 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 $\endgroup$
    – kodlu
    Commented May 4, 2023 at 21:11
  • $\begingroup$ @kodlu : Thank you for your further comment. $\endgroup$ Commented May 4, 2023 at 21:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .