Birthday Problem

The birthday problem asks how many people must be in a group for a shared birthday to become likely. Under a uniform 365-day model, 23 people give a probability above one half of at least one matching pair.

Complementary probability: The probability of an event equals one minus the probability that it does not occur. It is easier to count groups with no shared birthday, then subtract their probability from one.
Independent events: Events are independent when the occurrence of one does not change the probability of another. The standard calculation treats each person's birthday as an independent draw.
Cryptographic hash function: A function that maps data of arbitrary size to a fixed-length value designed for security properties. Hash outputs behave like birthday values when estimating accidental collisions.
Birthday paradox: The surprising result that a shared birthday becomes likely in a group much smaller than many people expect. This name emphasizes the counterintuitive conclusion of the birthday problem.
Pigeonhole principle: A counting principle stating that placing more objects than containers forces at least one container to hold multiple objects. It guarantees a match once a group exceeds the number of possible birthdays.
Uniform distribution: A probability distribution that assigns equal probability to every outcome in its stated set. The classic version gives each of 365 days equal chance.
Hash collision: An event in which distinct inputs to a hash function produce the same output. The birthday calculation estimates how many hashes are needed before a collision becomes likely.
Coupon collector's problem: A probability problem asking how many random draws are needed to collect every type in a finite set. It concerns repeated sampling too, but seeks complete coverage rather than the first match.
Birthday attack: A cryptographic method that exploits collision probabilities to find two inputs with the same hash value. It applies the same rapid growth of pairwise matches to cryptographic hashes.
Sample space: The set of all possible outcomes of a random experiment. Birthday assignments define the outcomes whose probabilities are counted.

Linked from 11 pages