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

石头布

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


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

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

但这个问题有两个情况：

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

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


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

njyd

不懂。不懂。不懂。
（老爱要求十个字以上）

nxp

文科生飘过～～～

穿着裤衩裸奔

我给你200爱元，你公布答案吧？

寒地散人

不可重叠的011的概率0.25      010的概率0.125
可重叠的概率相同都为0.125

三力思

计算机专业术语，小白退散

想象一下，读单条磁带机的识别逻辑。 读到第一个0，第一位正确的逻辑旗升起。 接下来是1的话，第二位正确的逻辑旗升起。 处理完第三位逻辑旗后，010和011的区别就出来了。 接下来第四位是什么， 识别010的第一位正确的逻辑旗可以不需要打下，读取数据直接跳到识别到第二位逻辑处理上。识别完011的，第一位正确的逻辑旗就要归零了。这个识别完后是不是逻辑旗归零，确定被识别的次数。 一般来说,5bit的01010不会等同6bit的010010.

石头布

寒地散人 发表于 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 02:31
就是说，磁带机认为“01010”是一个“010”， 而不是两个。make sense， 很多实际应用里面，不可重叠的设 ...

磁带机可以认为“01010”是两个“010”，看程序员的逻辑处理。 你认为不是，识别逻辑认出010后，下一个字符默认从头开始。 你认为是，设定下一个字符自动跳到第二位识别上。

独角兽

这个问题我始终想不明白的是，如果不可以重叠，那么概率1是什么？

石头布

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

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

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

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

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

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

独角兽

石头布 发表于 2014-2-27 03:26
很好的问题。可以重叠和不可以重叠，限制的只是对出现的010和011的记数。两种情况下，
概率1都是“所有的 ...

所以第一问的概率1/8我没问题；可是第二问，不可以重叠的情况下的概率我想不清楚。或者不应该叫概率吧？应该问计数的比值？假如不可重叠的情况下000的计数为1，那么其他7种各是多少呢？

石头布

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

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

Highway

不知道你说的“足够长”是多长，我取1个亿应该够长了吧？

Case 1: 重叠出现的”目标片段“被记为两次
010 sequence appears 12501116 times, rate: 12.501%  (1/8)
011 sequence appears 12500963 times, rate: 12.501%  (1/8)

Case 2:不允许重叠出现，也就是找到010或011，跳到下面去
010 sequence appears 10000444 times, rate: 10.000% (1/10)
011 sequence appears 12500963 times, rate: 12.501% (1/8)

石头布

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

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

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

Highway

石头布 发表于 2014-2-27 05:03
给力! 我比较没耐性，没算这么长。
跟理论预测值是一致的。010 是十分之一。000和111还要更小些。 ...

Case 1: 重叠出现的”目标片段“被记为两次
000 sequence appears 12504409 times, rate: 12.501%  (1/8)
111 sequence appears 12501683 times, rate: 12.501%  (1/8)

Case 2:不允许重叠出现，也就是找到000或111，跳到下面去
000 sequence appears 7143136 times, rate: 7.143136%
111 sequence appears 7145032 times, rate: 7.145032%

Anything else you want to know?

石头布

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

但是，怎么算出来的呢？

独角兽

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

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

膜拜计算机，顺便告诉一下000是多少次？