一個公平的骰子被擲出 1,000 次。連續滾動相同數字 5 次的概率是多少？
一個公平的骰子被擲出 1,000 次。連續滾動相同數字 5 次的概率是多少？對於可變的投擲次數和重複次數，您如何解決此類問題？
下面我們用四種方式計算概率：
Computation with Markov Chain 0.473981098314993 Computation with generating function 0.473981098314988 Estimation false method 0.536438013618686 Estimation correct method 0.473304632462677前兩種是精確的方法，只有一點點不同（可能是一些錯誤），第三種方法是一種天真的估計，沒有給出正確的數字，第四種方法更好，給出的結果非常接近精確方法。
計算上：
馬爾可夫鏈
您可以使用轉換矩陣對此進行計算建模
說列向量 $ X_{k,j} = \lbrace x_1,x_2,x_3,x_4,x_5 \rbrace_{j} $ 是有的概率 $ k $ 在同一行中的相同數字 $ j $ -擲骰子。然後（假設一個 6 面骰子）
$$ X_{k,j} = M \cdot X_{k,j-1} $$和
$$ M = \begin{bmatrix} \frac{5}{6} & \frac{5}{6} & \frac{5}{6} & \frac{5}{6} & 0 \ \frac{1}{6} & 0& 0 & 0 & 0 \ 0& \frac{1}{6} & 0& 0 & 0 \ 0 & 0& \frac{1}{6} & 0& 0 \ 0&0 & 0& \frac{1}{6} & 1 \ \end{bmatrix} $$
最後一個條目在哪裡 $ M_{5,5} = 1 $ 與連續 5 個相同的狀態相關，這是我們“停止”實驗的吸收狀態。
在第一次滾動之後，您肯定會處於狀態 1（肯定只有 1 個相同數字連續）。
$$ X_{k,1} = \lbrace 1,0,0,0,0 \rbrace $$
之後 $ j $ -th roll 這將乘以 $ M $ 一個 $ j-1 $ 次
$$ X_{k,j} = M^{j-1} \lbrace 1,0,0,0,0 \rbrace $$
R-代碼：
library(matrixcalc) ### allows us to use matrix.power M <- matrix(c(5/6, 5/6, 5/6, 5/6, 0, 1/6, 0 , 0 , 0 , 0, 0, 1/6, 0 , 0 , 0, 0, 0 , 1/6, 0 , 0, 0, 0 , 0 , 1/6, 1), 5, byrow = TRUE) start <- c(1,0,0,0,0) matrix.power(M,999) %*% start結果是$$ X_{k,1000} = \begin{bmatrix} 0.438631855\ 0.073152468\ 0.012199943\ 0.002034635\ \color{red}{0.473981098}\end{bmatrix} $$
最後一個條目 0.473981098 是在 1000 次滾動中連續滾動 5 次相同數字的概率。
生成函數
我們的問題是：
- 如何計算至少滾動任何數字的概率 $ k $ 連續幾次，出 $ n $ 嘗試？
這相當於問題
- 如何計算至少滾動數字 6的概率 $ k-1 $ 連續幾次，出 $ n-1 $ 嘗試？
您可以將其視為跟踪骰子是否滾動 $ m $ 與擲骰子的數字相同 $ m-1 $ （概率為 1/6）。這需要發生 $ k-1 $ 連續幾次（在我們的例子中是 4 次）。
在這個問答中，替代問題作為一個組合問題來解決：我們可以用多少種方式擲骰子 $ n $ 沒有出現數字“6”的次數 $ k $ 或連續多次。
這是通過找到我們可以將字符串“x”、“x6”、“x66”、“x666”（其中“x”是任意數字 1、2、3、4、5）組合成一串長度 $ n+1 $ ( $ n+1 $ 代替 $ n $ 因為在這種構造字符串的方式中，第一個字母總是 $ x $ 這裡）。通過這種方式，我們計算了製作長度字符串的所有可能性 $ n $ 但只有 1、2 或 3 次連續出現 6（而不是 4 次或更多次）。
這些組合可以通過使用等效多項式來找到。這與我們擴展冪時與係數相關的二項式係數非常相似 $ (x+y)^n $ ，但它也涉及到一個組合。
多項式是
$$ \begin{array}{rcl} P(x) &=& \sum_{k=0}^\infty (5x+5x^2+5x^3+5x^4)^k\ &=& \frac{1}{1-(5x+5x^2+5x^3+5x^4)} \ &=& \frac{1}{1-5\frac{x-x^5}{1-x}}\ &=& \frac{1-x}{1-6x+5x^5} \end{array} $$
的係數 $ x^n $ 與將數字 1,2,3,4,5,6 排列在長度字符串中的方式的數量有關 $ n-1 $ 連續沒有 4 個或更多的 6。這個係數可以通過遞歸關係找到。$$ P(x) (1-6x+5x^5) = 1-x $$這意味著係數遵循關係
$$ a_n - 6a_{n-1} + 5 a_{n-5} = 0 $$
第一個係數可以手動計算
$$ a_1,a_2,a_3,a_4,a_5,a_6,a_7 = 5,30,180,1080,6475,38825,232800 $$
有了這個，你可以計算 $ a_{1000} $ 和 $ 1-a_{1000}/6^{999} $ 將是在第 5 行中滾動相同數字 5 次的概率。
在下面的 R 代碼中，我們計算了這個（我們在遞歸中包含了除以 6，因為數字 $ a_{1000} $ 和 $ 6^{999} $ 太大而無法直接計算）。結果是 $ 0.473981098314988 $ ，與馬爾可夫鏈的計算相同。
x <- 6/5*c(5/6,30/6^2,180/6^3,1080/6^4,6475/6^5,38825/6^6,232800/6^7) for (i in 1:1000) { t <- tail(x,5) x <- c(x,(6/6*t[5]-5/6^5*t[1])) ### this adds a new number to the back of the vector x } 1-x[1000]分析/估計
方法一：錯
你可能會想，在任何一組 5 個相鄰骰子中，有 5 個相同數字的概率是 $ \frac{1}{6^4} = \frac{1}{1296} $ ，並且由於有 996 組 5 個相鄰骰子，因此在這些組中至少有一組 5 個相同骰子的概率為：
$$ 1-(1-\frac{1}{6^4})^{996} \approx 0.536 $$
但這是錯誤的。原因是996個集合是重疊的，不是獨立的。
方法二：正確
更好的方法是近似我們上面計算的馬爾可夫鏈。一段時間後你會發現，1、2、3、4個連續相同數量的州的佔領或多或少是穩定的，比例大約是 $ 1/6,1/6^2,1/6^3,1/6^4 $ (*)。因此，我們連續 4 次的時間分數是：
$$ \text{frequency 4 in a row} = \frac{1/6^4}{1/6+1/6^2+1/6^3+1/6^4} $$
如果我們連續有這 4 個，那麼我們有 1/6 的概率完成遊戲。所以完成遊戲的頻率是
$$ \text{finish-rate} = \frac{1}{6} \text{frequency 4 in a row} = \frac{1}{1554} $$
以及之後完成的概率 $ k $ 步驟大約是
$$ P_k \approx 1-(1-\frac{1}{1554})^{k-4} \underbrace{\approx 0.47330}_{\text{if $k=1000$}} $$
更接近精確的計算。
() 州內職業 $ k $ 在滾動期間 $ j $ 將與州內的職業有關 $ k-1 $ 在滾動期間 $ j-1 $ . 我們將有 $ x_{k,j} = \frac{1}{6} x_{k-1,j-1} \approx \frac{1}{6} x_{k-1,j} $ . 請注意，這要求您擁有 $ x_{k-1,j} \approx x_{k-1,j-1} $ ，當完成率很小時會發生這種情況。如果不是這種情況，那麼您可以應用一個因子來補償，但相對穩定比率的假設也是錯誤的。*
相關問題