再出一道"诡异逆天反直觉"的概率蹄

石头布

其实是仁在他的日志里出的题。把具体概率算出来一看，挺有意思的。题目很简单：


假设一个无限长的随机的“0,1”序列，在它的所有长度为3的片段里面，出现010或011的概率哪个大？概率（各？）是多少？

为防歧义，说明一下，对一个长度为N的随机序列而言，采样空间是N-2个长度为3的片段。不是N／3个。

但这个问题有两个情况：

(1), 重叠出现的”目标片段“被记为两次，比如： 01010可算作两个010

(2), 重叠出现的”目标片段“被记为一次，即： 01010 只能算作一个010


第一个用两行就把两种情况下的概率和原因说清楚的，我给22爱媛红包。 （仁就不给了 :) ）

石头布

寒地散人 发表于 2014-2-27 00:37
不可重叠的011的概率0.25      010的概率0.125
可重叠的概率相同都为0.125

第二行正确。
0.25 太高了， 实际上不可能高于1/8。

石头布

三力思 发表于 2014-2-27 00:45
计算机专业术语，小白退散

想象一下，读单条磁带机的识别逻辑。 读到第一个0，第一位正确的逻辑旗升起。  ...

就是说，磁带机认为“01010”是一个“010”， 而不是两个。make sense， 很多实际应用里面，不可重叠的设定较合理。
那磁带机读出的“010”和“011”的频率是不是有区别呢？

石头布

穿着裤衩裸奔 发表于 2014-2-26 23:55
我给你200爱元，你公布答案吧？

其实只有一种情况是反直觉的，另一种情况很平常。真说出来你肯定后悔这200块

石头布

独角兽 发表于 2014-2-27 03:07
这个问题我始终想不明白的是，如果不可以重叠，那么概率1是什么？

很好的问题。可以重叠和不可以重叠，限制的只是对出现的010和011的记数。两种情况下，
概率1都是“所有的长度为3的片段”，它们当然是重叠的，数量是N-2。

所谓的”可以重叠“和”不可以重叠“ 这两个情况我这样定义就更清楚些：

(1), 重叠出现的”目标片段“记为两次，比如： 01010可算作两个010。 （可以重叠）

(2), 重叠出现的”目标片段“记为一次，即： 01010 只能算作一个010。（不可以重叠）

----------------------------------------------
相应改进了题目的陈述。

石头布

独角兽 发表于 2014-2-27 03:39
所以第一问的概率1/8我没问题；可是第二问，不可以重叠的情况下的概率我想不清楚。或者不应该叫概率吧？ ...

还是可以称为概率。如果把因重叠而”飘没“的那些010的概率加入，总概率依然为1.
不可重叠的情况下000和111的记数是最少的

石头布

Highway 发表于 2014-2-27 04:41
不知道你说的“足够长”是多长，我取1个亿应该够长了吧？

Case 1: 重叠出现的”目标片段“被记为两次

给力! 我比较没耐性，没算这么长。
跟理论预测值是一致的。010 是十分之一。000和111还要更小些。

石头布

Highway 发表于 2014-2-27 05:30
Case 1: 重叠出现的”目标片段“被记为两次
000 sequence appears 12504409 times, rate: 12.501%  (1/8 ...

结果很给力！

实际上，允许重叠的话，八种片段的概率都是1/8。
不允许重叠的话，
000 和111 是1/14，
010 和101 是1/10，
其他的都是1/8， 当然它们总和不是1，缺口就是因重叠而不被记数的片段的概率。
对000和111来说，这个”飘没“概率是3/56
对010和101来说，是1/40

但是，怎么算出来的呢？

石头布

独角兽 发表于 2014-2-27 05:46
膜拜计算机，顺便告诉一下000是多少次？

N/14 次嘛。

其实仁出了这个题，我最初的想法是无头绪的，在他日志里我猜到011的概率大些，但无法定量，原因也似懂非懂。所以好奇就先用计算机模拟了，受到结果的启发和纠偏才找到正确答案的。

我的导师有一句话：Let the computer do the dirty work!  :)
所以你用纯脑不借助电脑就吃亏了。