用GERT方法求解两个抛硬币问题

问题:一枚均匀的硬币,一直抛直至出现HTT(H表示正面,T表示背面),期望要抛多少次?一直抛直至出现HTH(即正反正),期望要抛多少次?假定出现H面的概率为p,出现T面的概率为q,且p=q=1/2

本文使用GERT方法(又叫图解评审技术)来求解这两个问题,即先把定性描述的抛硬币问题转换为随机网络系统,再利用流线图和矩母函数中的一些理论来求解系统,并最终得到上述问题的答案。通过GERT方法不仅可以非常有效地解决类似的期望抛硬币次数问题,而且给定任何一个抛硬币次数,均可以直接计算出该次数下出现HTT或HTH等情形的概率。

文中第一部分详细介绍了GERT方法,可作为第二部分的参考内容;第二部分是利用GERT方法求解上述的两个抛硬币问题。由于文中图和公式较多,编辑比较麻烦,所以具体的文章见下面的链接。

文章下载地址:用GERT方法解决两个抛硬币问题

论坛帖子地址:http://cos.name/bbs/read.php?tid=16360

用GERT方法求解两个抛硬币问题》有17个想法

  1. 路漫漫其修远兮,吾将上下而求索……

    梅森公式的梅森和梅森素数的梅森是同一个人吗?

    1. 不是,前者是http://en.wikipedia.org/wiki/Samuel_Jefferson_Mason,后者是http://en.wikipedia.org/wiki/Marin_Mersenne,差了几个世纪

  2. 大致看来一下论文,很不错!大学时我也研究过这个问题,最开始时是用最土但是最有效的模拟来得到数值解。不过后来学了随机过程发现这个问题从殃的角度来求解会非常简单,至少不需要那么多繁杂的推导。这些理论的东西我早忘得差不多了,不过好在我也喜欢把算法转换成code,当年我用Mathematica写过一个函数,用来求解这个问题的准确(非近似)解。当然这个函数可以解决的问题远不止上面这个问题,它适用于任意一个有限的离散分布。我把code贴在下面,并附上几个例子以供有兴趣的朋友参考:

    PatternTheory[t1_List, t2_List] :=
    Module[{n1, n2, i, j, ProbSum = 0, ResultProb = {}, temp, expect},
    n1 = Length[t1];
    n2 = Length[t2];
    For[i = 1, i <= n1, i++,
    If[t1[[i, 2]] 1, Return[False]];
    For[i = 1, i < n1, i++,
    For[j = i + 1, j <= n1, j++,
    If[t1[[j, 1]] == t1[[i, 1]], Return[False]]]];
    For[i = 1, i <= n2, i++,
    For[j = 1, j n1, Return[False]]];
    ResultProb = Rationalize[ResultProb];
    expect = n2;
    For[i = 1, i <= n2, i++,
    temp = 1;
    For[j = i, j <= n2, j++,
    If[t2[[j]] == t2[[j – i + 1]], temp = temp/ResultProb[[j]],
    temp = 0; Break[]]];
    expect = expect + temp – 1];
    Return[expect]]

    (*其中参数t1是一个二维表,用来定义一个有限的离散分布,t2是一个一维表,用来定义花样*)

    fenbu1 = {{1, 1/2}, {0, 1/2}};

    (*定义两点分布*)
    huayang1 = {1, 0, 1, 0};
    huayang2 = {1, 1, 0, 0};
    huayang3 = {1, 1, 0, 0, 1, 1};
    fenbu2 = {{0, 1/2}, {1, 1/3}, {2, 1/6}};
    (*定义分布:P(X=0)=1/2,P(X=1)=1/3,P(X=2)=1/6,即书中用鞅计算花样的那个例子*)
    huayang = {0, 2, 0};
    huayang = {1, 0, 0, 2};

    PatternTheory[fenbu1, huayang1]
    20

    PatternTheory[fenbu1, huayang2]
    16

    PatternTheory[fenbu1, huayang3]
    70

    PatternTheory[fenbu2, huayang1]
    42

    PatternTheory[fenbu2, huayang2]
    36

  3. 这个问题也可以用马尔科夫链的思路来做,因为每一步扔下去是否到达HTT仅和前两步有关,所以已知前两步状态,后面的期望步数就确定了,那么假设前两步是HT,TH,HH,TT之后的到达HTT所需步数为x1,x2,x3,x4,那么就可以列出方程
    x1=0.5+0.5(x2+1)
    x2=0.5(x3+1)+0.5(x1+1)
    x3=0.5(x3+1)+0.5(x2+1)
    x4=0.5(x2+1)+0.5(x4+1)
    第一个式子意思是,HT之后一步如果扔的是T,那么就终止,1步到达HTT,如果扔的是H,那么回到TH的状态,也就是x2。其他三个式子以此类推,解之x1=4 x2=6 x3=6 x4=8,于是所求期望步数=0.25(x1+x2+x3+x4)+2=8

    1. 看到你这解法,我在屋里忍不住大拍桌子,我K,居然有这么简练的解法!!没话说了,没话说了……

      1. 我想在我的博客中收集这个解法,可以么?博客没有对外公开。

    2. 非常感谢!之前一直隐约觉得跟马氏链有关,可是就是不知道怎么列式求解,现在终于明白了!

发表评论

邮箱地址不会被公开。 必填项已用*标注