 Author
 Year
 2014
 Title
 Generalized birthday problems in the largedeviations regime
 Journal
 Probability in the Engineering and Informational Sciences
 Volume  Issue number
 28  1
 Pages (fromto)
 8399
 Document type
 Article
 Faculty
 Faculty of Science (FNWI)
 Institute
 Kortewegde Vries Institute for Mathematics (KdVI)
 Abstract

This paper considers generalized birthday problems, in which there are d classes of possible outcomes. A fraction f i of the N possible outcomes has probability α i /N, where $\sum_{i=1}^{d} f_{i} =\sum_{i=1}^{d} f_{i}\alpha_{i}=1$. Sampling k times (with replacements), the objective is to determine (or approximate) the probability that all outcomes are different, the socalled uniqueness probability (or: nocoincidence probability). Although it is trivial to explicitly characterize this probability for the case d=1, the situation with multiple classes is substantially harder to analyze.
Parameterizing k≡ aN, it turns out that the uniqueness probability decays essentially exponentially in N, where the associated decay rate ζ follows from a variational problem. Only for small d this can be solved in closed form. Assuming α i is of the form 1+φ i ɛ, the decay rate ζ can be written as a power series in ɛ; we demonstrate how to compute the corresponding coefficients explicitly. Also, a logarithmically efficient simulation procedure is proposed. The paper concludes with a series of numerical experiments, showing that (i) the proposed simulation approach is fast and accurate, (ii) assuming all outcomes equally likely would lead to estimates for the uniqueness probability that can be orders of magnitude off, and (iii) the powerseries based approximations work remarkably well.  URL
 go to publisher's site
 Language
 English
 Note
 With Eurandom
 Permalink
 http://hdl.handle.net/11245/1.438236
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.