主題
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)。

另請參閱

生日攻擊, 巧合, 小世界問題, 蘇丹嫁妝問題

使用 探索

參考文獻

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.

在 中引用

生日悖論

引用為

Weisstein, Eric W. “生日悖論。” 來自 Web 資源。 https://mathworld.tw/BirthdayProblem.html

主題分類