← 返回数学题库
157概率中等derivationmedium

Non-Uniform Birthdays Increase Collision Probability

题目

Suppose dd days have birthday probabilities p1,p2,,pdp_1, p_2, \ldots, p_d with jpj=1\sum_j p_j = 1 (not necessarily uniform). For nn people whose birthdays are independent draws from this distribution:

(a) Show that for n=2n = 2, P(collision)=j=1dpj21dP(\text{collision}) = \sum_{j=1}^{d} p_j^2 \ge \frac{1}{d}, with equality if and only if all pj=1dp_j = \frac{1}{d}.

(b) Deduce that the uniform distribution minimizes the collision probability among all distributions on dd days. Give a one-line intuitive explanation for why non-uniformity helps collisions.

解题计时

0:00

提交作答时记录,用于后续平均用时统计。

你的答案

b.deduction