杜传龙
大致看来一下论文，很不错！大学时我也研究过这个问题，最开始时是用最土但是最有效的模拟来得到数值解。不过后来学了随机过程发现这个问题从殃的角度来求解会非常简单，至少不需要那么多繁杂的推导。这些理论的东西我早忘得差不多了，不过好在我也喜欢把算法转换成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
