Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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. –  Thomas Andrews Aug 1 '12 at 18:05
1  
It's not clear what the text "is a constant" applies to above. –  Thomas Andrews Aug 1 '12 at 18:10
3  
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. –  Byron Schmuland Aug 1 '12 at 19:22

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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