去年写过一篇博客平均投几个三分才会连续进 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. https://mathworld.wolfram.com/Run.html
[3] Révész, P. “Strong theorems on coin tossing.” Proceedings of the International Congress of Mathematicians, Helsinki. 1978.