6 天 后
路漫漫其修远兮,吾将上下而求索……

梅森公式的梅森和梅森素数的梅森是同一个人吗?
    [未知用户] 路漫漫……看了这篇文章之后,深有同感ing
    24 天 后
    大致看来一下论文,很不错!大学时我也研究过这个问题,最开始时是用最土但是最有效的模拟来得到数值解。不过后来学了随机过程发现这个问题从殃的角度来求解会非常简单,至少不需要那么多繁杂的推导。这些理论的东西我早忘得差不多了,不过好在我也喜欢把算法转换成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,x4x_1,x_2,x_3,x_4,那么就可以列出方程
    x1=0.5+0.5(x2+1)x_1=0.5+0.5(x_2+1)
    x2=0.5(x3+1)+0.5(x1+1)x_2=0.5(x_3+1)+0.5(x_1+1)
    x3=0.5(x3+1)+0.5(x1+1)x_3=0.5(x_3+1)+0.5(x_1+1)
    x4=0.5(x2+1)+0.5(x4+1)x_4=0.5(x_2+1)+0.5(x_4+1)
    第一个式子意思是,HT之后一步如果扔的是T,那么就终止,1步到达HTT,如果扔的是H,那么回到TH的状态,也就是x2x_2。其他三个式子以此类推,解之x1=4,x2=6,x3=6,x4=8x_1=4, x_2=6, x_3=6, x_4=8,于是所求期望步数=0.25(x1+x2+x3+x4)+2=80.25(x_1+x_2+x_3+x_4)+2=8

      [未知用户] 看到你这解法,我在屋里忍不住大拍桌子,我K,居然有这么简练的解法!!没话说了,没话说了……
      [未知用户] 非常感谢!之前一直隐约觉得跟马氏链有关,可是就是不知道怎么列式求解,现在终于明白了!
      [未知用户] 没想到马氏链可以这么巧妙的用!佩服佩服!看来学东西要越学越活!
      1 年 后
      [未知用户] 我想在我的博客中收集这个解法,可以么?博客没有对外公开。
      [未知用户] 呵呵,可以的。以后多交流。
      22 天 后

      talentyxc 第三个式子笔误了,应该是x3=0.5(x3+1)+0.5(x1+1)x_3=0.5(x_3+1)+0.5(x_1+1),最终的结果是对的,没有任何问题。

      12 天 后
      9 年 后

      楼上的解法很赞!我看完后,把公式捋了一下