证明

KMP算法与一个经典概率问题

/ 22 条评论

    考虑一个事件，它有两种概率均等的结果。比如掷硬币，出现正面和反面的机会是相等的。现在我们希望知道，如果我不断抛掷硬币，需要多长时间才能得到一个特定的序列。

序列一：反面、正面、反面
序列二：反面、正面、正面

    首先，我反复抛掷硬币，直到最近的三次抛掷结果形成序列一，然后我记下这次我抛掷了多少次才得到了我要的序列。重复执行这个过程，我可以算出得到序列一平均需要的抛掷次数。同样地，反复抛掷硬币直到序列二产生，它所需要的次数也有一个平均值。你认为这两个平均值哪一个大哪一个小？换句话说，出现序列一平均所需的抛掷次数少还是出现序列二平均需要的次数少？

    大多数人会认为，两个序列会以同样快的速度出现，因为在所有“正”和“反”的8种三元组合里，“反正反”和“反正正”各占1/8，其概率是均等的。而事实上，我们将会看到掷出序列二所需的次数更少一些。不妨考虑这样一个问题：在由“正”和“反”构成的n位01序列中，有多少个序列以序列一结尾但之前不曾出现过序列一？有多少个序列以序列二结尾但之前不曾出现过序列二？当n比较小时，两者答案是一样的（例如n=3时符合要求的情况都是唯一的），但到后来n越大时，两者的差距越明显：后者的个数总比前者的个数要多一些。不妨看一看n=6的情况。对于序列一，只有以下5个序列是符合要求的：

  • 反反反反正反
  • 反正正反正反
  • 正正正反正反
  • 正反反反正反
  • 正正反反正反

    但对于序列二来说，符合条件的序列就有7个：

  • 反反反反正正
  • 反正反反正正
  • 反反正反正正
  • 正反反反正正
  • 正正反反正正
  • 正正正反正正
  • 正反正反正正

    你可以通过计算机编程枚举，计算一下n为其它值的情况。计算结果和刚才也一样：在n位01序列中，以序列二结尾但之前不含序列二的情况不会少于以序列一结尾但之前不含序列一的情况。这说明，抛掷第n次硬币后恰好出现了序列二，其概率不会小于恰好出现序列一的概率。显然，当n渐渐增大时，这个概率应该呈下降趋势；同时，随着n的增长，两个序列各自出现的概率由相等开始慢慢拉开差距，第n次抛掷产生序列二的概率下降得要缓慢一些，或者说更多的情况集中发生在n更小的时候。因此总的来说，出现序列二所需要的抛掷硬币次数的期望值更小。
    虽然我们通过一系列的观察验证了这个结论，并且我们也相信这个结论是正确的（虽然没有严格的证明），但我们仍然不是很接受这个结论。这种情况是有悖于我们的直觉的，它与我们的生活经验不相符合。此刻，我们迫切需要一个解释，来说明这种出人意料的反常现象产生的原因。

    如果不亲自做几次试验的话，你很难体会到这种微妙的差距。考虑整个游戏的实际过程，“反正正”序列显然会出现得更早一些。假如某一次我们得到了序列“反正”。如果我们需要的是“反正反”序列，那么下一次抛掷结果为反面将结束本轮的抛掷，而下一次是正面则前功尽弃，你必须再次从零开始。如果我们需要的是“反正正”序列，那么下一次抛掷结果为正面将结束本轮的抛掷，而下一次是反面的话我至少不会惨到一切归零，这相当于我已经有了一个反面作为新的开头，只需再来两个正面即可。这样看的话，提前掷出“反正正”的可能性更大一些。
    反复体会上面的想法，了解KMP算法的网友会恍然大悟：这就是KMP算法的基本思路！考虑这样一个问题：我们在当前字串中寻找子串“反正正”第一次出现的位置。假如当前已经能匹配模式串的前两个字“反正”，主串中的下一个字是“正”则匹配成功，主串的下一个字是“反”则将使模式串的当前匹配位置退到第一个字。考虑一个更复杂的例子：我们希望在主串中寻找子串abbaba，现在已经在主串中找到了abbab。如果主串下一个字符是a，则成功匹配；如果主串下一个字符是b，则模式串最多能匹配到的位置退到了第三个字符，我只需要从abb开始继续匹配，而不必一切从头再来。
    我们可以用KMP算法完美地解决上面的问题。首先预处理出一个数组c，c[i,0]表示模式串匹配到了第i个字符，主串下一个字符为0（反）时，模式串的匹配位置将退到哪里；同样地，c[i,1]表示模式串匹配到了第i个字符，主串下一个字符为1（正）时，新的模式串匹配位置在什么地方。设f[i,j]表示第i次抛掷硬币后恰好匹配到模式串第j位有多少种情况，则f[i,j]=Σf(i-1,k) + Σf(i-1,l)，其中k满足c[k,0]=j，l满足c[l,1]=j。将f[i,j]除以2的i次方，我们就得到了相应的概率值。或者更直接地，设P[i,j]表示第i次抛掷硬币后，最远能匹配到的模式串位置是第j位的概率，则P[i,j]=Σ( P(i-1,k)/2 ) + Σ( P(i-1,l)/2 )。注意，我们还应该添加一种特殊的概率值P[i,*]，它表示在主串第i个字符以前已经成功匹配过的概率，这样的话下表中每一列的和才能为1。

    来看一看程序的输出结果：
Pattern 1: s[]="aba"
主串位置       1        2       3       4       5       6       7       8       9      10
匹配到s[0]  0.5000  0.2500  0.2500  0.2500  0.2188  0.1875  0.1641  0.1445  0.1270  0.1113
匹配到s[1]  0.5000  0.5000  0.3750  0.3125  0.2813  0.2500  0.2188  0.1914  0.1680  0.1475
匹配到s[2]  0.0000  0.2500  0.2500  0.1875  0.1563  0.1406  0.1250  0.1094  0.0957  0.0840
匹配到s[3]  0.0000  0.0000  0.1250  0.1250  0.0938  0.0781  0.0703  0.0625  0.0547  0.0479
已找到匹配  0.0000  0.0000  0.0000  0.1250  0.2500  0.3438  0.4219  0.4922  0.5547  0.6094

Pattern 2: s[]="abb"
主串位置       1        2       3       4       5       6       7       8       9      10
匹配到s[0]  0.5000  0.2500  0.1250  0.0625  0.0313  0.0156  0.0078  0.
0039  0.0020  0.0010
匹配到s[1]  0.5000  0.5000  0.5000  0.4375  0.3750  0.3125  0.2578  0.2109  0.1719  0.1396
匹配到s[2]  0.0000  0.2500  0.2500  0.2500  0.2188  0.1875  0.1563  0.1289  0.1055  0.0859
匹配到s[3]  0.0000  0.0000  0.1250  0.1250  0.1250  0.1094  0.0938  0.0781  0.0645  0.0527
已找到匹配  0.0000  0.0000  0.0000  0.1250  0.2500  0.3750  0.4844  0.5781  0.6563  0.7207

    这下我们可以清楚地看到，序列二提前出现的概率要大得多。注意到，根据我们的概率定义，表格中每一列的数字之和都是1。同时，倒数第二行的数字之和（有无穷多项）也应该为1，因为最后一行的概率就是倒数第二行的概率值累加的结果，而根据最后一行概率的定义，主串无穷长时已找到匹配的概率应该为1。因此，我们也可以把倒数第二行看作是模式串在主串第i个位置首次匹配成功的概率。我们可以根据这一结果近似地计算出抛掷次数的期望值。

Matrix67原创
转贴请注明出处

趣题：丢失的机票 一个有趣的概率问题

/ 17 条评论

    一架客机上有100个座位，100个人排队依次登机。第一个乘客把机票搞丢了，但他仍被允许登机。由于他不知道他的座位在哪儿，他就随机选了一个座位坐下。以后每一个乘客登机时，如果他的座位是空着的，那么就在他的座位坐下；否则，他就随机选一个仍然空着的座位坐下。请问，最后一个人登机时发现唯一剩下的空位正好就是他的，其概率是多少？

    当最后一个乘客登机时，最后一个空位要么就是他的，要么就是第一个乘客的。由于所有人选择座位时都是随机选择的，这两个位置的“地位”相等，它们所面对的“命运”是相同的，不存在哪个概率大哪个概率小的问题。因此，它们成为最后一个空位的概率是均等的。也就是说，最后一个人发现剩下的空位正好是他的，其概率为50%。

来源：cut-the-knot
不知不觉地，这已经是第400篇日志了

趣题：直觉 VS 理性思考 经典概率问题

/ 18 条评论

    各种违反常理的错觉图片和数学事实告诉我们，我们的直觉并不可靠。其实这本身就是一种错觉，它让我们觉得我们的直觉总是不可信的。而事实上，多数情况下我们的直觉都是可信的，而理性的思考反而会带来一些错误。

    我的书桌有8个抽屉，分别用数字1到8编号。每次我拿到一份文件后，我都会把这份文件随机地（概率均等地）放在某一个抽屉中。但我非常粗心，有1/5的概率我会忘了把文件放在抽屉里，最终把这个文件搞丢了。
    现在，我要找一份非常重要的文件（比如GF的处女鉴定书）。我将按顺序打开每一个抽屉，直到找到这份文件为止，或者令人同情地，翻遍了所有抽屉都还没找到这份文件。考虑下面三个问题：

  • 1. 假如我打开了第一个抽屉，发现里面没有我要的文件。这份文件在其余7个抽屉里的概率是多少？
  • 2. 假如我翻遍了前4个抽屉，里面都没有我要的文件。这份文件在剩下的4个抽屉里的概率是多少？
  • 3. 假如我翻遍了前7个抽屉，里面都没有我要的文件。这份文件在最后一个抽屉里的概率是多少？

    你猜一猜这三个概率值是越来越大还是越来越小？你能算出准确的值来吗？

    三个概率值分别是7/9, 2/3和1/3。可能这有点出人意料，这个概率在不断减小；但设身处地地想一下，这也不是没有道理的。这正反映了我们实际生活中的心理状态：假如我肯定我的文件没被搞丢，每次发现抽屉里没有我要的东西时我都会更加坚信它在剩下的抽屉里；但如果我的文件很可能被搞丢了，那每翻过一个抽屉但没找到我的文件时，我就会更加担心。我会越来越担心，感到希望越来越渺茫，直到自己面对着第8个抽屉，呆呆地看着我的最后一丝希望，同时心里想：完了，这下可能是真丢了。

    平均每10份文件就有两份被搞丢，其余8份平均地分给了8个抽屉。假如我把所有搞丢了的文件都找回来了，那么它们应该有2个抽屉那么多。这让我们想到了这样一个有趣的思路：在这8个抽屉后加上两个虚拟抽屉──抽屉9和抽屉10，这两个抽屉专门用来装我丢掉的文件。我甚至可以把题目等价地变为：随机把文件放在10个抽屉里，但找文件时不允许打开最后两个抽屉。当我已经找过n个抽屉但仍没找到指定的文件时，文件只能在剩下的10-n个抽屉里，但我只能寻找剩下的8-n个抽屉，因此所求的概率是(8-n)/(10-n)。当0<=n<=8时，函数是一个递减函数。

参考资料：cut-the-knot
做人要厚道 转贴请注明出处

牛顿迭代法快速寻找平方根

/ 37 条评论

    下面这种方法可以很有效地求出根号a的近似值：首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了。
    例如，我想求根号2等于多少。假如我猜测的结果为4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了：

(       4  + 2/   4     ) / 2 = 2.25
(    2.25  + 2/   2.25  ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
….

      
    这种算法的原理很简单，我们仅仅是不断用(x,f(x))的切线来逼近方程x^2-a=0的根。根号a实际上就是x^2-a=0的一个正实根，这个函数的导数是2x。也就是说，函数上任一点(x,f(x))处的切线斜率是2x。那么，x-f(x)/(2x)就是一个比x更接近的近似值。代入f(x)=x^2-a得到x-(x^2-a)/(2x)，也就是(x+a/x)/2。
    同样的方法可以用在其它的近似值计算中。Quake III的源码中有一段非常牛B的开方取倒函数。

局部变动原理：算术平均数不小于几何平均数

/ 24 条评论

    前几天写的等高线模式中，在倒数第二个例子里我们证明了所有的圆内接n边形以正n边形最大。当时我们用到了一个很值得思考的方法：固定其余所有点的位置，只移动其中一个点的位置，那么这个点与左右相邻两点等距时面积才可能达到最大。这就说明圆内接n边形以正n边形最大，否则我可以不断寻找长度不等的邻边，通过一次次地调整不断地趋近我的最终目标。对于一个多变元函数，只有每个变量（在它所对应的单变量函数中）都达到最大时，所有变量才可能同时使函数值达到最大。这种思考方法被称之为“局部变动原理”。《数学与猜想》中提到了局部变动原理的另一个应用──证明n个数的算术平均数大于等于几何平均数。中学教材（至少在我的中学教材里）没有给出这一结论的证明。我自己曾经找到过这一定理的很多种证明，但《数学与猜想》中给出的是我所见到的最简洁、最有趣的证明。
    考虑两个数a和b，现在我已经知道它们的和是S，那么它们的乘积最大是多少？或许大家都知道，当两个数的和一定时，两数相等时乘积最大。也就是说，问题的答案就是((a+b)/2)^2。证明这个结论很简单，我们可以通过简单的代数运算看出，对于任意的a和b，((a+b)/2)^2不会小于ab。用前面的减去后面的，我们有
   ((a+b)/2)^2 – ab
= (a^2+2ab+b^2)/4 – ab
= (a^2-2ab+b^2)/4
= ((a-b)/2)^2
    可以看到，前者减去后者的差始终非负，并且仅当a=b时差值为0。

    下面考虑n个数a1, a2, …, an，现在已经知道它们的和是S，那么它们的乘积最大是多少？你也许不知道相关的定理，以前也不曾想过这个问题，但稍加思考你会说，当这n个数都相等时乘积最大。你或许以为你是凭直觉想到了这个结论，但事实上你的大脑已经不自觉地使用了局部变动法。固定其它n-2个数不变，只考虑其中两个数，那么很显然这两个数的和也已经固定了，并且增大它们的积也就可以改进整个问题的答案。而要想让这两个数的积最大，它们必须得相等才行。运用局部变动原理，则只有任两个数都相等，这n个数的乘积才会最大。此时，这n个数的值都等于(a1+a2+…+an)/n，只有这样它们的乘积才可能是最大的，任何其它情况下的a1*a2*…*an都比它小。
    仿照上面给出的式子，我们把这个结论写成如下形式：
( (a1+a2+…+an)/n )^n >= a1*a2*…*an
    两边同时开n次方，我们的结论赫然出现：n个数的算术平均数大于等于它们的几何平均数。

    今后我们还将看到这样的例子。
    做人要厚道，转贴请注明出处