首页 > 技术相关 > 能够连续扔出几个正面呢?

能够连续扔出几个正面呢?

2013年7月1日 发表评论 阅读评论

Throw coins

去年写过一篇博客平均投几个三分才会连续进 3 个?,现在我们再回过头来看一个类似的问题。假如我们连续扔硬币 100 次,那么大约最多会连续出现几个正面呢?

我们先来看看简单的情况,比方说就扔三次硬币,很简单就可以列出所有的情况( H 表示正面,T 表示反面):

HHH, HHT, HTH, HTT, THH, THT, TTH, TTT

把这个结果列成个表格,就是下面这样

最大连续正面数 概率
0 1/8
1 1/2
2 1/4
3 1/8

很容易可以算出来,最大连续正面次数的期望是 11/8。不过硬币一旦多起来,要是这样列下去可就够数一阵子的了,所以还是要找更好一点的方法。

比方说我们一共有 \(n\) 个硬币,很显然这么些硬币一共有 \(2^n\) 种扔法。如果用 \(A_n(x\)) 来表示最多连续正面不超过 \(x\) 个的扔法的次数,就可以很方便地知道这种扔法出现的概率就是 \(A_n(x) / 2^n\)。假如要求 \(A_n(3\)),也就是出现最多不超过三个连续正面的扔法,我们可以考虑一下最开始的时候的几种情况:

1. 先扔一个反面,然后最多不超过三个连续正面;
2. 先扔一个正面,一个反面,然后最多不超过三个连续正面;
3. 先扔两个正面,一个反面,然后最多不超过三个连续正面;
4. 先扔三个正面,一个反面,然后最多不超过三个连续正面

看出规律了吗?这个问题可以化成四种情况来讨论,于是对于所有 \(n>3\):
\[
A_n(3) = A_{n-1}(3)+A_{n-2}(3)+A_{n-3}(3)+A_{n-4}(3)
\]

这样就可以递推出所有的数值了。推而广之,我们有
\[
A_n(3) =
\begin{cases}
\sum\limits_{j=0}^x A_{n-j-1}(x), & n > x;\\
2^n, & n< x.
\end{cases}
\]

另外还可以注意到一点,就是如果我们要求不出现两个连续正面的概率,很简单 \(A_n(1) = A_{n-1}(1)+A_{n-2}(1)\) 就是斐波那契数列。

那么这个最大长度的期望是多少呢?直接计算这个东西是比较复杂的,有兴趣的同学可以参考相关的文章。[1] 但这里有一个相对比较直观的想法:

每出现一次反面,我们就认为开始连续地出现正面了(当然很可能只出现了 0 个)。这样的话,由于扔 \(n\) 次硬币后应当大约出现 \(n/2\) 个反面,也就是 \(n/2\) 次出现连续正面。出现反面,再出现一个正面的概率是 1/2,意味着有 \(n/4\) 次出现 1 个以上连续正面。同理,\(n/8\) 次出现 2 个以上连续正面,\(n/16\) 次出现 3 个以上连续正面…… 什么时候就是最长了呢?就是连续正面出现次数等于 1 的时候。因此,最长的连续正面个数的期望就近似为

\[
R_n \approx \log_2 n – 1
\]

如果连续扔 100 次硬币,最长的连续正面数应该在 5.6 左右。如果比较一下平均投几个三分才会连续进 3 个?的结果,还是很有意思的。

另外一个结论是这个概率的方差很小,最长连续正面数有相当大的概率会落在最靠近 \(\log_2 n -1\) 的整数 ±3 以内。这是一个很有用的性质,比如在通信和密码学中常常用到伪随机序列,那么这个伪随机序列到底像不像一个随机序列呢?随机性检测的标准有很多,比如任意子序列中 1 出现的频率应该接近 1/2 等。有一个常用标准就是看等长子序列中连续出现的 1 的长度(游程)分布是不是符合随机数的特征。

我们直觉上的“随机”常常并不是那么“随机”的。有好事者找了一帮小学生分成两组,一组是正儿八经地每人扔了 200 次钢蹦儿然后记下正反面,而另一组则是凭空“随机”写下 200 个正反面。然后他把这些都收集起来混在一起,试图自己把它们区分开来。他的成功率相当高,秘诀在于他发现在真正的随机结果中,200 次里多数会有连续出现 7 次正面或反面的情况,而假想“随机”的孩子则不大敢于写出这么长的连 1,一般游程都不会超过 4。所以他只要挑出游程在 5 以上的就基本上是真正随机得到的了。

所以如果你打牌连续输了 6 把,或者开车接连吃红灯,在反省你的人品问题以及技术问题之余,也许还有这冥冥之中的概率在起作用吧。


参考文献

[1] Schilling, Mark F. “The longest run of heads.” College Math. J 21.3 (1990): 196-207.
[2] Weisstein, Eric W. “Run.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/Run.html
[3] Révész, P. “Strong theorems on coin tossing.” Proceedings of the International Congress of Mathematicians, Helsinki. 1978.

分类: 技术相关 标签: ,
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

%d 博主赞过: