主题
Search

生日悖论

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

考虑概率 Q_1(n,d)，即在一个由 n 个人组成的群体中，在 d 个等可能生日中，没有两个人拥有相同的生日。 从任意一个人的生日开始，然后注意到第二个人生日不同的概率是 (d-1)/d，第三个人生日与前两个人不同的概率是 [(d-1)/d][(d-2)/d]，依此类推，直到第 n 个人。 明确地，

Q_1(n,d)=(d-1)/d(d-2)/d...(d-(n-1))/d
(1)
=((d-1)(d-2)...[d-(n-1)])/(d^(n-1)).
(2)

但这可以用阶乘表示为

Q_1(n,d)=(d!)/((d-n)!d^n),
(3)

因此，概率 P_2(n,d)，即在一个由 n 个人组成的群体中，两个或更多人确实拥有相同的生日，因此是

P_2(n,d)=1-Q_1(n,d)
(4)
=1-(d!)/((d-n)!d^n).
(5)

一般来说，令 Q_i(n,d) 表示在一个由 n 个人组成的群体中，恰好有 i 个人（不多也不少）拥有相同生日的概率。 那么，至少有 k 个人或更多人拥有相同生日的概率由下式给出：

P_k(n,d)=1-sum_(i=1)^(k-1)Q_i(n,d).
(6)

一般来说，Q_k(n,d) 可以使用以下递归关系计算：

Q_k(n,d)=sum_(i=1)^(|_n/k_|)[(n!d!)/(d^(ik)i!(k!)^i(n-ik)!(d-i)!)sum_(j=1)^(k-1)Q_j(n-ik,d-i)((d-i)^(n-ik))/(d^(n-ik))]
(7)

(Finch 1997)。 然而，计算此递归函数的时间随着 k 的增加呈指数增长，因此很快变得难以处理。

如果假设一年有 365 天，即忽略闰年的存在，并且假设生日在一年中的分布是均匀的（实际上，在美国，9 月份的出生率比平均水平高出 6% 以上；Peterson 1998），那么至少有 50% 的概率至少有两个人拥有相同生日所需的最少人数 n 满足 P_2(n,365)>=1/2。 这由 n=23 给出，因为

P_2(23,365)=(38093904702297390785243708291056390518886454060947061)/(75091883268515350125426207425223147563269805908203125)
(8)
approx 0.507297.
(9)

获得 P_2(n,d)>=1/2 所需的人数 n，对于 d=1, 2, ..., 分别是 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, ... (OEIS A033810)。 至少有 n 个生日重合的 50% 概率所需的最少人数是 1, 23, 88, 187, 313, 460, 623, 798, 985, 1181, 1385, 1596, 1813, ... (OEIS A014088; Diaconis and Mosteller 1989)。

概率 P_2(n,d) 可以估计为

P_2(n,d) approx 1-e^(-n(n-1)/2d)
(10)
approx 1-(1-n/(2d))^(n-1),
(11)

其中后者有误差

epsilon<(n^3)/(6(d-n+1)^2)
(12)

(Sayrafiezadeh 1994)。

Q_2 可以显式计算为

Q_2(n,d)=(n!)/(d^n)sum_(i=1)^(|_n/2_|)1/(2^i)(d; i)(d-i; n-2i)
(13)
=(d!)/(d^n(d-n)!)[_2F_1(1/2n,1/2(1-n);d-n+1;2)-1],
(14)

其中 (n; m) 是一个二项式系数，而 _2F_1(a,b,;c;z) 是一个超几何函数。 这给出了 P_3(n,d) 的显式公式为

P_3(n,d)=1-Q_1(n,d)-Q_2(n,d)
(15)
=1-d^(-n)d!_2F^~_1(1/2n,1/2(1-n);1+d-n;2),
(16)

其中 _2F^~_1(a,b;c;z) 是一个正则化超几何函数。

对于给定的值 p=P_k(n,d)，人数 n 的一个好的近似值可以通过解方程给出：

ne^(-n/(dk))=[d^(k-1)k!ln(1/(1-p))(1-n/(d(k+1)))]^(1/k)
(17)

解出 n 并取 [n]，其中 [n] 是上限函数 (Diaconis and Mosteller 1989)。 对于 p=0.5 和 k=1, 2, 3, ...，此公式给出 n=1, 23, 88, 187, 313, 459, 622, 797, 983, 1179, 1382, 1592, 1809, ... (OEIS A050255)，这些值与真值相差 0 到 4。 对于 n 且 p=0.5，且 k<20 的情况，一个更简单但也更差的近似值由下式给出：

n=47(k-1.5)^(3/2)
(18)

(Diaconis and Mosteller 1989)，对于 k=3, 4, ...，给出 86, 185, 307, 448, 606, 778, 965, 1164, 1376, 1599, 1832, ... (OEIS A050256)。

“近似”生日悖论，询问需要多少人才能使两个人彼此生日相差一天之内，由 Abramson 和 Moser (1970) 考虑，他们表明 14 人就足够了。 对于在 d 个可能日期中，两个人生日在 k 天之内匹配的概率达到 50-50 所需的最少人数的近似值由下式给出：

n(k,d)=1.2sqrt(d/(2k+1))
(19)

(Sevast'yanov 1972, Diaconis and Mosteller 1989)。

另请参阅

生日攻击, 巧合, 小世界问题, 苏丹嫁妆问题

使用 Wolfram|Alpha 探索

参考文献

Abramson, M. and Moser, W. O. J. "More Birthday Surprises." Amer. Math. Monthly 77, 856-858, 1970.Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 45-46, 1987.Bloom, D. M. "A Birthday Problem." Amer. Math. Monthly 80, 1141-1142, 1973.Bogomolny, A. "Coincidence." http://www.cut-the-knot.org/do_you_know/coincidence.shtml.Clevenson, M. L. and Watkins, W. "Majorization and the Birthday Inequality." Math. Mag. 64, 183-188, 1991.Diaconis, P. and Mosteller, F. "Methods for Studying Coincidences." J. Amer. Statist. Assoc. 84, 853-861, 1989.Durrett, R. "Triple Birthday Matches in the Senate: Lies, Damned Lies and ChatGPT." 19 Feb 2023. https://arxiv.org/abs/2302.09643.Feller, W. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. New York: Wiley, pp. 31-32, 1968.Finch, S. "Puzzle #28 [June 1997]: Coincident Birthdays." http://www.mathcad.com/library/LibraryContent/puzzles/puzzle.asp?num=28.Gehan, E. A. "Note on the 'Birthday Problem.' " Amer. Stat. 22, 28, Apr. 1968.Heuer, G. A. "Estimation in a Certain Probability Problem." Amer. Math. Monthly 66, 704-706, 1959.Hocking, R. L. and Schwertman, N. C. "An Extension of the Birthday Problem to Exactly k Matches." College Math. J. 17, 315-321, 1986.Hunter, J. A. H. and Madachy, J. S. Mathematical Diversions. New York: Dover, pp. 102-103, 1975.Klamkin, M. S. and Newman, D. J. "Extensions of the Birthday Surprise." J. Combin. Th. 3, 279-282, 1967.Levin, B. "A Representation for Multinomial Cumulative Distribution Functions." Ann. Statistics 9, 1123-1126, 1981.McKinney, E. H. "Generalized Birthday Problem." Amer. Math. Monthly 73, 385-387, 1966.Mises, R. von. "Über Aufteilungs--und Besetzungs-Wahrscheinlichkeiten." Revue de la Faculté des Sciences de l'Université d'Istanbul, N. S. 4, 145-163, 1939. Reprinted in Selected Papers of Richard von Mises, Vol. 2 (Ed. P. Frank, S. Goldstein, M. Kac, W. Prager, G. Szegö, and G. Birkhoff). Providence, RI: Amer. Math. Soc., pp. 313-334, 1964.Peterson, I. "MathTrek: Birthday Surprises." Nov. 21, 1998. http://www.sciencenews.org/sn_arc98/11_21_98/mathland.htm.Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 179-180, 1994.Sayrafiezadeh, M. "The Birthday Problem Revisited." Math. Mag. 67, 220-223, 1994.Sevast'yanov, B. A. "Poisson Limit Law for a Scheme of Sums of Dependent Random Variables." Th. Prob. Appl. 17, 695-699, 1972.Sloane, N. J. A. Sequences A014088, A033810, A050255, and A050256 in "The On-Line Encyclopedia of Integer Sequences."Stewart, I. "What a Coincidence!" Sci. Amer. 278, 95-96, June 1998.Tesler, L. "Not a Coincidence!" http://www.nomodes.com/coincidence.html.

在 Wolfram|Alpha 中引用

生日悖论

引用为

Weisstein, Eric W. “生日悖论。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/BirthdayProblem.html

主题分类