Problem 890: Birthday Paradox Variants

Mathematical Analysis

Theorem 1 (Exact Collision Probability)

Proof. The probability of no collision is $\frac{N}{N} \cdot \frac{N-1}{N} \cdot \frac{N-2}{N} \cdots \frac{N-n+1}{N}$. $\square$

Theorem 2 (Poisson Approximation)

For $n \ll N$:

Proof. Using $\ln(1 - k/N) \approx -k/N$ for small $k/N$:

Theorem 3 (50% Threshold)

$P(n, N) \geq 1/2$ when $n \geq \sqrt{2N \ln 2} \approx 1.1774\sqrt{N}$.

For $N = 365$: $n \geq \sqrt{2 \cdot 365 \cdot \ln 2} \approx 22.49$, so $n = 23$.

Theorem 4 ($k$-wise Collision)

The probability that some group of $k$ people share a birthday:

Theorem 5 (Non-uniform Distribution)

For non-uniform birthday probabilities $p_1, \ldots, p_N$ with $\sum p_i = 1$:

The collision probability is maximized when the distribution is uniform (by Schur-convexity).

Concrete Numerical Examples

Classical Birthday Problem ($N = 365$)

Threshold $n_{1/2}$ for Various $N$

Hash Collision Application

For a hash function with $N = 2^{128}$ outputs, 50% collision probability at $n \approx 2^{64}$ attempts (the “birthday attack”).

Coupon Collector Connection

While the birthday problem asks “when do we first see a repeat?”, the coupon collector problem asks “when do we first see all $N$ types?” The expected time is $N H_N = N \sum_{k=1}^{N} 1/k \approx N \ln N$.

Higher-Order Collisions

Expected Number of Collisions

The expected number of pairs sharing a birthday:

For $n = 23, N = 365$: $E = 253/365 \approx 0.693$.

Expected Number of Empty Bins

Variance of Collision Count

Generalized Occupancy Problems

The birthday problem is a special case of the random allocation or occupancy problem: throwing $n$ balls into $N$ bins uniformly. Key quantities:

• Probability of no empty bin: $\frac{N!}{N^n} S(n, N)$ (Stirling numbers)
• Maximum load: $\Theta(\log n / \log \log n)$ w.h.p.
• First collision: $\Theta(\sqrt{N})$ w.h.p.

Complexity Analysis

Answer

/*
 * Problem 890: Birthday Paradox Variants
 * P(n,N) = 1 - prod_{k=0}^{n-1} (1 - k/N).
 */
#include <bits/stdc++.h>
using namespace std;

double birthday_exact(int n, int N) {
    if (n > N) return 1.0;
    double p = 1.0;
    for (int k = 0; k < n; k++) p *= (double)(N - k) / N;
    return 1.0 - p;
}

double birthday_poisson(int n, int N) {
    double lam = (double)n * (n - 1) / (2.0 * N);
    return 1.0 - exp(-lam);
}

int threshold_50(int N) {
    for (int n = 1; n <= N + 1; n++)
        if (birthday_exact(n, N) >= 0.5) return n;
    return N + 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cout << fixed << setprecision(5);
    cout << "=== Birthday Problem (N=365) ===" << endl;
    for (int n : {5, 10, 20, 23, 30, 50, 70})
        cout << "P(" << n << ",365) = " << birthday_exact(n, 365) << endl;

    cout << "\n=== Thresholds ===" << endl;
    for (int N : {100, 365, 1000, 10000})
        cout << "n_50(" << N << ") = " << threshold_50(N) << endl;

    cout << "\nAnswer: P(23,365) = " << birthday_exact(23, 365) << endl;
    return 0;
}

"""
Problem 890: Birthday Paradox Variants
Collision probability: P(n,N) = 1 - prod(1-k/N) for k=0..n-1.
"""

from math import log, exp, comb, factorial, sqrt

def birthday_exact(n, N):
    """Exact collision probability."""
    if n > N:
        return 1.0
    prob_no_collision = 1.0
    for k in range(n):
        prob_no_collision *= (N - k) / N
    return 1.0 - prob_no_collision

def birthday_poisson(n, N):
    """Poisson approximation."""
    lam = n * (n - 1) / (2 * N)
    return 1.0 - exp(-lam)

def threshold_50(N):
    """Find smallest n where P(n,N) >= 0.5."""
    for n in range(1, N + 2):
        if birthday_exact(n, N) >= 0.5:
            return n
    return N + 1

def birthday_kwise(n, N, k):
    """Approximate probability of k-wise collision."""
    lam = comb(n, k) / N**(k-1)
    return 1.0 - exp(-lam)

# --- Verification ---
print("=== Classical Birthday Problem (N=365) ===")
N = 365
print(f"{'n':>4} {'Exact':>10} {'Poisson':>10} {'Diff':>10}")
for n in [5, 10, 20, 23, 30, 40, 50, 57, 70]:
    exact = birthday_exact(n, N)
    poisson = birthday_poisson(n, N)
    print(f"{n:>4} {exact:>10.5f} {poisson:>10.5f} {abs(exact-poisson):>10.5f}")

print(f"\n=== 50% Threshold ===")
for N in [100, 365, 1000, 10000, 100000]:
    n50 = threshold_50(N)
    approx = 1.1774 * sqrt(N)
    print(f"  N={N:>6}: n_50={n50:>4}, 1.177*sqrt(N)={approx:.1f}")

print(f"\n=== Hash Collision ===")
for bits in [32, 64, 128, 256]:
    N = 2**bits
    n50_approx = int(1.1774 * sqrt(N))
    print(f"  {bits}-bit hash: 50% collision at ~2^{bits//2} = {2**(bits//2)}")

print(f"\n=== k-wise Collisions (N=365) ===")
for k in [2, 3, 4]:
    for n in [23, 50, 100, 200]:
        p = birthday_kwise(n, 365, k)
        print(f"  k={k}, n={n}: P ~ {p:.5f}")

answer = birthday_exact(23, 365)
print(f"\nAnswer: P(23, 365) = {answer:.10f}")

# --- 4-Panel Visualization ---