預期擲骰子將每個數字擲出奇數次
我們家最近學會瞭如何玩一個簡單的遊戲，叫做“親愛的”。每個玩家有六張紙牌（Ace,2,3,4,5,6）面朝上，輪流擲骰子。無論骰子擲出多少數字，相應的牌都會翻開。獲勝者是先將所有牌面朝下翻牌的玩家，但如果您擲出已翻牌面朝下的牌號，則該牌將再次翻牌面朝上（您會說“哦，親愛的！”） .
我想計算出遊戲的預期長度（擲骰子）。我首先感興趣的是在單人遊戲的情況下解決這個問題，然後對多個玩家的答案如何變化的問題也很感興趣。這相當於計算出玩家必須擲骰子的預期次數，以使骰子上的每個數字都擲出奇數次。（我假設一個公平的六面骰子，但同樣會對更通用的解決方案感興趣）。
從任何位置盡快計算出獲勝機率很簡單，但我不確定如何計算玩家獲勝之前的預期擲骰數……
您可以將您的問題視為馬爾可夫鏈，即狀態之間具有一定轉換概率的一組狀態。您從一種狀態開始（所有卡面朝上）並最終進入吸收狀態（所有卡面朝下）。您的問題是關於達到該吸收狀態之前的預期步數，無論是對於單個鏈，還是對於跨鏈的預期最小步數 $ n $ 獨立的馬爾可夫鏈同時運行。
實際上有兩種稍微不同的方式來看待這個問題。第一個，正如 whuber 評論的那樣，將六張卡片視為六個不同的位 $ {0,1} $ 並將狀態視為一個六向量 $ {0,1}^6 $ ，即六維離散超立方體。我們從頂點開始 $ (0,0,0,0,0,0) $ , 吸收狀態為 $ (1,1,1,1,1,1) $ . 一個步驟可以將我們帶到一個相鄰的頂點，其中相對於原始狀態恰好翻轉了一位。也就是說，轉換將我們從一個頂點帶到任何相鄰的頂點，漢明距離正好為 1，並且每個這樣的鄰居都有相同的概率成為下一個狀態。
有一些關於具有漢明距離的離散立方體上的隨機遊走和馬爾可夫鏈的文獻，但我無法在短時間內找到任何東西。我們在Random walk on the edges of a cube有一個非常好的線程，這可能很有趣。
看待這一點的第二種方法是利用所有卡都可以互換的事實（假設一個公平的骰子）。然後我們可以只使用七種不同的狀態，對應於面朝下的卡片數量。我們從狀態開始 $ i=0 $ , 吸收狀態為 $ i=6 $ . 轉移概率取決於我們所處的狀態：
- 從 $ i=0 $ （所有牌面朝上），我們肯定會翻轉一張牌並最終得到一張牌面朝下：我們有轉移概率 $ p_{01}=1 $ （和 $ p_{0j}=0 $ 為了 $ j\neq 1 $ ）。
- 從 $ i=1 $ ，我們可以達到 $ j=0 $ 有概率 $ p_{10}=\frac{1}{6} $ 和 $ j=2 $ 有概率 $ p_{12}=\frac{5}{6} $ .
總的來說，我們得到以下轉換矩陣：
$$ T=\begin{pmatrix} 0 & \frac{6}{6} & 0 & 0 & 0 & 0 & 0 \ \frac{1}{6} & 0 & \frac{5}{6} & 0 & 0 & 0 & 0 \ 0 & \frac{2}{6} & 0 & \frac{4}{6} & 0 & 0 & 0 \ 0 & 0 & \frac{3}{6} & 0 & \frac{3}{6} & 0 & 0 \ 0 & 0 & 0 & \frac{4}{6} & 0 & \frac{2}{6} & 0 \ 0 & 0 & 0 & 0 & \frac{5}{6} & 0 & \frac{1}{6} \ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$
我們從狀態中的確定性開始 $ i=0 $ . 我們可以用向量編碼每個狀態在某個點的概率 $ v\in[0,1]^7 $ ，我們的起始狀態對應於 $ v_0=(1,0,0,0,0,0,0) $ .
這是關於馬爾可夫鏈的一個基本事實（通過歸納很容易看到和證明）：之後狀態的概率 $ k $ 轉換由下式給出 $ v_k=(T')^kv_0 $ . （那是 $ T $ 轉置。您還可以使用行向量 $ v $ ，那麼你不需要轉置，但是“ $ v_0T^k $ “需要一點時間來適應。）
因此，我們最終處於吸收狀態的概率 $ i=6 $ 後 $ k $ steps 正是該向量中的最後一個條目，或者 $ v_k[6]=((T')^kv_0)[6] $ . 當然，我們可能已經處於吸收狀態之後 $ k-1 $ 腳步。所以我們的馬爾可夫鏈在之後第一次進入吸收狀態的概率 $ k $ 步驟是
$$ p_k := ((T')^kv_0)[6]-((T')^{k-1}v_0)[6]. $$
我們可以數值計算 $ p_k $ 對於足夠多的 $ k\leq K $ 這樣 $ \sum_{k=0}^Kp_k\approx 1 $ ，甚至可能有一個封閉形式的解決方案。然後，給定 $ p_k $ ，我們可以計算期望為
$$ \sum_{k=0}^\infty kp_k \approx \sum_{k=0}^K kp_k. $$
接下來，假設我們有 $ n $ 玩家，我們想知道遊戲將在多少步後結束，即第一個玩家將所有牌面朝下的時間。我們可以很容易地計算出概率 $ q_k^n $ 至少一名玩家將所有牌面朝下 $ k $ 或更少的步驟，注意到
$$ \begin{align*} q_k^n &= P(\text{at least one player has all cards face down after $k$ or fewer steps}) \ &= 1-P(\text{all $n$ players need at least $k+1$ steps}) \ &= 1-P(\text{ONE player needs at least $k+1$ steps})^n \ &= 1-\bigg(\sum_{j=k+1}^\infty p_j\bigg)^n \ &= 1-\bigg(1-\sum_{j=0}^k p_j\bigg)^n. \end{align*} $$
由此我們可以推導出概率 $ p^n_k $ 那場比賽 $ n $ 玩家在完全結束之後 $ k $ 腳步：
$$ p^n_k = q_k^n-q_{k-1}^n = \bigg(1-\sum_{j=0}^{k-1} p_j\bigg)^n-\bigg(1-\sum_{j=0}^k p_j\bigg)^n. $$
反過來，我們可以再次計算出遊戲的預期長度 $ n $ 玩家：
$$ \sum_{k=0}^\infty kp^n_k \approx \sum_{k=0}^K kp^n_k. $$
正如我上面寫的，可能有一個封閉形式的解決方案 $ p_k $ ，但現在，我們可以使用 R 對它們進行數值評估。我正在使用 $ K=10,000 $ ， 以便 $ \sum_{k=0}^K p_k=1 $ 達到機器精度。
max_steps <- 10000 state_probabilities <- matrix(NA,nrow=max_steps+1,ncol=7,dimnames=list(0:max_steps,6:0)) state_probabilities[1,] <- c(1,0,0,0,0,0,0) transition_matrix <- rbind( c(0,6,0,0,0,0,0), c(1,0,5,0,0,0,0), c(0,2,0,4,0,0,0), c(0,0,3,0,3,0,0), c(0,0,0,4,0,2,0), c(0,0,0,0,5,0,1), c(0,0,0,0,0,0,6))/6 for ( kk in 1:max_steps ) { state_probabilities[kk+1,] <- t(transition_matrix)%*%state_probabilities[kk,] } probs <- diff(state_probabilities[,7]) sum(probs) # yields 1 sum(probs*seq_along(probs)) # yields 83.2 plot(probs[1:400],type="h",xlab="Number of steps",ylab="Probability",las=1)
接下來，這就是我們獲得概率的方式 $ p^4_k $ 為了 $ n=4 $ 玩家：
n_players <- 4 probs_minimum <- sapply(1:max_steps, function(kk)(1-sum(probs[1:(kk-1)]))^n_players-(1-sum(probs[1:kk]))^n_players) head(probs_minimum) plot(probs_minimum[1:400],type="h",xlab="Number of steps",ylab="Probability", las=1,main=paste(n_players,"players"))
當然，四個人完成的速度比一個人快。為了 $ n=4 $ ，我們得到一個期望值
sum(probs_minimum*seq_along(probs_minimum)) [1] 25.44876最後，我喜歡使用模擬來確認這樣的計算。
n_sims <- 1e5 steps_minimum <- rep(NA,n_sims) pb <- winProgressBar(max=n_sims) for ( ii in 1:n_sims ) { setWinProgressBar(pb,ii,paste(ii,"of",n_sims)) set.seed(ii) # for reproducibility states <- matrix(FALSE,nrow=6,ncol=n_players) n_steps <- 0 while ( TRUE ) { n_steps <- n_steps+1 for ( jj in 1:n_players ) { roll <- sample(1:6,1) states[roll,jj] <- !states[roll,jj] } if ( any ( colSums(states) == 6 ) ) { steps_minimum[ii] <- n_steps break } } } close(pb)我們需要的步驟數的分佈 $ 10^5 $ 模擬遊戲匹配計算 $ p^4_k $ 相當好：
result <- structure(rep(0,length(probs_minimum)),.Names=seq_along(probs_minimum)) result[names(table(steps_minimum))] <- as.vector(table(steps_minimum))/n_sims cbind(result,probs_minimum)[1:30,] result probs_minimum 1 0.00000 0.00000000 2 0.00000 0.00000000 3 0.00000 0.00000000 4 0.00000 0.00000000 5 0.00000 0.00000000 6 0.06063 0.06031414 7 0.00000 0.00000000 8 0.08072 0.07919228 9 0.00000 0.00000000 10 0.08037 0.08026479 11 0.00000 0.00000000 12 0.07382 0.07543464 13 0.00000 0.00000000 14 0.06826 0.06905406 15 0.00000 0.00000000 16 0.06409 0.06260212 17 0.00000 0.00000000 18 0.05668 0.05654555 19 0.00000 0.00000000 20 0.05180 0.05100393 21 0.00000 0.00000000 22 0.04570 0.04598101 23 0.00000 0.00000000 24 0.04078 0.04144437 25 0.00000 0.00000000 26 0.03749 0.03735245 27 0.00000 0.00000000 28 0.03241 0.03366354 29 0.00000 0.00000000 30 0.03026 0.03033861最後，模擬遊戲所需步數的平均值也與計算出的期望值非常吻合：
mean(steps_minimum) [1] 25.43862
