爱吱声

标题: 再出一道"诡异逆天反直觉"的概率蹄 [打印本页]
作者: 石头布    时间: 2014-2-26 21:17
标题: 再出一道"诡异逆天反直觉"的概率蹄
本帖最后由 石头布 于 2014-2-27 03:38 编辑

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


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

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

但这个问题有两个情况：

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

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


第一个用两行就把两种情况下的概率和原因说清楚的，我给22爱媛红包。 （仁就不给了 :) ）
作者: njyd    时间: 2014-2-26 22:03
不懂。不懂。不懂。
（老爱要求十个字以上）
作者: nxp    时间: 2014-2-26 22:45
文科生飘过～～～
作者: 穿着裤衩裸奔    时间: 2014-2-26 23:55
我给你200爱元，你公布答案吧？
作者: 寒地散人    时间: 2014-2-27 00:37
本帖最后由 寒地散人 于 2014-2-27 00:41 编辑

不可重叠的011的概率0.25      010的概率0.125
可重叠的概率相同都为0.125
作者: 三力思    时间: 2014-2-27 00:45
本帖最后由 三力思 于 2014-2-27 01:04 编辑

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

想象一下，读单条磁带机的识别逻辑。 读到第一个0，第一位正确的逻辑旗升起。 接下来是1的话，第二位正确的逻辑旗升起。 处理完第三位逻辑旗后，010和011的区别就出来了。 接下来第四位是什么， 识别010的第一位正确的逻辑旗可以不需要打下，读取数据直接跳到识别到第二位逻辑处理上。识别完011的，第一位正确的逻辑旗就要归零了。这个识别完后是不是逻辑旗归零，确定被识别的次数。 一般来说,5bit的01010不会等同6bit的010010.
作者: 石头布    时间: 2014-2-27 01:47
寒地散人 发表于 2014-2-27 00:37
不可重叠的011的概率0.25      010的概率0.125
可重叠的概率相同都为0.125

第二行正确。
0.25 太高了， 实际上不可能高于1/8。
作者: 桃李不言    时间: 2014-2-27 02:20
概率论还给老师的飘过……
作者: 石头布    时间: 2014-2-27 02:31
本帖最后由 石头布 于 2014-2-27 02:35 编辑
三力思 发表于 2014-2-27 00:45
计算机专业术语，小白退散

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


就是说，磁带机认为“01010”是一个“010”， 而不是两个。make sense， 很多实际应用里面，不可重叠的设定较合理。
那磁带机读出的“010”和“011”的频率是不是有区别呢？
作者: 石头布    时间: 2014-2-27 02:41
穿着裤衩裸奔 发表于 2014-2-26 23:55
我给你200爱元，你公布答案吧？


其实只有一种情况是反直觉的，另一种情况很平常。真说出来你肯定后悔这200块
作者: 三力思    时间: 2014-2-27 02:50
石头布 发表于 2014-2-27 02:31
就是说，磁带机认为“01010”是一个“010”， 而不是两个。make sense， 很多实际应用里面，不可重叠的设 ...

磁带机可以认为“01010”是两个“010”，看程序员的逻辑处理。 你认为不是，识别逻辑认出010后，下一个字符默认从头开始。 你认为是，设定下一个字符自动跳到第二位识别上。
作者: 独角兽    时间: 2014-2-27 03:07
这个问题我始终想不明白的是，如果不可以重叠，那么概率1是什么？
作者: 石头布    时间: 2014-2-27 03:26
本帖最后由 石头布 于 2014-2-27 03:39 编辑
独角兽 发表于 2014-2-27 03:07
这个问题我始终想不明白的是，如果不可以重叠，那么概率1是什么？


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

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

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

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

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

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

所以第一问的概率1/8我没问题；可是第二问，不可以重叠的情况下的概率我想不清楚。或者不应该叫概率吧？应该问计数的比值？假如不可重叠的情况下000的计数为1，那么其他7种各是多少呢？
作者: 石头布    时间: 2014-2-27 03:58
独角兽 发表于 2014-2-27 03:39
所以第一问的概率1/8我没问题；可是第二问，不可以重叠的情况下的概率我想不清楚。或者不应该叫概率吧？ ...

还是可以称为概率。如果把因重叠而”飘没“的那些010的概率加入，总概率依然为1.
不可重叠的情况下000和111的记数是最少的
作者: Highway    时间: 2014-2-27 04:41
本帖最后由 Highway 于 2014-2-27 04:49 编辑

不知道你说的“足够长”是多长，我取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)


作者: 石头布    时间: 2014-2-27 05:03
Highway 发表于 2014-2-27 04:41
不知道你说的“足够长”是多长，我取1个亿应该够长了吧？

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

给力! 我比较没耐性，没算这么长。
跟理论预测值是一致的。010 是十分之一。000和111还要更小些。
作者: Highway    时间: 2014-2-27 05:30
石头布 发表于 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?
作者: 石头布    时间: 2014-2-27 05:42
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
Highway 发表于 2014-2-27 04:41
不知道你说的“足够长”是多长，我取1个亿应该够长了吧？

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

膜拜计算机，顺便告诉一下000是多少次？
作者: Highway    时间: 2014-2-27 05:49
石头布 发表于 2014-2-27 05:42
结果很给力！

实际上，允许重叠的话，八种片段的概率都是1/8。

这两天讨论的所有的“概率题”我根本就没有动脑筋想，一抬手写两句程序就算出来了。动脑筋的事儿还是留给你们这些聪明的同学去鼓捣吧。
作者: 石头布    时间: 2014-2-27 06:25
本帖最后由 石头布 于 2014-2-27 06:38 编辑
独角兽 发表于 2014-2-27 05:46
膜拜计算机，顺便告诉一下000是多少次？


N/14 次嘛。

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

我的导师有一句话：Let the computer do the dirty work!  :)
所以你用纯脑不借助电脑就吃亏了。
作者: 仁    时间: 2014-2-27 06:42
独角兽 发表于 2014-2-27 03:39
所以第一问的概率1/8我没问题；可是第二问，不可以重叠的情况下的概率我想不清楚。或者不应该叫概率吧？ ...

第二种情况你可以这样考虑：扔一个 硬币，每次出现背和面的概率都是1/2。平均要扔几次才出现 背面面的情况？一旦 它出现了就重新开始扔。这个和不能共用是一样的。如果品均需要8次，那么在足够长的序列里，他出现的频率就是1/8。
作者: 仁    时间: 2014-2-27 06:56
Highway 发表于 2014-2-27 04:41
不知道你说的“足够长”是多长，我取1个亿应该够长了吧？

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

如果是可以重复的不需要算，只要是长度一样的，任何组合出像的频率都一样。
作者: leekai    时间: 2014-2-28 15:19
太搞脑子了，会提前衰老。不参与。
作者: 常挨揍    时间: 2014-2-28 20:18
石头布 发表于 2014-2-27 03:58
还是可以称为概率。如果把因重叠而”飘没“的那些010的概率加入，总概率依然为1.
不可重叠的情况下000和 ...

要加入非法样本的可能性才能把总概率凑成1！？



欢迎光临 爱吱声 (http://aswetalk.net/bbs/) Powered by Discuz! X3.2