在一系列抛硬币中击中正面和反面图案所需的时间

机器算法验证 r 可能性 随机过程 字符串计数
2022-02-04 03:02:04

受 Peter Donnelly 在TED上的演讲的启发，他在演讲中讨论了某种模式在一系列抛硬币中出现需要多长时间，我在 R 中创建了以下脚本。给定两个模式“hth”和“htt”，它计算在您达到其中一种模式之前平均需要多长时间（即抛硬币次数）。

coin <- c('h','t')

hit <- function(seq) {
    miss <- TRUE
    fail <- 3
    trp  <- sample(coin,3,replace=T)
    while (miss) {
        if (all(seq == trp)) {
            miss <- FALSE
        }
        else {
            trp <- c(trp[2],trp[3],sample(coin,1,T))
            fail <- fail + 1
        }
    }
    return(fail)
}

n <- 5000
trials <- data.frame("hth"=rep(NA,n),"htt"=rep(NA,n))

hth <- c('h','t','h')
htt <- c('h','t','t')

set.seed(4321)
for (i in 1:n) {
    trials[i,] <- c(hit(hth),hit(htt))    
}
summary(trials)

汇总统计如下，

      hth             htt        
 Min.   : 3.00   Min.   : 3.000  
 1st Qu.: 4.00   1st Qu.: 5.000  
 Median : 8.00   Median : 7.000  
 Mean   :10.08   Mean   : 8.014  
 3rd Qu.:13.00   3rd Qu.:10.000  
 Max.   :70.00   Max.   :42.000

演讲中解释说，两种模式的平均抛硬币次数会有所不同；从我的模拟中可以看出。尽管看了几次谈话，我仍然不太明白为什么会这样。我知道'hth'会重叠，直觉上我认为你会比'htt'更早地击中'hth'，但事实并非如此。如果有人可以向我解释这一点，我将不胜感激。

4个回答

想想当你第一次得到一个 H 后是一个 T 时会发生什么。

案例 1：您正在寻找 HTH，并且您是第一次看到 HT。如果下一次投掷是 H，那么你就完成了。如果是 T，你又回到第一方：因为最后两次投掷是 TT，你现在需要完整的 HTH。

案例 2：您正在寻找 HTT，并且您是第一次看到 HT。如果下一次投掷是 T，那么你就完成了。如果是H，这显然是一个挫折；但是，这是一个小问题，因为您现在拥有 H 并且只需要 -TT。如果下一次投掷是 H，这不会使您的情况变得更糟，而 T 会使情况变得更好，依此类推。

换句话说，在情况 2 中，您看到的第一个 H 会带您走 1/3 的路，从那时起，您永远不必从头开始。在案例 1 中情况并非如此，其中 TT 会抹去您已取得的所有进度。

我喜欢画画。

在此处输入图像描述

这些图是有限状态自动机(FSA)。它们是小型儿童游戏（例如Chutes 和 Ladders），通过将令牌从一个节点移动到另一个节点以响应硬币翻转，分别“识别”或“接受”HTT 和 HTH 序列。令牌从顶部节点开始，由箭头（第i行）指向。每次抛硬币后，令牌沿着标有该硬币结果（H 或 T）的边移动到另一个节点（我将分别称为“H 节点”和“T 节点”）。当令牌落在终端节点上时（没有外向箭头，以绿色表示），游戏结束，FSA 接受了序列。

将每个 FSA 视为沿线性轨道垂直前进。投掷正面和反面的“正确”序列会导致令牌向其目的地前进。抛出“错误”值会导致令牌备份（或至少静止不动）。 令牌备份到与最近的投掷对应的最高级状态。 例如，第 ii 行的 HTT FSA 在看到一个正面时停留在第ii行，因为该正面可能是最终 HTH 的初始序列。它不会一直回到开头，因为这实际上会完全忽略最后一个头。

经过验证这两款游戏确实对应声称的HTT和HTH，并逐行比较它们，现在应该很明显HTH更难获胜。它们的图形结构仅在第iii行有所不同，其中 H 将 HTT 带回第ii行（并且 T 接受），但是在 HTH 中，T 将我们一直带回第i行（并且 H 接受）。 在第iii行玩 HTH 的惩罚比玩 HTT 的惩罚更严重。

这可以量化。我已经用接受所需的预期投掷次数 标记了这两个 FSA 的节点。 让我们将这些节点称为“值”。标签开始于

(1) 在接受节点处写入明显的 0 值。

设正面概率为 p(H)，反面概率为 1 - p(H) = p(T)。（对于一枚公平的硬币，两个概率都等于 1/2。）因为每次掷硬币都会使投掷次数增加一，

(2) 一个节点的值等于 1 加上 p(H) 乘以 H 节点的值加上 p(T) 乘以 T 节点的值。

这些规则决定了这些值。这是验证标记值（假设是公平硬币）是否正确的快速且内容丰富的练习。例如，考虑第ii行的 HTH 值。规则说 8 必须比 8（第i行 H 节点的值）和 6（第iii行 T 节点的值）的平均值大1：果然，8 = 1 + (1/2) *8 + (1/2)*6。您可以很容易地检查图中剩余的五个值。

假设您掷硬币次并数一数您看到“HTH”图案（包括重叠）的次数。预期的数字是。但它也是。由于可以自身重叠而 "HTT" 不能重叠，因此您会期望更多地与 "HTH" 聚集在一起，这会增加首次出现的预期时间。 8n+2nnHTHHTH

另一种看待它的方式是，在达到“HT”之后，“T”会将“HTH”发送回起点，而“H”将开始前进到可能的“HTT”。

通过查看重叠，您可以使用 Conway 算法 [我认为] 计算出两个预期时间：如果模式的前次投掷与最后一次匹配，则添加。因此，对于“HTH”，您会得到作为期望值，对于“HTT”，您会得到，从而确认您的模拟。kk2k2+0+8=100+0+8=8

奇怪并不止于此。如果您在两种模式之间进行比赛，则它们首先出现的概率相同，并且直到其中一种出现的预期时间为（比预期时间多 1 获得“HT”，之后必须出现其中一种） . 5

情况变得更糟：在Penney 的游戏中，你选择一种模式进行比赛，然后我选择另一种。如果您选择“HTH”，那么我会选择“HHT”，并且有 2:1 的获胜几率；如果您选择“HTT”，那么我将再次选择“HHT”，仍然有 2:1 的赔率对我有利。但如果你选择“HHT”，那么我会选择“THH”，赔率是 3:1。第二个玩家总是可以偏向赔率，最好的选择是不可传递的。

一些很棒的答案。我想采取稍微不同的方法，并解决反直觉的问题。（我非常同意，顺便说一句）

这就是我的理解。想象一列随机顺序的掷硬币结果打印在纸带上，由字母“H”和“T”组成。

任意撕下该磁带的一部分，并制作相同的副本。

在给定的磁带上，如果磁带足够长，序列 HTH 和序列 HTT 将分别出现。

但有时HTH 实例会一起运行，即HTHTH。（甚至非常偶尔 HTHTHTH）

这种重叠不会发生在 HTT 实例上。

使用荧光笔挑出成功结果的“条纹”，一个磁带上的 HTH 和另一个磁带上的 HTT。由于重叠，一些 HTH 条纹会更短。因此，平均而言，它们之间的间隙将比其他磁带稍长。

这有点像等公共汽车，平均每五分钟就有一趟。如果允许公共汽车相互重叠，则平均间隔将略长于五分钟，因为有时会有两辆公共汽车一起经过。

如果您在任意时间到达，则平均而言，如果允许它们重叠，您将等待下一辆（对您来说，第一辆）公共汽车稍长一些。

其它你可能感兴趣的问题
上一篇测试矩阵列之间的线性相关性 下一篇盖尔·加斯拉姆是谁？