曾经面试的时候遇到过一道数学题，跟之前碰到过的题目都不一样，非常有意思，题目如下：
一个字典包含26个字符（\(a \sim z\)），从里面随机有放回地选取\(m\)个字符构成的字符串\(X\)，重复上述操作构成一个字符串\(Y\)。请问平均需要多少次比较操作，才能判断\(X\)和\(Y\)是否相等。
注意：\(X\)和\(Y\)的对应位置上的字符比较一次，记为一次比较操作。
（题目到这里并没有结束）
思路一：
对于每一次比较，相同的概率\(p(e) = 1/26\)，不同的概率\(p(n) = 25/26\)（因为是随机有放回），考虑比较\(x\)次的概率
当\(x <= m-1\)的时候，第\(x\)个字符不一样，第\(x\)个前面的全部一样
\(p(x) = p(e)^{x-1} * p(n)\)所以比较次数的期望值是：
\(E(x)=x * p(e)^{x-1} * p (n)\)当\(x=m\)的时候，第\(x\)个一样不一样都可以
\(p(x) = p(e)^{x-1}\) \(E(x) = x * p(e)^{x-1}\)所以字符串长度为\(m\)的时候比较次数的期望等于：
\(f(m) = E(1) + E(2) + … + E(m) \\ = \sum^{m-1}_{x=1} x * p(e)^{x-1} * p(n) + m * p(e)^{m-1} \\ = \sum^{m-1}_{x=1} x * (1/26)^{x-1} * (25/26)+ m * (1/26)^{m-1} \)（题目到这里依旧没有结束）
思路二：
每一次的比较，比较次数都会+1，其中25/26的概率不相同，如果不相同，则不需要新增比较次数，1/26的概率相同，如果相同，则需要继续比较，对于一个长度为m的字符串，比较了第一个过后，考虑第二个的时候其实等同于\(m-1\)的情况，即：
\(f(m) = 1 + 25/26 * 0 + 1/26 * f(m-1)\)又因为f(1) = 1
所以
\(f(m) = 1 + 1*1/26 + 1*(1/26)^2 + … + 1*(1/26)^{m-1}\)回看刚刚思路一的结论
\(f(m) = \sum^{m-1}_{x=1} x * (1/26)^{x-1} * (25/26)+ m * (1/26)^{m-1} \)问题终于来了，思路一和思路二最终表达式看起来显然并不相等，请问哪个是对的？
由于这是一道面试题而不是考试题，着重考察的是临场反应，所以题目本身可能存在误导性，比如：思路一和思路二其实是相等的。
首先代入几个值来算一算，会发现两个公式的值都是一样的，可是思路一里面有一个25/26，看起来怎么都跟思路二不一样。这里应该就是考察的纯数学sense了，在数学大佬同学指点一番过后我也总算是证明出来了：
\(f(m) = \sum_{x=1}^{m-1} x * p(e)^{x-1}*p(n) + m * p(e)^{m-1} \\ =\sum_{x=1}^{m-1} x * p(e)^{x-1} * (1-p(e)) + m * p(e)^{m-1} \\ = \sum_{x=1}^{m-1}(x*p(e)^{x-1} – x*p(e)^x) + m*p(e)^{m-1} \\ = \sum_{x=1}^{m-1}x*p(e)^{x-1} – \sum_{x=1}^{m-1}x*p(e)^x + m*p(e)^{m-1} \\ =\sum_{x=0}^{m-2}(x+1)p(e)^x – \sum_{x=1}^{m-1}x*p(e)^x + m*p(e)^{m-1} \\ = \sum_{x=0}^{m-2}x*p(e)^x + \sum_{x=0}^{m-2}p(e)^x – \sum_{x=1}^{m-1}x*p(e)^x + m*p(e)^{m-1} \\ = \sum_{x=1}^{m-2}x*p(e)^x – \sum_{x=1}^{m-1}x * p(e)^x + \sum_{x=0}^{m-2}p(e)^x \\ + (m-1)p(e)^{m-1} + p(e)^{m-1} \\ = \sum_{x=1}^{m-1}x*p(e)^x – \sum_{x=1}^{m-1}x*p(e)^x + \sum_{x=0}^{m-2}p(e)^x + p(e)^{m-1} \\ =\sum_{x=0}^{m-1}p(e)^x\)而\(\sum_{x=0}^{m-1}p(e)^x\) 其实就是思路二。
感觉自己平时工作中接触到的数学推导太少了，还是要多看多推呀。