用GERT方法求解两个抛硬币问题
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
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所需步数为,那么就可以列出方程
第一个式子意思是,HT之后一步如果扔的是T,那么就终止,1步到达HTT,如果扔的是H,那么回到TH的状态,也就是。其他三个式子以此类推,解之,于是所求期望步数=
[未知用户] 看到你这解法,我在屋里忍不住大拍桌子,我K,居然有这么简练的解法!!没话说了,没话说了……
[未知用户] 哈哈,妙哉!
[未知用户] 非常感谢!之前一直隐约觉得跟马氏链有关,可是就是不知道怎么列式求解,现在终于明白了!
[未知用户] 没想到马氏链可以这么巧妙的用!佩服佩服!看来学东西要越学越活!
1 年 后
[未知用户] 怎一个妙字了得……
[未知用户] 我想在我的博客中收集这个解法,可以么?博客没有对外公开。
[未知用户] 呵呵,可以的。以后多交流。
12 天 后
[未知用户] 恩,是写错了。。
9 年 后
楼上的解法很赞!我看完后,把公式捋了一下