主題
Search

連串

下載 Mathematica 筆記本下載 Wolfram 筆記本

連串是指一個多於一個連續相同結果的序列，也稱為聚集。

設 R_p(r,n) 為在 n 次獨立拋擲 硬幣（即，n 次 伯努利試驗）中出現 r 次或更多連續正面的機率。這等同於從一個裝有兩個可區分物體的甕中重複抽取，每次抽取後放回。設獲得正面的機率為 0<p<1。那麼，關於 R_p(r,n) 有一個漂亮的公式，以 生成函式 的係數給出

F_p(r,s)=(p^rs^r(1-ps))/(1-s+(1-p)p^rs^(r+1))=sum_(i=r)^inftyc_i^ps^i
(1)

（Feller 1968，第 300 頁）。那麼

R_p(r,n)=sum_(i=r)^nc_i^p.
(2)

下表給出了數字三角形 2^nR_(1/2)(r,n)，對於 n=1、2、... 和 r=1、2、...、n (OEIS A050227)。

SloaneA000225A008466A050231A050233
n\r12345678
110000000
231000000
373100000
4158310000
53119831000
663432083100
71279447208310
82552011074820831

特殊情況 r=2 給出了序列

R_(1/2)(2,n)=2^(n+1)-F_(n+3),
(3)

其中 F_n 是一個 斐波那契數。類似地，在 n 次拋擲中不出現 k 次連續反面的機率由 F_(n+2)^((k))/2^n 給出，其中 F_l^((k)) 是一個 斐波那契 k 步數。

Feller（1968，第 278-279 頁）證明了對於 w(n)=1-R_(1/2)(3,n)，

lim_(n->infty)w(n)alpha^(n+1)=beta,
(4)

其中

alpha=(x^3+2x^2+4x-8)_1
(5)
=1.087378025...
(6)

（OEIS A086253）是上述多項式的正根，並且

beta=(2-alpha)/(4-3alpha)
(7)
=(11x^3-22x^2+12x-2)_1
(8)
=1.236839844...
(9)

（OEIS A086254）是上述多項式的正根。對於 k>1 次正面連串，相應的常數是 alpha_k，即

1-x+(1/2x)^(k+1)=0,
(10)

和

beta_k=(2-alpha)/(k+1-kalpha_k).
(11)

對於 P(H)=p 和 P(T)=q=1-p 的不公平硬幣，這些常數被修改為 alpha_k^'，即

1-x+qp^kx^(k+1)=0,
(12)

和

beta_k^'=(1-palpha_k^')/((k+1-kalpha_k^')p)
(13)

（Feller 1968，第 322-325 頁）。

給定 n 次 伯努利試驗，成功的機率（正面）為 p，則反面的期望數為 n(1-p)，因此反面連串 >=1 的期望數為 approx n(1-p)p。繼續，

N_R=n(1-p)p^R
(14)

是連串 >=R 的期望數。因此，最長的期望連串由下式給出

R=log_(1/p)[n(1-p)]
(15)

（Gordon et al. 1986，Schilling 1990）。給定 m 個 0 和 n 個 1，具有 u 個連串的可能排列數為

f_u={2(m-1; k-1)(n-1; k-1) u=2k; (m-1; k)(n-1; k-1)+(m-1; k-1)(n-1; k) u=2k+1
(16)

對於 k 為 整數，其中 (n; k) 是一個 二項式係數（Johnson 和 Kotz 1968，第 268 頁）。那麼

P(u<=u^')=sum_(u=2)^(u^')(f_u)/((m+n; m)).
(17)

現在考慮從包含 m 個一種型別的不可區分物體和 k 個另一種型別的不可區分物體的 N 個物體的集合中不放回地抽取 N 個物體。設 N(r;m,k) 表示這些物體的排列數，其中沒有 r 連串出現。例如，型別 A 的兩個物體和型別 B 的兩個物體有 6 種排列。在這些排列中，AABB、ABBA、BAAB 和 BBAA 包含長度為 2 的連串，因此 N(2;2,2)=2。一般來說，r 連串確實發生的機率由下式給出

P(r;m,k)=1-(N(r;m,k))/((m+k; k)),
(18)

其中 (a; b) 是一個 二項式係數。Bloom（1996）給出了 N(r;m,k) 的以下遞推序列，

N(r;m,k)=e(r;m,k)+sum_(i=0)^(r-1)N(r;m-1,k-i)-sum_(i=1)^(r-1)N(r;m-r,k-i),
(19)

其中當 m 或 k 為負數時，N(r,m,k)=0，並且

e(r;m,k)={1 if m=0 and 0<=k<r; -1 if m=r and 0<=k<r; 0 otherwise.
(20)

另一個只有固定項數的遞推式由下式給出

N(r;m,k)=N(r;m-1,k)+N(r;m,k-1)-N(r;m-r,k-1)-N(r;m-1,k-r)+N(r;m-r,k-r)+e_r^*(m,k),
(21)

其中

e_r^*(m,k)={1 if (m,k)=(0,0) or (r,r); -1 if (m,k)=(0,r) or (r,0); 0 otherwise
(22)

（Goulden 和 Jackson 1983，Bloom 1996）。

這些公式可用於計算一副 52 張牌的牌組中獲得 n 張相同顏色牌的連串的機率。對於 N=1、2、...，這產生了序列 1, 247959266474051/247959266474052, ... (OEIS A086439 和 A086440)。透過乘以 (52; 26) 進行歸一化得到 495918532948104, 495918532948102, 495891608417946, 483007233529142, ... (OEIS A086438)。結果

P(6;26,26)=(2740784175881)/(5903792058906)=0.46424...
(23)

反駁了 Gardner (1982) 的斷言，即在普通牌組中“幾乎總是會有六到七張相同顏色的牌聚集在一起”。

Bloom (1996) 給出了 r 連串（即，將序列分成相同值的最大聚集，並計算長度 >=r 的此類聚集的數量）在 m 個 0 和 n 個 1 的序列中的期望數，為

E(n,m,r)=((m+1)(n)_r+(n+1)(m)_r)/((m+n)_r),
(24)

其中 (a)_n 是 遞降階乘。對於 m>10，u 近似服從 正態分佈，其 均值 和 方差 為

mu_u=1+(2mn)/(m+n)
(25)
sigma_u^2=(2mn(2mn-m-n))/((m+n)^2(m+n-1)).
(26)

另請參見

牌, 拋硬幣, 尤拉數, 超幾何分佈, 排列, 排列連串, s-連串

使用 探索

參考文獻

Bloom, D. M. "Probabilities of Clumps in a Binary Sequence (and How to Evaluate Them Without Knowing a Lot)." Math. Mag. 69, 366-372, 1996.Feller, W. An Introduction to Probability Theory and Its Application, Vol. 1, 3rd ed. New York: Wiley, 1968.Finch, S. R. "Feller's Coin Tossing Constants." §5.11 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 339-342, 2003.Gardner, M. Aha! Gotcha: Paradoxes to Puzzle and Delight. New York: W. H. Freeman, p. 124, 1982.Godbole, A. P. "On Hypergeometric and Related Distributions of Order k." Commun. Stat.: Th. and Meth. 19, 1291-1301, 1990.Godbole, A. P. and Papastavridis, G. (Eds.). Runs and Patterns in Probability: Selected Papers. New York: Kluwer, 1994.Gordon, L.; Schilling, M. F.; and Waterman, M. S. "An Extreme Value Theory for Long Head Runs." Prob. Th. and Related Fields 72, 279-287, 1986.Goulden, I. P. and Jackson, D. M. Combinatorial Enumeration. New York: Wiley, 1983.Johnson, N. and Kotz, S. Discrete Distributions. New York: Wiley, 1968.Mood, A. M. "The Distribution Theory of Runs." Ann. Math. Statistics 11, 367-392, 1940.Philippou, A. N. and Makri, F. S. "Successes, Runs, and Longest Runs." Stat. Prob. Let. 4, 211-215, 1986.Schilling, M. F. "The Longest Run of Heads." Coll. Math. J. 21, 196-207, 1990.Schuster, E. F. In Runs and Patterns in Probability: Selected Papers (Ed. A. P. Godbole and S. Papastavridis). Boston, MA: Kluwer, pp. 91-111, 1994.Sloane, N. J. A. Sequences A000225/M2655, A008466, A050227, A050231, A050232, A050233, A086253, A086254, A086438, A086439, and A086440 in "The On-Line Encyclopedia of Integer Sequences."

在 上被引用

連串

請引用為

Weisstein, Eric W. “連串”。來自 Web 資源。 https://mathworld.tw/Run.html

學科分類