有一个经典的概率问题：平均需要抛掷多少次硬币，才会首次出现连续的 n 个正面？它的答案是 2^(n+1) – 2 。取 n=2 的话，我们就有这样的结论：平均要抛掷 6 次硬币，才能得到两个连续的正面。或许这个期望次数比你想象中的要多吧。我们不妨试着来验证一下这一结果。由简单的递推可得，所有 1 都不相邻的 k 位 01 串有 F_k+2 个，其中 F_i 表示 Fibonacci 数列中的第 i 项。而“抛掷第 k 次才出现连续两个正面”的意思就是， k 位 01 串的末三位是 011 ，并且前面 k – 3 位中的数字 1 都不相邻。因此，在所有 2^k 个 k 位 01 串中，只有 F_k-1 个是满足要求的。因此，我们要求的期望值就等于 ∑ (k=2..∞) k * F_k-1 / 2^k 。这个无穷级数就等于 6 。我怎么算的呢？我用 Mathematica 算的。

 
    显然，当 n 更大的时候，期望值的计算更加复杂。而简单美妙的结论让我们不由得开始思考，这个问题有没有什么可以避免计算的巧妙思路？万万没有想到的是，在赌博问题的研究中，概率论帮了不少大忙；而这一回，该轮到赌博问题反过来立功了。
Read more…

    数学常数最令人着迷的就是，它们常常出现在一些看似与之毫不相干的场合中。 随便取一个 0 到 1 之间的数，再加上另一个 0 到 1 之间的随机数，然后再加上一个 0 到 1 之间的随机数⋯⋯直到和超过 1 为止。一个有趣的问题：平均需要加多少次，才能让和超过 1 呢？答案是 e 次。

Read more…

    偶然读到一个非常帅的证明：用信息熵可以瞬间证明素数有无穷多个。这个证明比本 Blog 之前讲过的五种非主流证明 (282, 539, 1678) 看上去都要帅，并且更重要地，它道出了素数无穷多的根本原因：只有无穷多的素数，才有能力表达出如此丰富的自然数世界。
    假设我们从所有不超过 n 的自然数中随机选取一个数 N ，并把它分解成质因数的乘积 N = P1^X1 * P2^X2 * … * Pm^Xm，其中 m 是不超过 n 的素数的个数。注意到由于 2^Xi ≤ Pi^Xi ≤ N ≤ n 对所有 i 都成立，因此我们有 Xi ≤ log(n) 。真正帅的地方来了。考虑随机选取一个 N 带来的信息熵，我们有：

log(n) = H(N)
         = H(X1, X2, …, Xm)
         ≤ H(X1) + H(X2) + … + H(Xm)
         ≤ log(log(n)+1) * m

    上面的第一个等号是由信息熵的定义直接得出的。第二个等号是由唯一分解定理得到的：由于一个数可以唯一地分解为质因数的乘积，因此 N 和 (X1, X2, …, Xm) 是一一对应的，知道了前者也就确定了后者，它们的信息熵是相同的。第三行的不等式是由于我们放开了 Xi 的取值条件（每个 Xi 独立取值可能会导致它们的乘积超过 n ），必然会增加结果的不确定性。而每个 Xi 的取值范围不会超出 0 到 log(n) ，最多 log(n)+1 种情况，因此 H(Xi) ≤ log(log(n)+1) ，这就得到了第四行的那个不等式。
    整理上式，我们得到了 m ≥ log(n) / log(log(n)+1) ，这不但告诉我们当 n 趋于无穷大时不超过 n 的素数个数也是趋于无穷的，还给出了不超过 n 的素数个数的一个下界。

    昨夜，M同学牵着女朋友的手走出宿舍楼，整夜没有回来；直到今天早晨，大家才见他支着腰回到寝室，样子十分疲惫。我们几个好友似乎已经心领神会，于是一行人走上前去，带着淫邪的笑容拷问他：昨晚干啥了，那么疲惫？本以为M同学会支支吾吾答不上话来，殊不知他义正严词地答道：我和女朋友去看通宵电影去了。几个人不服气，问他，那电影票呢？谁知他说了一句“忘了放哪儿了”后，还真煞有其事地在包里翻来翻去。一群人大笑着说，唉呀，你就别装了吧。两分钟后，我们全都傻了眼——M同学还真摸出两张电影票。一哥们儿猛地拍了一下M同学的肩膀说，唉呀，为了骗过我们真是煞费苦心啊，居然到影院门口找散场观众买了两张票根！
    笑过之后，我突然开始想，假如M同学为了掩饰自己的恶劣行径，真的准备好了伪证的话，他的演技可不是一般的高明。试着想象以下两个画面：

1. 几个人不服气，问他，那电影票呢？M同学不急不慢地从口袋里掏出两张电影票说，在这儿呢。
2. 几个人不服气，问他，那电影票呢？M同学假装到处寻找电影票，过了两分钟才翻出来。

    显然，第二种做法更令人相信，他真的跑去看通宵电影去了。事实上，M同学还能做得更好：

Read more…