Thumbnail
Access Restriction
Open

Author Galbraith, Steven D. ♦ Holmes, Mark
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Non-uniform Birthday Problem ♦ Birthday Problem ♦ Certain Variant ♦ Different Colour ♦ Amusing Paradox ♦ Expected Number ♦ Discrete Logarithm Problem
Abstract Abstract. We consider a generalisation of the birthday problem that arises in the analysis of algorithms for certain variants of the discrete logarithm problem in groups. More precisely, we consider sampling coloured balls and placing them in urns, such that the distribution of assigning balls to urns depends on the colour of the ball. We determine the expected number of trials until two balls of different colours are placed in the same urn. As an aside we present an amusing “paradox ” about birthdays.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2012-01-01