杀死那个怪物

勇士将无限次地攻击怪物，怪物被砍中3次就会死，第 $k$ 次攻击的命中率为 $\frac{1}{2^k},k\in\mathbb N$

那么勇士能杀死这个怪物吗？

攻击无限次，期望总伤害值 $\displaystyle E(\mathrm{damage})=\sum_{k=0}^\infty\frac{1}{2^k}=2<3$ 确实小于怪物的体力值...

难道这就意味着怪物是不可战胜的吗？

不，不是的，即使一次又一次失败，勇士依然会一次又一次地冲锋，直到杀死怪物为止！

关键在于，我们真正关心的是，是 $n$ 次攻击后，怪物仍未被杀死的概率.

举个例子，在经典的一维随机游走模型中，我们从原点0开始，每一步以相同的概率向左或向右走.
即 $\{Z_n\}_{n\in\mathbb N}$ 为一系列随机变量， $Z_n=-1,1$ 表示向左走或向右走.
$S_n=\sum _{k=1}^nZ_k$ 为 $n$ 步之后的位置，那么显然有 $E(Sn)=0$.
也就是说任意时刻的期望位置都是原点.
但朴素的直觉告诉我们，对于数轴上的任意一个点，在无限游走的过程中迟早会经过该点！
因此 $E(S_n)=0$ 并不意味着 $S_n$ 永远也无法达到1926.
关键在于 $S_n$ 经过1926的概率，而计算可得这个概率是1！
如果随机游走永不停止， $\mathbb{Z}$ 上的简单随机游走将会无限次走过每一个点.
这个结果被称为常返(recurrence)或赌徒破产理论.
若一个拥有有限财富的赌徒和一家拥有无限金钱的银行玩“公平游戏”，最终赌徒一定会输掉. 赌徒的钱的数量将经过随机游走的过程，并且在某个时刻达到零，游戏结束.

明白了吗？我们关心的并不是总伤害值的期望，而是 $n$ 次攻击后，怪物仍未被杀死的概率.

那么接下来想必就是愉快的计算了吧？

先忽略必然命中的第0刀，设 $\{X_n\}_{n\in\mathbb N^*}$ 为一系列随机变量

$P(X_n=1)=\frac{1}{2^n},P(X_n=0)=1-\frac{1}{2^n}$

$\displaystyle S_n=\sum_{k=1}^n X_k$ 表示 $n$ 次攻击后造成的总伤害值. 当 $S_n$ 达到2时怪物就会被杀死.

$n$ 次攻击全部失败的概率为：

${\displaystyle P(S_n=0)=\prod_{k=1}^n\left(1-\frac{1}{2^k}\right)}\\$

n 次攻击只有一次命中的概率为：

$\displaystyle P(S_n=0)=\sum_{i=1}^n\frac{1}{2^i}\prod_{k\ne i}\left(1-\frac{1}{2^k}\right)\\ =\sum_{i=1}^n\frac{1}{2^i-1}\prod_{k=1}^n\left(1-\frac{1}{2^k}\right)$

那么成功杀死怪物的概率为：

$p_n=P(S_n\ge2)=1-P(S_n=0)-P(S_n=1) \\ =1-\left(1+\sum_{k=1}^n\frac{1}{2^k-1}\right)\prod_{k=1}^n\left(1-\frac{1}{2^k}\right)$

真是令人愉悦啊，只要可以得出当 $n\to\infty$ 时 $p_n\to 1$，就证明了在不限次数的攻击下，勇士迟早会杀死怪物.

那么这两个看起来有点怪怪的式子具体是多少呢？

不妨把 $\prod_{k=1}^\infty(1-\frac{1}{2^k})$ 记作 $a$

那么常规操作转换为求和

$\ln a=\sum_{k=1}^\infty \ln\left(1-\frac{1}{2^k}\right)$

由于 $-\ln (1-x)=\sum_{k=1}^\infty\frac{1}{k} x^k,0\le x<1$

进而有

$-\ln a=\sum_{k=1}^\infty\sum_{i=1}^\infty\frac{1}{i2^{ki}} \\ =\sum_{i=1}^\infty\frac{1}{i}\sum_{k=1}^\infty\frac{1}{2^{ki}} \\ =\sum_{i=1}^\infty\frac{1}{i(2^i-1)}$

遗憾的是这个表达式只能化简到这里了，根据Quora上的分享计算机数值计算结果 ，大致为 $−\ln ⁡a≈1.242,a≈0.288$. 详细信息可以查阅OEIS A048651 .

另一个式子 似乎更难计算了，根据WolframAlpha的计算结果

$\displaystyle\sum_{k=1}^\infty \frac{1}{2^k - 1} = 1 - \frac{\psi^{(0)}\left(\frac{1}{2}\right)}{\ln(2)} \approx 1.607$

看起来和我们想象的有很大不一样呢

非常遗憾，勇士能击败怪物的概率只有大约 25% ...

所谓的“即使一次又一次失败，勇士依然会一次又一次地冲锋，直到杀死怪物为止”，仅仅是我们一厢情愿的错误直觉（听起来有点残酷...）

如何说服自己从直觉上理解这种无限过程却不能成功的结果呢？

可以参考这样一个理论，一维和二维随机游走，返回原点的概率为1，然而在三维及以上的随机游走对此却不成立. 一个相对直观的角度是，在较高的维度，外面的空间会更加广阔，一旦我们走出一段距离后，会更容易迷失在浩瀚无垠的外界空间中，再也找不到回家的路.

所以，大概就简单地理解为，在一次次徒劳的攻击后，勇士早已忘却了自己的初心，只是麻木的做着挥剑的动作，但其实已经几乎不可能真的对怪物造成损失了...

P.S. 不保证以上计算过程全部正确，但可以确定击败怪物的概率并不是1.