8
$\begingroup$

The classic birthday paradox considers all $n$ possible choices to be equally likely (i.e. every day is chosen with probability $1/n$) and once $\Omega(\sqrt{n})$ days are chosen, the probability of $2$ being the same, is a constant. I'm wondering if someone could point me to an analysis that also works for a non-uniform distribution of days?

$\endgroup$
3
  • 2
    $\begingroup$ Note that such a solution would implicitly then include the solutions for $m<n$ in the even distribution case. In general, I believe you can prove that it cannot take longer with another distribution - that is, the "even distribution" is the worst case in some sense. If $p$ is a probability on $1,...,n$ and $b(p)$ is the birthday number for $p$ - the number at which the odds of two selections being equal out $b(p)$ selections is greater than $1/2$ - then $b(p)$ is maximized when $p$ is the even distribution. $\endgroup$ Aug 1, 2012 at 18:05
  • 2
    $\begingroup$ It's not clear what the text "is a constant" applies to above. $\endgroup$ Aug 1, 2012 at 18:10
  • 5
    $\begingroup$ In Exercise 13.7 of The Cauchy-Schwarz Master Class, J. Michael Steele uses Schur convexity to show that uniform probabilities are least likely to give birthday matches. So non-uniform birthdays give us a better chance of an early match. $\endgroup$
    – user940
    Aug 1, 2012 at 19:22

2 Answers 2

5
$\begingroup$

Maybe those can help you (yes, I know this thread is old, but maybe the answer can be useful to someone else)

http://eprint.iacr.org/2010/616.pdf

http://www.ism.ac.jp/editsec/aism/pdf/044_3_0479.pdf

$\endgroup$
0
$\begingroup$

I found these two articles that are quite digestible.

APPROXIMATIONS TO THE BIRTHDAY PROBLEM WITH UNEQUAL OCCURRENCE PROBABILITIES AND THEIR APPLICATION TO THE SURNAME PROBLEM IN JAPAN*, S. Mase, 1991

THE BIRTHDAY PROBLEM WITH UNEQUAL PROBABILITIES, J. Klotz, 1979

$\endgroup$

You must log in to answer this question.

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