8
$\begingroup$

I am looking into some properties of some hash functions. It is rather a short hash $16bit$ which yields up to $65536$ different values.

Given that I have $M$ samples which populate $N$ out of $65536$ bins, with $M>N$, is there a way to do a maximum likelihood estimation on the $M$ parameter ($M$ is unknown)? I would like to avoid simulations as I think that they tend to be computationally expensive and quite variable for $M >N$ and have stability issues.

To translate it in the birthday paradox can I predict how many people were in my sample given that I now that there are $N$ different birthdays in a year found in the sample?

Is there a closed form solution I can approximate this result?

Improve this question
$\endgroup$
0
9
$\begingroup$

This is a problem amenable to maximum likelihood estimation, provided one can write down the likelihood or design a latent variable representation to run an EM algorithm.

Let us denote $\bar N$ for the number of days/boxes (like $\bar N=365$ in the original problem) and $M$ for the number of individuals. Borrowing from this paper by Fisher, Funk, and Sams, the probability to have $r$ distinct birth-days in a population of $M=m$ individuals writes as $$\mathbb P(R=r)=\frac{\bar N!}{(\bar N-r)!}\frac{m!}{\bar N^m} \sum_{(r_1,\ldots,r_m);\\\sum_1^m r_i=r\ \&\\\sum_1^m ir_i=m}1\Big/\prod_{j=1}^m r_j! (j!)^{r_j}\tag{1}$$ where the $r_j$'s correspond to the number of days with exactly $j$ simultaneous or shared birthdays. But Feller (1970, p.102) gives the simpler representation $$\mathbb P(R=r)={\bar{N} \choose r}\sum_{\nu=0}^r (-1)^{\nu}{r\choose\nu}\left(1-\frac{T-r+\nu}T \right)^m$$ which fits well an empirical distribution when $\bar N$ is small enough.

Feller (1970, pp.103-104) justifies an asymptotic Poisson approximation with parameter$$\lambda(M)=\bar{N}\exp\{-M/\bar N\}$$from which an estimate of $M$ can be derived. With the birthday problem as illustration (pp.105-106)!

And if I understand properly the "strong birthday" problem in Das Gupta (2005)](https://www.math.ucdavis.edu/~tracy/courses/math135A/UsefullCourseMaterial/birthday.pdf) the number of "unique" people (not sharing a birthday with anyone else) is distributed as: $$\mathbb P(R'=r)=\sum_{i=r}^m (-1)^{i-r} \frac{i!}{r!(i-r)!}\frac{\bar N!m!(\bar N-i)^{m-i}}{i!(\bar N-i)!(m-i)!\bar N^m}\tag{2}$$

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ +1. I obtained something that looks very like the second formula by solving a Markov chain formulation of the problem (where the states count the numbers of distinct birthdays). It works well, but because it involves huge amounts of cancellation, it is not useful for double precision calculations once the number of possible birthdays exceeds 50 or so. (Your formula doesn't look quite right: in particular, $m!$ appears as a factor of both the numerator and denominator. You ought to explain what you mean by "$\bar N,$" too.) $\endgroup$ – whuber♦ Jan 19 at 20:53
  • $\begingroup$ Thank you @whuber. I corrected (2). This "strong birthday" formula is (4) in Anirban's paper., later reproduced in a Significance article. $\endgroup$ – Xi'an Jan 20 at 7:29
  • 2
    $\begingroup$ It is noteworthy that the Significance article refers to the first formula as "fiendish." I have found ways to apply the second formula for values of $\bar N$ up to a few hundred, and for slightly higher values and special values of $N,$ but beyond that all precision disappears (the probabilities are expressed as sums and differences of quantities of $10^{20}$ and greater). Thus, finding good approximations is important. $\endgroup$ – whuber♦ Jan 20 at 15:09
  • $\begingroup$ @whuber Yes, numerical method (2) looks unstable. $ -(1)^{i-r} $ causes the subtraction of similar numbers which can amplify the machine epsilon in each iteration. $\endgroup$ – Mini Fridge Jan 21 at 14:18
  • 1
    $\begingroup$ In my understanding (2) is not the correct answer in that it gives the probability of having $r$ individuals not sharing a birth date with anyone else. $\endgroup$ – Xi'an Jan 21 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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